Seth Lewis GILBERT

Dean's Chair Associate Professor
Assistant Dean, Graduate Studies

Ph.D. (Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts, 2007)
M.S. (Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts, 2003)
B.S. (Electrical Engineering & Mathematics, Yale University, New Haven, Connecticut, 1999)
651 62729

Research Areas

  • Algorithms & Theory
  • Systems & Networking

Research Interests

  • Distributed and Parallel Algorithms
  • Algorithms and Data Structures
  • Distributed Systems
  • My research focuses on algorithms for large-scale distributed systems, with a particular interest in issues of scalability and fault-tolerance. Examples include the following topics:
  • Wireless networks: In the context of wireless networks, I have explored the question of how we can use dynamic spectrum access (and multichannel wireless networking) to improve the reliability and efficiency of communication protocols.
  • Contention resolution: A closely related problem is contention resolution, where the goal is to efficiently share access to a limited resource (such as a wireless channel or a shared lock). It is quite difficult to ensure good throughput in a dynamic system, with a constantly changing number of participants. It is even more difficult to make such a protocol robust.
  • Dynamic networks: In general, dynamic networks with changing participants, varying connections, and unpredictable latencies create many challenges even in classical wired networks. We have studied several problems in such settings, including gossip protocols, consensus protocols, leader election, and random walks.
  • Optimization/Reallocation: I am also interested in a variety of optimization problems, particularly for dynamic systems. For example, consider maintaining a good schedule, even as jobs are added and removed from the schedule. How often do you have to reallocate existing jobs to ensure an efficient allocation? These types of resource allocation (and reallocation) problems show up frequently in dynamic systems.


Current Projects

Selected Publications

  • Slow links, fast links, and the cost of gossip. Seth Gilbert, Peter Robinson, Suman Sourav. (ICDCS 2018)

  • File Maintenance: When in Doubt, Change the Layout! Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Tsvi Kopelowitz, Pablo Montes. (SODA 2017)

  • Load balancing with bounded convergence in dynamic networks. Michael Dinitz, Jeremy T. Fineman, Seth Gilbert, Calvin Newport. (INFOCOM 2017)

  • How to Scale Exponential Backoff:  Constant Throughput, Polylog Access Attempts, and Robustness. Michael Bender, Jeremy Fineman, Seth Gilbert and Maxwell Young.  (SODA 2016)

  • Contention Resolution on a Fading Channel. Jeremy T. Fineman, Seth Gilbert, Fabian Kuhn, Calvin C. Newport. (PODC 2016)

  • A Secure Sharding Protocol For Open Blockchains. Loi Luu, Viswesh Narayanan, Chaodong Zheng, Kunal Baweja, Seth Gilbert, Prateek Saxena. (CCS 2016)

  • Reallocation Problems in Scheduling. Michael A. Bender, Martin Farach-Colton, Sándor P. Fekete, Jeremy T. Fineman, Seth Gilbert. (Algorithmica 2015)

  • Tight Bounds for Asynchronous Renaming. Dan Alistarh, James Aspnes, Keren Censor-Hillel, Seth Gilbert and Rachid Guerraoui. (Journal of the ACM 2014)

  • Asynchronous gossip. Chryssis Georgiou, Seth Gilbert, Rachid Guerraoui, Dariusz R. Kowalski. (Journal of the ACM 2013)

  • How to Allocate Tasks Asynchronously. Dan Alistarh, Michael A. Bender, Seth Gilbert and Rachid Guerraoui. (FOCS 2012)

  • Mutual Exclusion with O(log2log n) Amortized Work. Michael A. Bender and Seth Gilbert. (FOCS 2011)

  • Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services. Seth Gilbert and Nancy A. Lynch. (SIGACT News, 2002)

Awards & Honours

  • Young Researcher Award: NUS university-wide award for researchers under the age of 40, based on their impact and promise in research, 2014.
  • Faculty Teaching Excellence Award: For teaching in 2013/14, 2014/15, 2015/16.
  • School of Computing Teaching Excellence Honour Roll: 2016-2021
  • Annual Teaching Excellence Award: For teaching in 2013/14.
  • Dean’s Chair: Appointed Dean’s Chair Assistant Professor in April 2013.

Teaching (2018/2019)

  • CS5234: Combinatorial and Graph Algorithms
  • CS5330: Randomized Algorithms