Uma Estratégia de Difusão Agressiva para Aumentar a Vazão do Algoritmo de Consenso HyperPaxos

• Djenifer R. Pereira UFPR
• Fernando M. Kiotheka UFPR
• Elias P. Duarte Jr. UFPR

DOI: https://doi.org/10.5753/sbrc_estendido.2023.815

Resumo

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 uma estratégia para melhorar a vazão do algoritmo HyperPaxos em termos de decisões por segundo. 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. Neste trabalho, propomos que o difusor adote uma estratégia de difusão agressiva para transmitir, de uma só vez, as mensagens para uma maioria de acceptors paralelamente. A estratégia proposta foi implementada e comparada à versão original. Resultados obtidos mostram o desempenho superior da estratégia proposta em todos os cenários testados.

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.

Duarte Jr, E. P. and Nanya, T. (1998). A hierarchical adaptive distributed system-level diagnosis algorithm. IEEE Transactions on Computers, 47(1):34–45.

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 Proceedings of the 17th IEEE Symposium on Reliable Distributed Systems, 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. (2022). HyperPaxos / LibHyperPaxos GitLab. https://gitlab.c3sl.ufpr.br/hyperpaxos/libhyperpaxos.

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. 41o Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuídos (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álise 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. (2018). A distributed k-mutual exclusion algorithm based on autonomic spanning trees. JPDC, 115:41–55.