Of choices, failures and asynchrony: the many faces of set agreement

DOI10.1007/s00453-011-9581-7zbMath1236.68016MaRDI QIDQ2428676

Rachid Guerraoui, Corentin Travers, Dan Alistarh, Seth Gilbert

Publication date: 26 April 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://infoscience.epfl.ch/record/174713

zbMATH Keywords

lower bounds; time complexity; distributed computing; message passing; set agreement; eventual synchrony

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68M14: Distributed systems

Cites Work

• Synchronous consensus under hybrid process and link failures
• Strongly terminating early-stopping \(k\)-set agreement in synchronous systems with general omission failures
• A topological treatment of early-deciding set-agreement
• More \(choices\) allow more \(faults\): Set consensus problems in totally asynchronous systems
• The inherent price of indulgence
• Booting clock synchronization in partially synchronous systems with hybrid process and link failures
• The Heard-Of model: computing in distributed systems with benign faults
• Round-by-round fault detectors (extended abstract)
• Structured derivations of consensus algorithms for failure detectors
• Tight bounds for k -set agreement
• The Complexity of Early Deciding Set Agreement
• The topological structure of asynchronous computability
• How to Solve Consensus in the Smallest Window of Synchrony
• The Byzantine Generals Problem
• Atomic snapshots of shared memory
• Atomic Snapshots in O (n log n) Operations
• Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
• The extended BG-simulation and the characterization of t-resiliency
• Timeliness, failure-detectors, and consensus performance
• Generalized FLP impossibility result for t-resilient asynchronous computations