Technical reports

Paxos at war

Piotr Zieliński

June 2004, 30 pages

DOI: 10.48456/tr-593

Abstract

The optimistic latency of Byzantine Paxos can be reduced from three communication steps to two, without using public-key cryptography. This is done by making a decision when more than (n+3f)/2 acceptors report to have received the same proposal from the leader, with n being the total number of acceptors and f the number of the faulty ones. No further improvement in latency is possible, because every Consensus algorithm must take at least two steps even in benign settings. Moreover, if the leader is correct, our protocol achieves the latency of at most three steps, even if some other processes fail. These two properties make this the fastest Byzantine agreement protocol proposed so far.

By running many instances of this algorithm in parallel, we can implement Vector Consensus and Byzantine Atomic Broadcast in two and three steps, respectively, which is two steps faster than any other known algorithm.

Full text

PDF (0.3 MB)

BibTeX record

@TechReport{UCAM-CL-TR-593,
  author =	 {Zieli{\'n}ski, Piotr},
  title = 	 {{Paxos at war}},
  year = 	 2004,
  month = 	 jun,
  url = 	 {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-593.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  doi = 	 {10.48456/tr-593},
  number = 	 {UCAM-CL-TR-593}
}