HyperPaxos em Múltiplas Instâncias sobre a LibPaxos: Uma Versão Hierárquica do Algoritmo de Consenso Paxos

Authors

  • Djenifer R. Pereira Universidade Federal do Paraná
  • Fernando M. Kiotheka Universidade Federal do Paraná
  • Elias P. Duarte Jr. Universidade Federal do Paraná

DOI:

https://doi.org/10.5753/reic.2023.3427

Keywords:

Consenso distribuído, Paxos, Algoritmos distribuídos

Abstract

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

Não há dados estatísticos.

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

2023-08-05

Como Citar

Pereira, D. R., Kiotheka, F. M., & Duarte Jr., E. P. (2023). HyperPaxos em Múltiplas Instâncias sobre a LibPaxos: Uma Versão Hierárquica do Algoritmo de Consenso Paxos. Revista Eletrônica De Iniciação Científica Em Computação, 21(2), 11–20. https://doi.org/10.5753/reic.2023.3427