Distributed Agreement with Optimal Communication Complexity

Seth Gilbert, Dariusz R. KowalskiSODA 2010 · DOI

TL;DR

This paper presents a novel randomized consensus algorithm that achieves optimal communication complexity (O(n) bits) and near-optimal time complexity (O(log n) rounds) in synchronous distributed systems with crash failures. This breakthrough bridges a significant gap between theoretical lower bounds and existing practical solutions.

What Problem Does This Paper Address?

In distributed systems, "consensus" is the fundamental problem of getting a group of processes to agree on a single value, even if some processes fail. This is crucial for many distributed applications, like maintaining consistent databases or coordinating actions. The challenge lies in achieving this agreement efficiently, specifically in terms of communication (how much data is sent) and time (how long it takes). While previous algorithms achieved good time complexity, they often required a quadratic amount of communication (O(n²) messages/bits), which is impractical for large systems. This paper tackles the problem of achieving consensus with minimal communication (O(n) bits) and near-optimal time (O(log n) rounds), a goal that had remained elusive.

Methods

The core innovation of this paper is the "universe reduction" technique. Instead of having all n processes participate directly in a complex consensus protocol, the algorithm randomly selects a small subset of O(log n) "coordinators." These coordinators then run a simplified consensus protocol among themselves. The algorithm consists of three main sub-protocols:

  1. CHOOSEC: This sub-protocol efficiently selects the coordinators and ensures they are aware of each other, even in the presence of failures. It uses a probabilistic approach to manage coordinator discovery and consistency.
  2. LUCONSENSUS: This is a "limited universe consensus" protocol where only the selected coordinators participate. Because the number of coordinators is small, this protocol can be executed efficiently. It guarantees agreement among coordinators with high probability.
  3. DISSEMINATE: This sub-protocol handles the dissemination of the agreed-upon value from the coordinators to all other processes. It uses a novel, efficient work-sharing paradigm to ensure all non-failed processes receive the decision.

The paper also demonstrates how these techniques can be adapted to partially synchronous systems (where message delays can be unpredictable) and for the related problem of gossip (where processes need to learn all information from others).

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Universe Reduction as a Key Enabler: The central idea of delegating the heavy lifting of consensus to a small, randomly chosen subset of processes is a powerful abstraction that significantly reduces communication overhead.
  • Bridging the Communication Gap: The algorithm successfully closes the gap between the theoretical lower bound of O(n) communication bits and the previously achieved O(n log n) or higher complexities.
  • Probabilistic Guarantees for Efficiency: By relying on randomization and high-probability guarantees, the algorithm achieves efficiency that deterministic approaches struggle to match.
  • Adaptability to Partial Synchrony: The core techniques are shown to be robust enough to handle systems that are not perfectly synchronous, a critical consideration for real-world distributed systems.

Key Results

  • Optimal Communication Complexity: The algorithm achieves O(n) bits of communication complexity with high probability.
  • Near-Optimal Time Complexity: The algorithm terminates in O(log n) rounds with high probability.
  • Fault Tolerance: The protocol tolerates up to f < n/2 crash failures.
  • Adaptability: The techniques are extended to work in partially synchronous systems and for the gossip problem.

Limitations and Future Work

  • Locality: While the overall communication complexity is optimal, individual coordinators might still send a significant number of messages. The authors conjecture that achieving both locality (each process sending few bits) and optimal communication/time complexity might involve a trade-off.
  • Deterministic Consensus: The paper focuses on randomized algorithms. An open question is whether deterministic consensus can achieve both O(n) communication complexity and linear time complexity. The authors conjecture this is impossible.
  • Gossip Complexity: For the gossip problem, the communication complexity depends on the size of the "rumors" being gossiped, which is an inherent property of gossip protocols. However, for specific aggregation tasks (like finding an average), the bit complexity can be kept low.

Summary updated

BibTeX
@inproceedings{gilbert2010distributed,
  author = {Seth Gilbert and Dariusz R. Kowalski},
  title = {{Distributed Agreement with Optimal Communication Complexity}},
  booktitle = {SODA},
  year = {2010},
  doi = {10.1137/1.9781611973075.78},
}
Figure