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
- 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?)
- 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 Randomization: A Hybrid Approach to Solve Consensus
- Failure detection and consensus in the crash-recovery model
- 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
- 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
(27)- Stopping times of distributed consensus protocols: a probabilistic analysis
- On the complexity of basic abstractions to implement consensus
- Switched PIOA: parallel composition via distributed scheduling
- A constructive proof for FLP
- Random Node-Asynchronous Updates on Graphs
- Lower bounds for asynchronous consensus
- Randomization and failure detection: a hybrid approach to solve consensus
- Simple constant-time consensus protocols in realistic failure models
- A reduction theorem for randomized distributed algorithms under weak adversaries
- Distributed Computing
- On the nonexistence of resilient consensus protocols
- Easy impossibility proofs for distributed consensus problems
- Fast randomized consensus using shared memory
- Random oracles in constantipole
- Task-structured probabilistic I/O automata
- Automata, Languages and Programming
- A partial equivalence between shared-memory and message-passing in an asynchronous fail-stop distributed environment
- On the Validity of Consensus
- Asynchronous byzantine agreement protocols
- Closed schedulers: a novel technique for analyzing asynchronous protocols
- Randomized consensus with regular registers
- Communication-efficient randomized consensus
- scientific article; zbMATH DE number 1256649 (Why is no real title available?)
- Monte Carlo and Las Vegas randomized algorithms for systems and control. An introduction
- Preserving hyperproperties of programs using primitives with consensus number 2
- Faster randomized consensus with an oblivious adversary
- The epigenetic consensus problem
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)
