Seth Gilbert

SODA Conference 2025 Conference Paper

Partial Synchrony for Free: New Upper Bounds for Byzantine Agreement

• Pierre Civit
• Muhammad Ayaz Dzulfikar
• Seth Gilbert
• Rachid Guerraoui
• Jovan Komatovic
• Manuel Vidigueira
• Igor Zablotchi

TCS Journal 2025 Journal Article

Robust overlays meet blockchains: On handling high churn and catastrophic failures

• Vijeth Aradhya
• Seth Gilbert
• Aquinas Hobor

Blockchains have become ubiquitous in the world of robust decentralized applications. A crucial requirement for implementing a blockchain is an “overlay network” providing reliable and efficient communication among the participants. In this work, we provide communication-efficient and churn-optimal (barring log factors) Byzantine-resilient algorithms for maintaining blockchain networks. Our approach utilizes an interesting “cross-layer optimization” wherein the overlay network relies on the blockchain that is built on top of it. An important contribution is a tight “half-life” analysis on the amount of churn that can be tolerated, where peers have bandwidth restrictions. Moreover, by leveraging synergies between the blockchain and the overlay, we provide non-trivial recovery guarantees from catastrophic failures, which include a large class of connectivity issues such as denial-of-service, or exponentially unlikely lucky streaks for Byzantine peers, etc.

TCS Journal 2020 Journal Article

On simple back-off in unreliable radio networks

• Seth Gilbert
• Nancy Lynch
• Calvin Newport
• Dominik Pajak

In this paper, we study local and global broadcast in the dual graph model, which describes communication in a radio network with both reliable and unreliable links. Existing work proved that efficient solutions to these problems are impossible in the dual graph model under standard assumptions. In real networks, however, simple back-off strategies tend to perform well for solving these basic communication tasks. We address this apparent paradox by introducing a new set of constraints to the dual graph model that better generalize the slow/fast fading behavior common in real networks. We prove that in the context of these new constraints, simple back-off strategies now provide efficient solutions to local and global broadcast in the dual graph model. We also precisely characterize how this efficiency degrades as the new constraints are reduced down to non-existent, and prove new lower bounds that establish this degradation as near optimal for a large class of natural algorithms. We conclude with an analysis of a more general model where we propose an enhanced back-off algorithm. These results provide theoretical foundations for the practical observation that simple back-off algorithms tend to work well even amid the complicated link dynamics of real radio networks.

SODA Conference 2017 Conference Paper

File Maintenance: When in Doubt, Change the Layout!

• Michael A. Bender
• Jeremy T. Fineman
• Seth Gilbert
• Tsvi Kopelowitz
• Pablo Montes

This paper gives a new deamortized solution to the sequential-file-maintenance problem. The data structure uses several new tools for solving this historically complicated problem. These tools include an unbalanced ternary-tree layout embedded in the sparse table, one-way rebalancing, and extra structural properties to keep interaction among rebalances to a minimum.

SODA Conference 2016 Conference Paper

How to Scale Exponential Backoff: Constant Throughput, Polylog Access Attempts, and Robustness

• Michael A. Bender
• Jeremy T. Fineman
• Seth Gilbert
• Maxwell Young

Randomized exponential backoff is a widely deployed technique for coordinating access to a shared resource. A good backoff protocol should, arguably, satisfy three natural properties: (i) it should provide constant throughput, wasting as little time as possible; (ii) it should require few failed access attempts, minimizing the amount of wasted effort; and (iii) it should be robust, continuing to work efficiently even if some of the access attempts fail for spurious reasons. Unfortunately, exponential backoff has some well-known limitations in two of these areas: it provides poor (sub-constant) throughput (in the worst case), and is not robust (to adversarial disruption). The goal of this paper is to “fix” exponential backoff by making it scalable, particularly focusing on the case where processes arrive in an on-line, worst-case fashion. We present a relatively simple backoff protocol, R e -B ackoff, that has, at its heart, a version of exponential backoff. It guarantees expected constant throughput with dynamic process arrivals and requires only an expected polylogarithmic number of access attempts per process. R e -B ackoff is also robust to periods where the shared resource is unavailable for a period of time. If it is unavailable for D time slots, R e -B ackoff provides the following guarantees. When the number of packets is a finite n, the average expected number of access attempts for successfully sending a packet is O (log 2 ( n + D )). In the infinite case, the average expected number of access attempts for successfully sending a packet is O (log 2 ( η + D )) where η is the maximum number of processes that are ever in the system concurrently.

SODA Conference 2014 Conference Paper

Dynamic Task Allocation in Asynchronous Shared Memory

• Dan Alistarh
• James Aspnes
• Michael A. Bender
• Rati Gelashvili
• Seth Gilbert

Task allocation is a classic distributed problem in which a set of p potentially faulty processes must cooperate to perform a set of tasks. This paper considers a new dynamic version of the problem, in which tasks are injected adversarially during an asynchronous execution. We give the first asynchronous shared-memory algorithm for dynamic task allocation, and we prove that our solution is optimal within logarithmic factors. The main algorithmic idea is a randomized concurrent data structure called a dynamic to-do tree, which allows processes to pick new tasks to perform at random from the set of available tasks, and to insert tasks at random empty locations in the data structure. Our analysis shows that these properties avoid duplicating work unnecessarily. On the other hand, since the adversary controls the input as well the scheduling, it can induce executions where lots of processes contend for a few available tasks, which is inefficient. However, we prove that every algorithm has the same problem: given an arbitrary input, if OPT is the worst-case complexity of the optimal algorithm on that input, then the expected work complexity of our algorithm on the same input is O ( OPT log 3 m ), where m is an upper bound on the number of tasks that are present in the system at any given time.

FOCS Conference 2012 Conference Paper

How to Allocate Tasks Asynchronously

• Dan Alistarh
• Michael A. Bender
• Seth Gilbert
• Rachid Guerraoui

Asynchronous task allocation is a fundamental problem in distributed computing in which p asynchronous processes must execute a set of m tasks. Also known as write-all or do-all, this problem been studied extensively, both independently and as a key building block for various distributed algorithms. In this paper, we break new ground on this classic problem: we introduce the To-Do Tree concurrent data structure, which improves on the best known randomized and deterministic upper bounds. In the presence of an adaptive adversary, the randomized To-Do Tree algorithm has O(m+plogplog2m) work complexity. We then show that there exists a deterministic variant of the To-Do Tree algorithm with work complexity O(m+p log5 m log2 max(m, p)). For all values of m and p, our algorithms are within log factors of the O(m + p log p) lower bound for this problem. The key technical ingredient in our results is a new approach for analyzing concurrent executions against a strong adaptive scheduler. This technique allows us to handle the complex dependencies between the processes' coin flips and their scheduling, and to tightly bound the work needed to perform subsets of the tasks.

FOCS Conference 2011 Conference Paper

Mutual Exclusion with O(log^2 Log n) Amortized Work

• Michael A. Bender
• Seth Gilbert

This paper presents a new algorithm for mutual exclusion in which each passage through the critical section costs amortized O(log 2 log n) RMRs with high probability. The algorithm operates in a standard asynchronous, local spinning, shared memory model with an oblivious adversary. It guarantees that every process enters the critical section with high probability. The algorithm achieves its efficient performance by exploiting a connection between mutual exclusion and approximate counting.

FOCS Conference 2011 Conference Paper

The Complexity of Renaming

• Dan Alistarh
• James Aspnes
• Seth Gilbert
• Rachid Guerraoui

We study the complexity of renaming, a fundamental problem in distributed computing in which a set of processes need to pick distinct names from a given namespace. We prove an individual lower bound of \Omega( k ) process steps for deterministic renaming into any namespace of size sub-exponential in k, where k is the number of participants. This bound is tight: it draws an exponential separation between deterministic and randomized solutions, and implies new tight bounds for deterministic fetch-and-increment registers, queues and stacks. The proof of the bound is interesting in its own right, for it relies on the first reduction from renaming to another fundamental problem in distributed computing: mutual exclusion. We complement our individual bound with a global lower bound of \Omega( k \log ( k / c ) ) on the total step complexity of renaming into a namespace of size ck, for any c \geq 1. This applies to randomized algorithms against a strong adversary, and helps derive new global lower bounds for randomized approximate counter and fetch-and-increment implementations, all tight within logarithmic factors.

SODA Conference 2010 Conference Paper

Distributed Agreement with Optimal Communication Complexity

• Seth Gilbert
• Dariusz R. Kowalski

SODA Conference 2009 Conference Paper

A new approach to incremental topological ordering

• Michael A. Bender
• Jeremy T. Fineman
• Seth Gilbert

TCS Journal 2009 Journal Article

Of malicious motes and suspicious sensors

• Seth Gilbert
• Rachid Guerraoui
• Calvin Newport

How efficiently can a malicious device disrupt a single-hop wireless network? Imagine two honest players attempting to exchange information in the presence of a malicious adversary that can disrupt communication by jamming or overwriting messages. Assume the adversary has a broadcast budget of β —unknown to the honest players. We show that communication can be delayed for 2 β + Θ ( lg | V | ) rounds, where V is the set of values that the honest players may transmit. We then derive, via reduction to this 3-player game, round complexity lower bounds for several classical n -player problems: 2 β + Ω ( lg | V | ) for reliable broadcast, 2 β + Ω ( log n ) for leader election, and 2 β + Ω ( k lg | V | / k ) for static k -selection. We also consider an extension of our adversary model that includes up to t crash failures. Here we show a bound of 2 β + Θ ( t ) rounds for binary consensus. We provide tight, or nearly tight, upper bounds for all four problems. From these results we can derive bounds on the efficiency of malicious disruption, stated in terms of two new metrics: jamming gain (the ratio of rounds delayed to adversarial broadcasts) and disruption-free complexity (the rounds required to terminate in the special case of no disruption). Two key conclusions of this study: (1) all the problems considered feature semantic vulnerabilities that allow an adversary to disrupt termination more efficiently than simple jamming (i. e. , all have a jamming gain greater than 1); and (2) for all the problems considered, the round complexity grows linearly with the number of bits to be communicated (i. e. , all have a Ω ( lg | V | ) or Ω ( lg n ) disruption-free complexity.)

TAAS Journal 2009 Journal Article

Self-stabilizing robot formations over unreliable networks

• Seth Gilbert
• Nancy Lynch
• Sayan Mitra
• Tina Nolte

We describe how a set of mobile robots can arrange themselves on any specified curve on the plane in the presence of dynamic changes both in the underlying ad hoc network and in the set of participating robots. Our strategy is for the mobile robots to implement a self-stabilizing virtual layer consisting of mobile client nodes, stationary Virtual Nodes (VNs), and local broadcast communication. The VNs are associated with predetermined regions in the plane and coordinate among themselves to distribute the client nodes relatively uniformly among the VNs' regions. Each VN directs its local client nodes to align themselves on the local portion of the target curve. The resulting motion coordination protocol is self-stabilizing, in that each robot can begin the execution in any arbitrary state and at any arbitrary location in the plane. In addition, self-stabilization ensures that the robots can adapt to changes in the desired target formation.