Seth Gilbert

Research Interests

The main goal of my research is to develop algorithmic techniques for designing robust large-scale systems. At the heart of these large-scale systems is the problem of scalable, trusted coordination. How do we build platforms to support coordinated activity among large numbers of untrusted and unreliable participants? How do we cope with this constantly changing environment, where dynamic participation and continuous cycles of failure and repair are the norm? What are the fundamental algorithms needed to enable these types of large-scale, reliable distributed distributed? In general, I design algorithms for several different applications that rely on trusted coordination. Some of these applications are fairly concrete, such as new and efficient algorithms for Byzantine agreement, the critical problem for blockchains. Other applications are more abstract, such as distributing information in a dynamic networks or coordinating resource usage under varying levels of contention. There are several common techniques that underlie these results. They include:
• Accountability: If you can identify where a network is failing or who is attacking the network, then you can respond efficiently. This idea has shown up informally in my work for many years (see, e.g., ``DConstructor'', PODC 2020); more recently we have formalized the idea of accountability and showed how it plays a central role in agreement protocols (see, e.g., ``Polygraph'', ICDCS 2021).
• Work Sharing and Task Distribution: For many coordination problems, the critical challenge is in determining who does what task. We have studied this explicitly (e.g., ``How to allocate tasks asynchronously'', FOCS 2012; ``On the Complexity of Load Balancing in Dynamic Networks'', SPAA 2021); and we have seen how it applies to specific problems (e.g., ``A Secure Sharding Protocol For Open Blockchains'', CCS 2016). A careful distribution of work is also critical to communication efficiency, as has been evident in our more recent work on information dissemination (e.g., ``Every Bit Counts in Consensus'', DISC 2023).
• Contention Resolution: A fundamental problem underlying many coordination protocols is contention resolution: many devices/users need to share a set of common resources, and we need to efficiently allocate those resources. We have focused on the question of efficiency (e.g., ``Leader Election in Well-Connected Graphs'', Algorithmic 2023), the challenge of robustness (e.g., ``Scaling Exponential Backoff: Constant Throughput, Polylogarithmic Channel-Access Attempts, and Robustness'', JACM 2019), and the problem of adapting to different network settings (e.g., ``Contention Resolution for Coded Radio Networks'', SPAA 2022).

Overall, my research has led to significant new insights in how to design robust and scalable algorithms for large-scale coordination.