Randomized protocols for asynchronous consensus
From MaRDI portal
Abstract: 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.
Recommendations
- Asynchronous byzantine agreement protocols
- Impossibility of distributed consensus with one faulty process
- Randomized Consensus in Expected O(N\log ^2 N) Operations Per Processor
- On the nonexistence of resilient consensus protocols
- A simple and fast asynchronous consensus protocol based on a weak failure detector
Cites work
- An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement
- An randomized Byzantine agreement protocol with constant expected time and guaranteed termination in optimal (deterministic) time
- Asynchronous consensus and broadcast protocols
- Bounds on the time to reach agreement in the presence of timing uncertainty
- Computing with faulty shared objects
- Consensus numbers of multi-objects
- Determining consensus numbers
- Efficient asynchronous consensus with the weak adversary scheduler
- Failure detection and consensus in the crash-recovery model
- Failure Detection and Randomization: A Hybrid Approach to Solve Consensus
- Fast asynchronous Byzantine agreement with optimal resilience
- Fast deterministic consensus in a noisy environment
- Fast randomized consensus using shared memory
- Fault-tolerant wait-free shared objects
- scientific article; zbMATH DE number 1696671 (Why is no real title available?)
- scientific article; zbMATH DE number 432838 (Why is no real title available?)
- scientific article; zbMATH DE number 1179121 (Why is no real title available?)
- scientific article; zbMATH DE number 2102783 (Why is no real title available?)
- Impossibility of distributed consensus with one faulty process
- Lower bounds for distributed coin-flipping and randomized consensus
- On the minimal synchronism needed for distributed consensus
- Polylog randomized wait-free consensus
- Randomized Consensus in Expected O(N\log ^2 N) Operations Per Processor
- Reaching Agreement in the Presence of Faults
- Robust wait-free hierarchies
- Software transactional memory
- The best of both worlds: Guaranteeing termination in fast randomized Byzantine agreement protocols
- The correctness proof of Ben-Or's randomized consensus algorithm
- The power of multiobjects.
- The weakest failure detector for solving consensus
- Time- and Space-Efficient Randomized Consensus
- Time-Adaptive Algorithms for Synchronization
- Time-Lapse Snapshots
- Unreliable failure detectors for reliable distributed systems
- Wait-free consensus with infinite arrivals
- Wait-free synchronization in multiprogrammed systems
Cited in
(29)- Easy impossibility proofs for distributed consensus problems
- Stopping times of distributed consensus protocols: a probabilistic analysis
- Asynchronous byzantine agreement protocols
- Task-structured probabilistic I/O automata
- Lower bounds for asynchronous consensus
- Randomized consensus with regular registers
- Communication-efficient randomized consensus
- The epigenetic consensus problem
- A reduction theorem for randomized distributed algorithms under weak adversaries
- Monte Carlo and Las Vegas randomized algorithms for systems and control. An introduction
- Fast randomized consensus using shared memory
- Simple constant-time consensus protocols in realistic failure models
- A partial equivalence between shared-memory and message-passing in an asynchronous fail-stop distributed environment
- Failure Detection and Randomization: A Hybrid Approach to Solve Consensus
- scientific article; zbMATH DE number 1256649 (Why is no real title available?)
- Solvability in Asynchronous Environments II: Finite Interactive Tasks
- Closed schedulers: a novel technique for analyzing asynchronous protocols
- Random oracles in constantipole
- Random Node-Asynchronous Updates on Graphs
- Distributed Computing
- Automata, Languages and Programming
- Faster randomized consensus with an oblivious adversary
- On the Validity of Consensus
- Randomization and failure detection: a hybrid approach to solve consensus
- On the complexity of basic abstractions to implement consensus
- Preserving hyperproperties of programs using primitives with consensus number 2
- On the nonexistence of resilient consensus protocols
- A constructive proof for FLP
- Switched PIOA: parallel composition via distributed scheduling
This page was built for publication: Randomized protocols for asynchronous consensus
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5138489)
