Towards a Hierarchical Alternative for Implementing the Paxos Consensus Algorithm

• Acacia Terra Universidade Federal do Paraná
• Edson Tavares de Camargo Universidade Tecnológica Federal do Paraná https://orcid.org/0000-0002-6520-9142
• Elias Procópio Duarte Jr. Universidade Federal do Paraná https://orcid.org/0000-0002-8916-3302

DOI: https://doi.org/10.5753/wtf.2020.12484

Abstract

Paxos is one of the most important consensus algorithms. Consensus allows a set of processes to agree on a proposed value. This paper introduces a hierarchical implementation of a single Paxos instance. In the implementation, n acceptors are organized along a VCube, a virtual topology that is scalable by definition, presenting multiple logarithmic properties, even when there are faulty processes. A proposer communicates using a best-effort broadcast algorithm across the VCube to obtain votes from a majority of acceptors. Messages are autonomously propagated through the VCube. The proposed algorithm assumes an partially synchronous system with crash faults, and ensures safety and liveness (this property under weak synchrony assumptions). Simulation results include a comparison with Ring Paxos, an implementation of Paxos over a virtual ring topology.

Keywords: consensus, Paxos, vcube, hypercube

References

Cachin, C., Guerraoui, R., and Rodrigues, L. (2011). Introduction to Reliable and SecureDistributed Programming. Springer Publishing Company, Incorporated, 2nd edition.

Chandra, T. D. and Toueg, S. (1996). Unreliable failure detectors for reliable distributedsystems. J. ACM, 43(2):225-267.

Duarte, E. P., Bona, L. C. E., and Ruoso, V. K. (2014). Vcube: A provably scalabledistributed diagnosis algorithm. In 2014 5th Workshop on Latest Advances in ScalableAlgorithms for Large-Scale Systems, pages 17-22.

Fischer, M. J., Lynch, N. A., and Paterson, M. S. (1985). Impossibility of distributedconsensus with one faulty process. Journal of the ACM, 32(2):374-382.

Jalili Marandi, P., Primi, M., Schiper, N., and Pedone, F. (2017). Ring Paxos: High-Throughput Atomic Broadcast. The Computer Journal, 60(6):866-882.

Jeanneau, D., Rodrigues, L. A., Arantes, L., and Jr., E. P. D. (2017). An autonomic hierarchical reliable broadcast protocol for asynchronous distributed systems with failuredetection. J. Braz. Comp. Soc., 23(1):15:1-15:14.

Lamport (2001). Paxos made simple. SIGACTN: SIGACT News (ACM Special InterestGroup on Automata and Computability Theory), 32.

Lamport, L. (1998). The part-time parliament. ACM Trans. Comput. Syst., 16(2):133-169.

Lamport, L. (2006a). Fast paxos. Distributed Computing, 19(2):79-103.

Lamport, L. (2006b). Lower bounds for asynchronous consensus. Distributed Computing,19(2):104-125.

MacDougall, M. H. (1987). Simulating Computer Systems: Techniques and Tools. MITPress, Cambridge, MA, USA.

Moraru, I., Andersen, D. G., and Kaminsky, M. (2013). There is more consensus in ega-litarian parliaments. In Proceedings of the Twenty-Fourth ACM Symposium on Opera-ting Systems Principles, SOSP "13, pages 358-372, New York, NY, USA. ACM.

Parisa Jalili Marandi, Primi, M., Schiper, N., and Pedone, F. (2010). Ring paxos: A high-throughput atomic broadcast protocol. In 2010 IEEE/IFIP International Conferenceon Dependable Systems Networks (DSN), pages 527-536.

Rodrigues, L. A., Duarte Jr, E. P., and Arantes, L. (2014). Árvores geradoras mínimasdistribuídas e autonômicas. In Anais do 32º Simpósio Brasileiro de Redes de Compu-tadores e Sistemas Distribuídos — SBRC 2014, pages 1-14.