Lower Bounds on Consensus
Leslie Lamport · 2016
We derive lower bounds on the number of messages and the number of message delays required by a nonblocking fault-tolerant consensus algorithm, and we show that variants of the Paxos algorithm achieve those bounds. 1