2002/09/06 by James Aspnes, Aspnes, James · 1 citation
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #Distributed #Distributed systems and fault tolerance #F.1.2 #F.2.2 #FOS: Computer and information sciences #Modular Robots and Swarm Intelligence #Parallel #and Cluster Computing (cs.DC) #cs.DC #cs.DS
paper · pdf · doi:10.48550/arxiv.cs/0209014
29 pages; survey paper written for PODC 20th anniversary issue of Distributed Computing
arxiv created 2002/09/06 · openalex publication_date 2002/09/06 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The famous Fischer, Lynch, and Paterson impossibility proof shows that it is impossible to solve the consensus problem in a natural model of an asynchronous distributed system if even a single process can fail. Since its publication, two decades of work on fault-tolerant asynchronous consensus algorithms have evaded this impossibility result by using extended models that provide (a) randomization, (b) additional timing assumptions, (c) failure detectors, or (d) stronger synchronization mechanisms than are available in the basic model. Concentrating on the first of these approaches, we illustrate the history and structure of randomized asynchronous consensus protocols by giving detailed descriptions of several such protocols.