publication . Preprint . 2020

On the Significance of Consecutive Ballots in Paxos

Goldweber, Eli; Zhang, Nuda; Kapritsos, Manos;
Open Access English
  • Published: 02 Jun 2020
Abstract
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 o...
Subjects
ACM Computing Classification System: ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION
free text keywords: Computer Science - Distributed, Parallel, and Cluster Computing, C.4.1
Download from
34 references, page 1 of 3

[1] Ailidani Ailijiang, Aleksey Charapko, Murat Demirbas, and Tevfik Kosar. 2019. WPaxos: Wide area network flexible consensus. IEEE Transactions on Parallel and Distributed Systems 31, 1 (2019), 211-223.

[2] Balaji Arun, Sebastiano Peluso, Roberto Palmieri, Giuliano Losa, and Binoy Ravindran. 2017. Speeding up consensus by chasing fast decisions. In 2017 47th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). IEEE, 49-60.

[3] Jason Baker, Chris Bond, James C. Corbett, JJ Furman, Andrey Khorlin, James Larson, Jean-Michel Leon, Yawei Li, Alexander Lloyd, and Vadim Yushprakh. 2011. Megastore: Providing Scalable, Highly Available Storage for Interactive Services. In Proceedings of the Conference on Innovative Data system Research (CIDR). 223-234. http://www.cidrdb.org/cidr2011/Papers/CIDR11_Paper32.pdf

[4] Romain Boichat, Partha Dutta, Svend Frølund, and Rachid Guerraoui. 2003. Deconstructing paxos. ACM Sigact News 34, 1 (2003), 47-67.

[5] Mike Burrows. 2006. The Chubby lock service for loosely-coupled distributed systems. In Proceedings of the 7th symposium on Operating systems design and implementation. 335-350.

[6] Miguel Castro, Barbara Liskov, et al. 1999. Practical Byzantine fault tolerance. In OSDI, Vol. 99. 173-186.

[7] Tushar D Chandra, Robert Griesemer, and Joshua Redstone. 2007. Paxos made live: an engineering perspective. In Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing. 398-407.

[8] James C Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, Jeffrey John Furman, Sanjay Ghemawat, Andrey Gubarev, Christopher Heiser, Peter Hochschild, et al. 2013. Spanner: GoogleâĂŹs globally distributed database. ACM Transactions on Computer Systems (TOCS) 31, 3 (2013), 1-22.

[9] Leonardo De Moura and Nikolaj Bjørner. 2008. Z3: An efficient SMT solver. In International conference on Tools and Algorithms for the Construction and Analysis of Systems. Springer, 337-340.

[10] Michael J Fischer, Nancy A Lynch, and Michael S Paterson. 1985. Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM) 32, 2 (1985), 374-382.

[11] Eli Gafni and Leslie Lamport. 2003. Disk paxos. Distributed Computing 16, 1 (2003), 1-20.

[12] Chris Hawblitzel, Jon Howell, Manos Kapritsos, Jacob R Lorch, Bryan Parno, Michael L Roberts, Srinath Setty, and Brian Zill. 2015. IronFleet: proving practical distributed systems correct. In Proceedings of the 25th Symposium on Operating Systems Principles. 1-17.

[13] Heidi Howard. 2019. Distributed consensus revised. Ph.D. Dissertation. University of Cambridge.

[14] Heidi Howard, Dahlia Malkhi, and Alexander Spiegelman. 2016. Flexible paxos: Quorum intersection revisited. arXiv preprint arXiv:1608.06696 (2016). [OpenAIRE]

[15] Heidi Howard and Richard Mortier. 2019. A Generalised Solution to Distributed Consensus. arXiv preprint arXiv:1902.06776 (2019). [OpenAIRE]

34 references, page 1 of 3
Abstract
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 o...
Subjects
ACM Computing Classification System: ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION
free text keywords: Computer Science - Distributed, Parallel, and Cluster Computing, C.4.1
Download from
34 references, page 1 of 3

[1] Ailidani Ailijiang, Aleksey Charapko, Murat Demirbas, and Tevfik Kosar. 2019. WPaxos: Wide area network flexible consensus. IEEE Transactions on Parallel and Distributed Systems 31, 1 (2019), 211-223.

[2] Balaji Arun, Sebastiano Peluso, Roberto Palmieri, Giuliano Losa, and Binoy Ravindran. 2017. Speeding up consensus by chasing fast decisions. In 2017 47th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). IEEE, 49-60.

[3] Jason Baker, Chris Bond, James C. Corbett, JJ Furman, Andrey Khorlin, James Larson, Jean-Michel Leon, Yawei Li, Alexander Lloyd, and Vadim Yushprakh. 2011. Megastore: Providing Scalable, Highly Available Storage for Interactive Services. In Proceedings of the Conference on Innovative Data system Research (CIDR). 223-234. http://www.cidrdb.org/cidr2011/Papers/CIDR11_Paper32.pdf

[4] Romain Boichat, Partha Dutta, Svend Frølund, and Rachid Guerraoui. 2003. Deconstructing paxos. ACM Sigact News 34, 1 (2003), 47-67.

[5] Mike Burrows. 2006. The Chubby lock service for loosely-coupled distributed systems. In Proceedings of the 7th symposium on Operating systems design and implementation. 335-350.

[6] Miguel Castro, Barbara Liskov, et al. 1999. Practical Byzantine fault tolerance. In OSDI, Vol. 99. 173-186.

[7] Tushar D Chandra, Robert Griesemer, and Joshua Redstone. 2007. Paxos made live: an engineering perspective. In Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing. 398-407.

[8] James C Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, Jeffrey John Furman, Sanjay Ghemawat, Andrey Gubarev, Christopher Heiser, Peter Hochschild, et al. 2013. Spanner: GoogleâĂŹs globally distributed database. ACM Transactions on Computer Systems (TOCS) 31, 3 (2013), 1-22.

[9] Leonardo De Moura and Nikolaj Bjørner. 2008. Z3: An efficient SMT solver. In International conference on Tools and Algorithms for the Construction and Analysis of Systems. Springer, 337-340.

[10] Michael J Fischer, Nancy A Lynch, and Michael S Paterson. 1985. Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM) 32, 2 (1985), 374-382.

[11] Eli Gafni and Leslie Lamport. 2003. Disk paxos. Distributed Computing 16, 1 (2003), 1-20.

[12] Chris Hawblitzel, Jon Howell, Manos Kapritsos, Jacob R Lorch, Bryan Parno, Michael L Roberts, Srinath Setty, and Brian Zill. 2015. IronFleet: proving practical distributed systems correct. In Proceedings of the 25th Symposium on Operating Systems Principles. 1-17.

[13] Heidi Howard. 2019. Distributed consensus revised. Ph.D. Dissertation. University of Cambridge.

[14] Heidi Howard, Dahlia Malkhi, and Alexander Spiegelman. 2016. Flexible paxos: Quorum intersection revisited. arXiv preprint arXiv:1608.06696 (2016). [OpenAIRE]

[15] Heidi Howard and Richard Mortier. 2019. A Generalised Solution to Distributed Consensus. arXiv preprint arXiv:1902.06776 (2019). [OpenAIRE]

34 references, page 1 of 3
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue