Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Lower Bounds for Asynchronous Consensus

Leslie Lamport


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.


Publication typeTechReport
InstitutionMicrosoft Research
> Publications > Lower Bounds for Asynchronous Consensus