HyperPaxos in Multiple Instances over LibPaxos: A Hierarchical Version of the Paxos Consensus Algorithm
DOI:
https://doi.org/10.5753/reic.2023.3427Keywords:
Consenso distribuído, Paxos, Algoritmos distribuídosAbstract
Distributed consensus algorithms are essential components of storage systems and databases, and have multiple other applications, such as in access control and orchestration of cloud applications. This paper presents the HyperPaxos algorithm, a hierarchical version of one of the most important consensus algorithms, Paxos. HyperPaxos is based on the vCube hierarchical virtual topology, which has several logarithmic properties. Acceptors are organized in clusters and proposers execute the two Paxos phases by choosing an acceptor that is responsible for relaying the messages to the other acceptors across the vCube. Broadcast starts from the largest cluster to the smallest, returning to the proposer as soon as a majority is reached. HyperPaxos was implemented as the libHyperPaxos library. Results obtained highlight the performance of libHyperPaxos, which surpasses libPaxos and, in some cases, the implementation of U-Ring Paxos in decisions per second.
Downloads
References
Benz, S. (2017). sambenz/URingPaxos: URingPaxos - A high throughput atomic multicast protocol. https://github.com/sambenz/URingPaxos.
Brewer, E. (2017). Spanner, TrueTime and the CAP Theorem. Technical report, Google.
Cachin, C., Guerraoui, R., and Rodrigues, L. (2011). Introduction to reliable and secure distributed programming. Springer Science & Business Media, 2nd edition.
Duarte Jr, E. P., Bona, L. C. E., and Ruoso, V. K. (2014). VCube: A Provably Scalable Distributed Diagnosis Algorithm. In 5th ScalA, pages 17–22.
Dwork, C., Lynch, N., and Stockmeyer, L. (1988). Consensus in the presence of partial synchrony. Journal of the ACM (JACM), 35(2):288–323.
Hurfin, M., Mostefaoui, A., and Raynal, M. (1998). Consensus in asynchronous systems where processes can crash and recover. In The 17th SRDS, pages 280–286.
Jalili Marandi, P., Primi, M., Schiper, N., and Pedone, F. (2017). Ring Paxos: High-throughput atomic broadcast. The Computer Journal, 60(6):866–882.
Kiotheka, F. M. and Pereira, D. R. (2022a). HyperPaxos / LibHyperPaxos - GitLab. https://gitlab.c3sl.ufpr.br/hyperpaxos/libhyperpaxos.
Kiotheka, F. M. and Pereira, D. R. (2022b). HyperPaxos em múltiplas instâncias sobre a LibPaxos: Uma versão hierárquica do algoritmo de consenso Paxos. TCC, UFPR.
Kiotheka, F. M., Pereira, D. R., Camargo, E. T., and Duarte Jr, E. P. (2023). HyperPaxos: Uma Versão Hierárquica do Algoritmo de Consenso Paxos. XLI SBRC, pages 1–14.
Lamport, L. (1998). The Part-Time Parliament. ACM Transactions on Computer Systems, 16(2):133–169.
Lamport, L. (2001). Paxos made simple. ACM SIGACT News (Distributed Computing Column) 32, 4 (Whole Number 121, December 2001), pages 51–58.
Primi, M. and Sciascia, D. (2013). LibPaxos: Open-source Paxos. http://libpaxos.sourceforge.net/.
Red Hat (2019). What is etcd? https://www.redhat.com/en/topics/containers/what-is-etcd.
Regis, S. and Mendizabal, O. M. (2022). An ́alise comparativa do algoritmo Paxos e suas variações. In XXIII WTF, pages 71–84.
Renesse, R. v. and Altinbuken, D. (2015). Paxos Made Moderately Complex. ACM Computing Surveys (CSUR), 47(3):1–36.
Rodrigues, L. A., Duarte Jr, E. P., and Arantes, L. (2014). Árvores geradoras mínimas distribuídas e autonômicas. XXXII SBRC, 2014:1–14.
Weil, S. A., Leung, A. W., Brandt, S. A., and Maltzahn, C. (2007). Rados: a scalable, reliable storage service for petabyte-scale storage clusters. In Proceedings of the 2nd international workshop on Petascale data storage, pages 35–44.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 Os autores
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
