HyperPaxos em Múltiplas Instâncias sobre a LibPaxos: Uma Versão Hierárquica do Algoritmo de Consenso Paxos
DOI:
https://doi.org/10.5753/reic.2023.3427Keywords:
Consenso distribuído, Paxos, Algoritmos distribuídosAbstract
Algoritmos de consenso distribuído são essenciais para sistemas de armazenamento, bancos de dados, controle de acesso e orquestração de aplicações em nuvem. Este trabalho apresenta o algoritmo HyperPaxos, uma versão hierárquica de um dos principais algoritmos de consenso, o Paxos. O HyperPaxos é baseado na topologia virtual hierárquica vCube, que apresenta diversas propriedades logarítmicas. Os acceptors são organizados em clusters e os proposers executam as duas fases do Paxos escolhendo um acceptor dito difusor. O difusor é responsável por retransmitir as mensagens para os demais acceptors sobre o vCube. A difusão ocorre do maior cluster para o menor, retornando ao proposer quando uma maioria é atingida. O HyperPaxos foi implementado como a biblioteca libHyperPaxos. Resultados obtidos mostram o bom desempenho da libHyperPaxos, que inclusive supera a libPaxos e, em alguns casos, a implementação do U-Ring Paxos em decisões por segundo.
Downloads
Referências
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
Como Citar
Issue
Section
Licença
Copyright (c) 2023 Os autores
Este trabalho está licenciado sob uma licença Creative Commons Attribution-NonCommercial 4.0 International License.
