2020/06/02 by Eli Goldweber, Goldweber, Eli, Nuda Zhang +3 · 1 citation
Computer Science · #C.4.1 #Cryptography and Data Security #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Parallel #Security and Verification in Computing #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2006.01885
openalex publication_date 2020/06/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we examine the Paxos protocol and demonstrate how the discrete numbering of ballots can be leveraged to weaken the conditions for learning. Specifically, we define the notion of consecutive ballots and use this to define Consecutive Quorums. Consecutive Quorums weakens the learning criterion such that a learner does not need matching accept messages sent in the same ballot from a majority of acceptors to learn a value. We prove that this modification preserves the original safety and liveness guarantees of Paxos. We define Consecutive Paxos which encapsulates the properties of discrete consecutive ballots. To establish the correctness of these results, we, in addition to a paper proof, formally verify the correctness of a State Machine Replication Library built on top of an optimized version of Multi-Paxos modified to reflect Consecutive Paxos.