Lower bounds for asynchronous consensus
- 29 June 2006
- journal article
- Published by Springer Science and Business Media LLC in Distributed Computing
- Vol. 19 (2), 104-125
- https://doi.org/10.1007/s00446-006-0155-x
Abstract
Impossibility results and best-case lower bounds are proved for the number of message delays and the number of processes required to reach agreement in an asynchronous consensus algorithm that tolerates non-Byzantine failures. General algorithms exist that achieve these lower bounds in the normal case, when the response time of non-faulty processes and the transmission delay of messages they send to one another are bounded. Our theorems allow algorithms to do better in certain exceptional cases, and such algorithms are presented. Two of these exceptional algorithms may be of practical interest.Keywords
This publication has 11 references indexed in Scilit:
- Fast PaxosDistributed Computing, 2006
- Lower Bounds for Asynchronous ConsensusPublished by Springer Science and Business Media LLC ,2003
- Handling message semantics with Generic Broadcast protocolsDistributed Computing, 2002
- Consensus in One Communication StepLecture Notes in Computer Science, 2001
- Revisiting the paxos algorithmTheoretical Computer Science, 2000
- The part-time parliamentACM Transactions on Computer Systems, 1998
- How to Write a ProofThe American Mathematical Monthly, 1995
- Consensus in the presence of partial synchronyJournal of the ACM, 1988
- Impossibility of distributed consensus with one faulty processJournal of the ACM, 1985
- Time, clocks, and the ordering of events in a distributed systemCommunications of the ACM, 1978