A Hundred Impossibility Proofs for Distributed Computing

✨ Summary

Overview

Nancy Lynch presents a survey of more than one hundred impossibility and lower-bound results in distributed computing. The paper does not establish one new theorem; instead, it organizes existing results, explains their proof techniques, provides historical context, and identifies common principles underlying apparently different impossibility arguments. The surveyed topics include shared-memory resource allocation, distributed consensus, shared registers, computation in rings and other networks, communication protocols, and miscellaneous distributed tasks. (groups.csail.mit.edu)

Central insight

The paper identifies the limitation imposed by local knowledge as the fundamental idea behind the surveyed results. A process must behave identically in executions that are indistinguishable from its local perspective. Impossibility proofs exploit this fact by constructing executions or configurations that look the same to selected processes but require incompatible behavior. The paper emphasizes that precise formal models are essential because small changes in timing, failures, communication, fairness, or process capabilities can change the result.

Main proof techniques

• Pigeonhole arguments: Limited shared-memory values force different executions to produce indistinguishable states.
• Scenario and indistinguishability arguments: Carefully constructed executions make processes behave as though they were in different systems or fault scenarios.
• Chain arguments: A sequence of executions changes one relevant feature at a time, forcing a contradiction between neighboring executions.
• Bivalence arguments: A configuration from which both decisions remain possible is shown to persist or to lead to a contradiction with termination.
• Symmetry and distance arguments: Indistinguishable processes or limited communication distance prevent leader election, coordination, or efficient computation.
• Communication-structure arguments: Message diagrams, message stealing, finite-state limitations, and graph constructions establish lower bounds for protocols and networks.
• Reductions: Results for one problem or model are transferred to another through simulations or problem transformations.

Results surveyed

The discussion covers lower bounds on shared-memory size for mutual exclusion and resource allocation; process counts, rounds, messages, and timing conditions for consensus; asynchronous consensus impossibility in the presence of failures; limits on commit, synchronization, and register implementation; message complexity in rings, complete graphs, meshes, and general networks; communication-protocol limitations; database availability under network partitions; termination detection; and hardware coordination problems. Particular attention is given to how stronger communication primitives, authentication, randomization, synchrony, or failure assumptions can avoid or weaken an impossibility result.

Methodological conclusions

Lynch argues that impossibility work depends heavily on well-designed problem statements and models. Specifications should be precise, crisp, sufficiently general, and no stronger than necessary. Models must describe admissible executions, liveness assumptions, control of actions, and the interaction between algorithms and their environments. The paper also observes that attempts to prove impossibility can generate useful positive results: failed proofs may expose counterexample algorithms, while successful proofs can indicate which assumptions must be added to make a task solvable.

Influence

The paper became an established survey reference for distributed-computing impossibility theory. Fich and Ruppert’s 2003 survey explicitly describes itself as building on Lynch’s survey while extending coverage of models, complexity measures, and proof techniques. (researchgate.net) Later research continues to cite it as background for impossibility, consensus, and lower-bound arguments, including work presented at DISC 2023. (drops.dagstuhl.de) The paper has also been used as recommended or assigned reading in distributed-systems courses, including courses at the University of Chicago, the University of Illinois, and Harvard. (classes.cs.uchicago.edu)