Seth Gilbert


Department of Computer Science
National University of Singapore


Home · Google Scholar · DBLP · CV(pdf)


Papers

Click here for abstracts and more details.


2017

File Maintenance: When in Doubt, Change the Layout!
by Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Tsvi Kopelowitz, and Pablo Montes
Proceedings of the Symposium on Discrete Algorithms, (SODA), 2017

Who are you? Secure identities in single hop ad hoc networks
by Seth Gilbert, Calvin Newport, and Chaodong Zheng
Distributed Computing, 30(2):103–125, 2017


2016

A Secure Sharding Protocol For Open Blockchains
by Loi Luu, Viswesh Narayanan, Chaodong Zheng, Kunal Baweja, Seth Gilbert, and Prateek Saxena
Proceedings of the Conference on Computer and Communications Security (CCS), October, 2016

Contention Resolution on a Fading Channel
by Jeremy T. Fineman, Seth Gilbert, Fabian Kuhn, and Calvin Newport
Proceeding of the Symposium on Principles of Distributed Computing (PODC), July, 2016

PSync: Visible Light-Based Time Synchronization for Internet of Things
by Xiangfa Guo, Mobashir Mohammad, Sudipta Saha, Mun Choon Chan, Seth Gilbert, and Derek Leong
Proceedings of INFOCOM, April, 2016

How to Scale Exponential Backoff: Constant Throughput, Polylog Access Attempts, and Robustness
by Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Maxwell Young
Proceedings of the Symposium on Discrete Algorithms (SODA), Pages: 636–654
January, 2016

A New Approach to Incremental Cycle Detection and Related Problems
by Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Robert E. Tarjan
ACM Trans. Algorithms, 12(2)2016


2015

QProbe: Locating the Bottleneck in Cellular Communication
by Nimantha Baranasuriya, Vishnu Navda, Venkat Padmanabhan, and Seth Gilbert
Proceedings of the Conference on emerging Networking EXperiments and Technologies (CoNEXT), December, 2015

On Differentially Private Online Collaborative Recommendation Systems
by Seth Gilbert, Xiao Liu, and Haifeng Yu
Proceedings of the International Conference on Information Security and Cryptology (ICISC), Pages: 210–226
November, 2015

Smoothed Analysis of Dynamic Networks
by Michael Dinitz, Jeremy T. Fineman, Seth Gilbert, and Calvin C. Newport
Proceedings of the Symposium on Distributed Computing (DISC), Pages: 513–527
October, 2015

The Computational Power of Beeps
by Seth Gilbert and Calvin C. Newport
Proceedings of the Symposium on Distributed Computing (DISC), Pages: 31–46
October, 2015

Efficient Communication in Cognitive Radio Networks
by Seth Gilbert, Fabian Kuhn, Calvin Newport, and Chaodong Zheng
Proceedings of the Symposium on Principles of Distributed Computing (PODC), Pages: 119–128
July, 2015

Cost-Oblivious Reallocation for Scheduling and Planning
by Michael A. Bender, Martin Farach-Colton, Sándor P. Fekete, Jeremy T. Fineman, and Seth Gilbert
Proceedings of the Symposium on Parallelism in Algorithms and Architectures (SPAA), Pages: 143–154
June, 2015

Reallocation Problems in Scheduling
by Michael A. Bender, Martin Farach-Colton, Sándor P. Fekete, Jeremy T. Fineman, and Seth Gilbert
Algorithmica, 73(2):389–409, 2015

Resource-Competitive Algorithms
by Michael A. Bender, Jeremy T. Fineman, Mahnush Movahedi, Jared Saia, Varsha Dani, Seth Gilbert, Seth Pettie, and Maxwell Young
SIGACT News, 46(3):57–71, 2015

SybilCast: Broadcast on the Open Airwaves
by Seth Gilbert and Chaodong Zheng
TOPC, 2(3):16, 2015


2014

Making Sense of Relativistic Distributed Systems
by Seth Gilbert and Wojciech M. Golab
Proceedings of the Symposium on Distributed Computing (DISC), Pages: 361–375
October, 2014

Who Are You? Secure Identities in Ad Hoc Networks
by Seth Gilbert, Calvin Newport, and Chaodong Zheng
Proceeding of the International Symposium on Distributed Computing (DISC), October, 2014

(Near) optimal resource-competitive broadcast with jamming
by Seth Gilbert, Valerie King, Seth Pettie, Ely Porat, Jared Saia, and Maxwell Young
Proceedings of the Symposium on Parallelism in Algorithms and Architectures (SPAA), Pages: 257–266
June, 2014

Cost-oblivious storage reallocation
by Michael A. Bender, Martin Farach-Colton, Sandor P. Fekete, Jeremy T. Fineman, and Seth Gilbert
Proceeding of the Symposium on Principles of Database Systems (PODS), June, 2014

Aggregation in Smartphone Sensor Networks
by Nimantha Thushan Baranasuriya, Seth Lewis Gilbert, Calvin C. Newport, and Jayanthi Rao
Proceedings of the Conference on Distributed Computing in Sensor Systems (DCOSS), Pages: 101–110
May, 2014

Dynamic task allocation in asynchronous shared memory
by Dan Alistarh, James Aspnes, Michael Bender, Rati Gelashvili, and Seth Gilbert
Proceedings of the Symposium on Discrete Algorithms (SODA), January, 2014

Structuring unreliable radio networks
by Keren Censor-Hillel, Seth Gilbert, Fabian Kuhn, Nancy A. Lynch, and Calvin C. Newport
Distributed Computing, 27(1):1–19, 2014

Tight Bounds for Asynchronous Renaming
by Dan Alistarh, James Aspnes, Keren Censor-Hillel, Seth Gilbert, and Rachid Guerraoui
J. ACM, 61(3):18:1–18:51, 2014


2013

Broadcast in the Ad Hoc SINR Model
by Sebastian Daum, Seth Gilbert, Fabian Kuhn, and Calvin C. Newport
Proceeding of the International Conference on Distributed Computing (DISC), October, 2013

Maximal independent set in multichannel radio networks
by Sebastian Daum, Mohsen Ghaffari, Seth Gilbert, Fabian Kuhn, and Calvin C. Newport
Proceedings of the Symposium on Principles of Distributed Computing (PODC), July, 2013

Reallocation problems in scheduling
by Michael A. Bender, Martin Farach-Colton, Sandor P. Fekete, Jeremy T. Fineman, and Seth Gilbert
Proceeding of the Symposium on Parallelism in Algorithms and Architectures (SPAA), July, 2013

SybilCast: broadcast on the open airwaves
by Seth Gilbert and Chaodong Zheng
Proceeding of the Symposium on Parallelism in Algorithms and Architectures (SPAA), July, 2013

Asynchronous Gossip
by Chryssis Georgiou, Seth Gilbert, Rachid Guerraoui, and Dariusz R. Kowalski
Journal of the ACM, 60(2)April, 2013


2012

Optimal Broadcast in Shared Spectrum Radio Networks
by Mohsen Ghaffari, Seth Gilbert, Calvin Newport, and Henry Tan
Proceedings of the Conference On Principles Of Distributed Systems (OPODIS), December, 2012

How to Allocate Tasks Asynchronously
by Dan Alistarh, Michael Bender, Seth Gilbert, and Rachid Guerraoui
Proceedings of the Symposium on Foundations of Computer Science (FOCS), October, 2012

Aggregation in dynamic networks
by Alejandro Cornejo, Seth Gilbert, and Calvin C. Newport
Proceedings of the Symposium on Principles of Distributed Computing (PODC), July, 2012

Leader election in shared spectrum radio networks
by Sebastian Daum, Seth Gilbert, Fabian Kuhn, and Calvin C. Newport
Proceedings of the Symposium on Principles of Distributed Computing (PODC), July, 2012

Making evildoers pay: resource-competitive broadcast in sensor networks
by Seth Gilbert and Maxwell Young
Proceedings of the Symposium on Principles of Distributed Computing (PODC), July, 2012

Resource-competitive analysis: a new perspective on attack-resistant distributed computing
by Seth Gilbert, Jared Saia, Valerie King, and Maxwell Young
Proceedings of the Workshop on Foundations of Mobile Computing (FOMC), July, 2012

Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement
by Dan Alistarh, Seth Gilbert, Rachid Guerraoui, and Corentin Travers
Algorithmica, 62(1-2):595-629, February, 2012

Perspectives on the CAP Theorem
by Seth Gilbert and Nancy A. Lynch
IEEE Computer, 45(2):30-36, 2012


2011

Meeting the deadline: On the complexity of fault-tolerant continuous gossip
by Chryssis Georgiou, Seth Gilbert, and Dariusz R. Kowalski
Distributed Computing, 24(5):223–244, December, 2011

Mutual Exclusion with $O(\log^2\log n)$ Amortized Work
by Michael A. Bender and Seth Gilbert
Proceedings of the Symposium on Foundations of Computer Science (FOCS), October, 2011
To download the paper: pdf format 

The Complexity of Renaming
by Dan Alistarh, James Aspnes, Seth Gilbert, and Rachid Guerraoui
Proceedings of the Symposium on Foundations of Computer Science (FOCS), October, 2011
To download the paper: pdf format 

Leveraging Channel Diversity to Gain Efficiency and Robustness for Wireless Broadcast
by Shlomi Dolev, Seth Gilbert, Majid Khabbazian, and Calvin Newport
Proceedings of the Symposium on Distributed Computing (DISC), September, 2011
To download the paper: pdf format 

Confidential Gossip
by Chryssis Georgiou, Seth Gilbert, and Dariusz Kowalski
Proceedings of the International Conference on Distributed Computing Systems (ICDCS), June, 2011
To download the paper: pdf format 

Optimal-Time Adaptive Strong Renaming, with Applications to Counting
by Dan Alistarh, James Aspnes, Keren Censor-Hillel, Seth Gilbert, and Morteza Zadimoghaddam
Proceedings of the International Conference on Principles of Distributed Computing (PODC), June, 2011
To download the paper: pdf format 

Structuring Unreliable Radio Networks
by Keren Censor-Hillel, Seth Gilbert, Fabian Kuhn, Nancy Lynch, and Calvin Newport
Proceedings of the International Conference on Principles of Distributed Computing (PODC), June, 2011
To download the paper: pdf format 

Generating Fast Indulgent Algorithms
by Dan Alistarh, Seth Gilbert, Rachid Guerraoui, and Corentin Travers
Proceedings of the International Conference On Distributed Computing and Networking (ICDCN), January, 2011
To download the paper: pdf format 


2010

RAMBO: Rapidly Reconfigurable Atomic Memory for Dynamic Networks
by Seth Gilbert, Nancy A. Lynch, and Alex A. Shvartsman
Distributed Computing, 23(4):225-272, December, 2010

Fast Randomized Test-and-Set and Renaming
by Dan Alistarh, Hagit Attiya, Seth Gilbert, Andrei Giurgiu, and Rachid Guerraoui
Proceedings of the International Symposium on Distributed Computing (DISC), September, 2010
To download the paper: pdf format 

Trusted Computing for Fault-Prone Wireless Networks
by Seth Gilbert and Dariusz Kowalski
Proceedings of the International Symposium on Distributed Computing (DISC), September, 2010
To download the paper: pdf format 

How efficient can gossip be? (On the message complexity of resilient information exchange)
by Dan Alistarh, Seth Gilbert, Rachid Guerraoui, and Morteza Zadimoghaddam
Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), July, 2010
To download the paper: pdf format 

Meeting the deadline: On the complexity of fault-tolerant continuous gossip
by Chryssis Georgiou, Seth Gilbert, and Dariusz R. Kowalski
Proceedings of the Symposium on Principles of Distributed Computing (PODC), July, 2010
To download the paper: pdf format 

Collaborative Scoring with Dishonest Participants
by Seth Gilbert, Rachid Guerraoui, Raezeh Malakouti Rad, and Morteza Zadimoghaddam
Proceedings of the Symposium on Parallelism in Algorithms and Architectures (SPAA), June, 2010
To download the paper: pdf format 

Securing Your Every Bit: Reliable Broadcast in Byzantine Wireless Networks
by Dan Alistarh, Seth Gilbert, Rachid Guerraoui, Zarko Milosevic, and Calvin Newport
Proceedings of the Symposium on Parallelism in Algorithms and Architectures (SPAA), June, 2010
To download the paper: pdf format 

Distributed Agreement with Optimal Communication Complexity
by Seth Gilbert and Dariusz Kowalski
Proceedings of the Symposium on Discrete Algorithms (SODA), January, 2010
To download the paper: pdf format 


2009

Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement
by Dan Alistarh, Seth Gilbert, Rachid Guerraoui, and Corentin Travers
Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC), December, 2009
To download the paper: pdf format 

The Wireless Synchronization Problem
by Shlomi Dolev, Seth Gilbert, Rachid Guerraoui, Fabian Kuhn, and Calvin Newport
Proceeding of the 28th Symposium on Principles of Distributed Computing (PODC), August, 2009
To download the paper: pdf format 

Interference-Resilient Information Exchange
by Seth Gilbert, Rachid Guerraoui, Dariusz Kowalski, and Calvin Newport
Proceedings of INFOCOM, April, 2009
To download the paper: pdf format 

Of Malicious Motes and Suspicious Sensors: On the Efficiency of Malicious Interference in Wireless Networks
by Seth Gilbert, Rachid Guerraoui, and Calvin Newport
Theoretical Computer Science, 410(6–7):546–569, February, 2009

A New Approach to Incremental Topological Ordering
by Michael A. Bender, Jeremy T. Fineman, and Seth Gilbert
Proceedings of the Symposium on Discrete Algorithms (SODA), January, 2009
To download the paper: pdf format 

Reconfigurable Distributed Storage for Dynamic Networks
by Gregory Chockler, Seth Gilbert, Vincent C. Gramoli, Peter M. Musial, and Alex A. Shvartsman
Journal of Parallel and Distributed Computing, 69(1):100–116, January, 2009

Self-Stabilizing Robot Formations over Unreliable Networks
by Seth Gilbert, Nancy Lynch, Sayan Mitra, and Tina Nolte
Transactions on Autonomous and Adaptive Systems (TAAS), Special Issue on Self-Adaptive and Self-Organising Wireless Networking Systems, 4(3)2009


2008

Self-Stabilizing Mobile Robot Formations with Virtual Nodes
by Seth Gilbert, Nancy A. Lynch, Sayan Mitra, and Tina Nolte
Proceedings of the Symposium on Stabilization, Safety and Security of Distributed Systems (SSS), December, 2008
To download the paper: pdf format 

How to solve consensus in the smallest window of synchrony
by Dan Alistarh, Seth Gilbert, Rachid Guerraoui, and Corentin Travers
22nd International Symposium on Distributed Computing (DISC), September, 2008
To download the paper: pdf format 

On the Complexity of Asynchronous Gossip
by Chryssis Georgiou, Seth Gilbert, Rachid Guerraoui, and Dariusz Kowalski
Proceeding of the 27th Symposium on Principles of Distributed Computing (PODC), August, 2008
To download the paper: pdf format 

Secure Communication over Radio Channels
by Shlomi Dolev, Seth Gilbert, Rachid Guerraoui, and Calvin Newport
Proceeding of the 27th Symposium on Principles of Distributed Computing (PODC), August, 2008
To download the paper: pdf format 

Virtual Infrastructure for Collision-Prone Wireless Networks
by Gregory Chockler, Seth Gilbert, and Nancy A. Lynch
Proceeding of the 27th Symposium on Principles of Distributed Computing (PODC), August, 2008
To download the paper: pdf format 
To download talk slides: ppt format 

Consensus and Collision Detectors in Radio Networks
by Gregory Chockler, Murat Demirbas, Seth Gilbert, Nancy A. Lynch, Calvin Newport, and Tina Nolte
Distributed Computing, 21(1):55–84, June, 2008

Extensible Encoding of Type Hierarchies
by Hamed S. Alavi, Seth Gilbert, and Rachid Guerraoui
Proceedings of the Symposium on Principles of Programming Languages (POPL), January, 2008
To download the paper: pdf format 


2007

Gossiping in a Multi-Channel Radio Network (An Oblivious Approach to Coping With Malicious Interference)
by Shlomi Dolev, Seth Gilbert, Rachid Guerraoui, and Calvin Newport
Proceedings of the the 21st International Symposium on Distributed Computing (DISC), September, 2007
To download the paper: pdf format 
To download talk slides: ppt format 

On the Message Complexity of Indulgent Consensus
by Seth Gilbert, Rachid Guerraoui, and Dariusz Kowalski
Proceedings of the the 21st International Symposium on Distributed Computing (DISC), September, 2007
To download the paper: pdf format 
To download talk slides: ppt format 

The Virtual Node Layer: A Programming Abstraction for Wireless Sensor Networks
by Matthew Brown, Seth Gilbert, Nancy A. Lynch, Calvin Newport, Tina Nolte, and Michael Spindel
Proceedings of the the International Workshop on Wireless Sensor Network Architecture (WWSNA), April, 2007
To download the paper: pdf format 

Virtual Infrastructure for Wireless Ad Hoc Networks
by Seth Gilbert
Ph. D. Thesis, MIT, 2007
To download the paper: pdf format 


2006

Of Malicious Motes and Suspicious Sensors: On the Efficiency of Malicious Interference in Wireless Networks
by Seth Gilbert, Rachid Guerraoui, and Calvin Newport
Proceedings of the 10th International Conference On Principles Of Distributed Systems (OPODIS), December, 2006
To download the paper: pdf format 

Contention Resolution with Heterogeneous Job Sizes
by Michael A. Bender, Jeremy T. Fineman, and Seth Gilbert
Proceedings of the 14th Annual European Symposium on Algorithms (ESA), September, 2006
To download the paper: pdf format 
To download talk slides: ppt format 

Playing Games in Many Possible Worlds
by Matthew Lepinski, David Liben-Nowell, Seth Gilbert, and April Rasala Lehman
Proceedings of the Seventh ACM Conference on Electronic Commerce (EC), June, 2006
To download the paper: pdf format 

Communication-Efficient Probabilistic Quorum Systems
by Gregory Chockler, Seth Gilbert, and Boaz Patt-Shamir
Proceedings of the International Workshop on Foundations and Algorithms for Wireless Networking (FAWN), March, 2006
To download the paper: pdf format 


2005

Reconfigurable Distributed Storage for Dynamic Networks
by Gregory Chockler, Seth Gilbert, Vincent C. Gramoli, Peter M. Musial, and Alex A. Shvartsman
9th International Conference on Principles of Distributed Systems (OPODIS), December, 2005
To download the paper: pdf format 

Timed Virtual Stationary Automata for Mobile Networks
by Shlomi Dolev, Seth Gilbert, Limor Lahiani, Nancy A. Lynch, and Tina Nolte
9th International Conference on Principles of Distributed Systems (OPODIS), December, 2005
To download the paper: pdf format 

GeoQuorums: Implementing Atomic Memory in Mobile Ad Hoc Networks
by Shlomi Dolev, Seth Gilbert, Nancy A. Lynch, Alex A. Shvartsman, and Jennifer Welch
Distributed Computing, 18(2):125–155, November, 2005

A Middleware Framework for Robust Applications in Wireless Ad Hoc Networks
by Gregory Chockler, Murat Demirbas, Seth Gilbert, and Calvin Newport
Proceeding of the 43rd Allerton Conference on Communication, Control, and Computing, September, 2005 (Invited)
To download the paper: pdf format 

Autonomous Virtual Mobile Nodes
by Shlomi Dolev, Seth Gilbert, Elad Schiller, Alex A. Shvartsman, and Jennifer Welch
Proceeding of the 3rd Workshop on Foundations of Mobile Computing (DIAL-M-POMC), September, 2005
To download the paper: pdf format 

Timed Virtual Stationary Automata for Mobile Networks
by Shlomi Dolev, Seth Gilbert, Limor Lahiani, Nancy A. Lynch, and Tina Nolte
Proceeding of the 43rd Allerton Conference on Communication, Control, and Computing, September, 2005 (Invited)
To download the paper: pdf format 

Brief Announcement: Virtual Stationary Automata for Mobile Networks
by Shlomi Dolev, Limor Lahiani, Seth Gilbert, Nancy A. Lynch, and Tina Nolte
Proceeding of the 24th Symposium on Principles of Distributed Computing (PODC), July, 2005

Concurrent Cache-Oblivious B-Trees
by Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Bradley C. Kuszmaul
Proceedings of the Seventeenth Symposium on Parallelism in Algorithms and Architectures (SPAA), July, 2005
To download the paper: pdf format 

Consensus and Collision Detectors in Wireless Ad Hoc Networks
by Gregory Chockler, Murat Demirbas, Seth Gilbert, Calvin Newport, and Tina Nolte
24th Annual Symposium on the Principles of Distributed Computing (PODC), July, 2005
To download the paper: pdf format 
To download talk slides: ppt format 

Etna: a fault-tolerant algorithm for atomic mutable DHT data
by Athicha Muthitacharoen, Seth Gilbert, and Robert Morris
Technical Report , MIT, June, 2005

Reconciling the Theory and Practice of UnReliable Wireless Broadcast
by Gregory Chockler, Murat Demirbas, Seth Gilbert, Nancy A. Lynch, Calvin Newport, and Tina Nolte
International Workshop on Assurance in Distributed Systems and Networks (ADSN), June, 2005
To download the paper: pdf format 


2004

The Quorum Deployment Problem
by Seth Gilbert and Grzegorz Malewicz
Proceedings of the 8th International Conference on Principles of Distributed Systems (OPODIS), December, 2004
To download the paper: pdf format 
To download talk slides: ppt format 

Virtual Mobile Nodes for Mobile Ad Hoc Networks
by Shlomi Dolev, Seth Gilbert, Nancy A. Lynch, Elad Schiller, Alex A. Shvartsman, and Jennifer Welch
Proceeding of the 18th International Conference on Distributed Computing (DISC), October, 2004
To download the paper: pdf format 
To download talk slides: ppt format 

Brief Announcement: Virtual Mobile Nodes for Mobile Ad Hoc Networks
by Shlomi Dolev, Seth Gilbert, Nancy A. Lynch, Elad Schiller, Alex A. Shvartsman, and Jennifer Welch
Proceeding of the 23rd Symposium on Principles of Distributed Computing (PODC), July, 2004

On-the-Fly Maintenance of Series-Parallel Relationships in Fork-Join Multithreaded Programs
by Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Charles E. Leiserson
Proceedings of the Sixteenth ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), July, 2004
To download the paper: pdf format 

RamboNodes for the Metropolitan Ad Hoc Network
by Jake Beal and Seth Gilbert
Proceedings of DIWANS Workshop, International Conference on Dependable Systems and Networks (DSN), July, 2004
To download the paper: pdf format 
To download talk slides: ppt format 


2003

GeoQuorums: Implementing Atomic Memory in Mobile Ad Hoc Networks
by Shlomi Dolev, Seth Gilbert, Nancy A. Lynch, Alex A. Shvartsman, and Jennifer Welch
Proceeding of the 17th International Conference on Distributed Computing (DISC), October, 2003
To download the paper: pdf format 
To download talk slides: ppt format 

RAMBO II: Rapidly Reconfigurable Atomic Memory for Dynamic Networks
by Seth Gilbert, Nancy A. Lynch, and Alex A. Shvartsman
Proceedings of the International Conference on Dependable Systems and Networks (DSN), June, 2003
To download the paper: pdf format 
To download talk slides: ppt format 

RAMBO II: Rapidly Reconfigurable Atomic Memory for Dynamic Networks
by Seth Gilbert
Master's Thesis, MIT, 2003
To download the paper: pdf format 


2002

Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services
by Seth Gilbert and Nancy A. Lynch
SigAct News, June, 2002
To download the paper: pdf format 



E-mail: seth dot gilbert at comp dot nus dot edu dot sg Office: COM2-3-23 Phone: +65-6516-2729