Lower Bounds for Asynchronous Consensus

This paper contains the precise statements and proofs of the results announced in [143] for the non-Byzantine case. It also includes another result showing that a completely general consensus algorithm cannot be faster than the Paxos algorithm of [122] in the presence of conflicting requests. However, there are two exceptional cases in which this result does not hold, and the paper presents potentially useful optimal algorithms for both cases.