Estratégia de Difusão Agressiva para Aumentar a Vazão do Algoritmo de Consenso HyperPaxos
DOI:
https://doi.org/10.22481/recic.v5i1.12949Abstract
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.
Downloads
References
E. Brewer, “Spanner, TrueTime and the CAP Theorem,” Google, Tech. Rep., 2017.
Google, “Replication | Cloud Spanner | Google Cloud,” https://cloud.google.com/spanner/docs/replication, 2023.
J. Ellis, “Lightweight transactions in Cassandra 2.0,” https://www.datastax.com/blog/lightweight-transactions-cassandra-20, 2013.
M. Burrows, “The Chubby lock service for loosely-coupled distributed systems,” in Proceedings of the 7th symposium on Operating systems design and implementation, 2006, pp. 335–350.
Red Hat, “What is etcd?” https://www.redhat.com/en/topics/containers/whatis-etcd, 2019.
L. Lamport, “The Part-Time Parliament,” ACM Transactions on Computer Systems, vol. 16, no. 2, pp. 133–169, 1998. [Online]. Available: https://www.microsoft.com/en-us/research/publication/parttime-parliament/
——, “Paxos made simple,” ACM SIGACT News (Distributed Computing Column) 32, 4 (Whole Number 121, December 2001), pp. 51–58, Dec. 2001.
R. v. Renesse and D. Altinbuken, “Paxos Made Moderately Complex,” ACM Computing Surveys (CSUR), vol. 47, no. 3, pp. 1–36, Feb. 2015. [Online]. Available: https://doi.org/10.1145/2673577
S. Regis and O. M. Mendizabal, “An´alise comparativa do algoritmo Paxos e suas variac¸ ˜oes,” in Anais do XXIII Workshop de Testes e Tolerˆancia a Falhas, May 2022, pp. 71–84. [Online]. Available: https://sol.sbc.org.br/index.php/wtf/article/view/21506
P. Jalili Marandi, M. Primi, N. Schiper, and F. Pedone, “Ring Paxos: High-throughput atomic broadcast,” The Computer Journal, vol. 60, no. 6, pp. 866–882, 2017.
F. M. Kiotheka, D. R. Pereira, E. T. Camargo, and E. P. Duarte Jr, “HyperPaxos: Uma Vers˜ao Hier´arquica do Algoritmo de Consenso Paxos,” 41o Simp´osio Brasileiro de Redes de Computadores e Sistemas Distribu´ıdos (SBRC), pp. 1–14, 2023.
E. P. Duarte Jr, L. C. E. Bona, and V. K. Ruoso, “VCube: A Provably Scalable Distributed Diagnosis Algorithm,” in 2014 5th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems, Nov. 2014, pp. 17–22. [Online]. Available: http://ieeexplore.ieee.org/document/7016729/
M. Primi and D. Sciascia, “LibPaxos: Open-source Paxos,” http://libpaxos.sourceforge.net/, 2013.
S. Benz, “sambenz/URingPaxos: URingPaxos - A high throughput atomic multicast protocol,” https://github.com/sambenz/URingPaxos, 2017.
C. Dwork, N. Lynch, and L. Stockmeyer, “Consensus in the presence of partial synchrony,” Journal of the ACM (JACM), vol. 35, no. 2, pp. 288–323, 1988.
M. Hurfin, A. Mostefaoui, and M. Raynal, “Consensus in asynchronous systems where processes can crash and recover,” in Proceedings of the 17th IEEE Symposium on Reliable Distributed Systems, 1998, pp. 280–286.
C. Cachin, R. Guerraoui, and L. Rodrigues, Introduction to reliable and secure distributed programming, 2nd ed. Springer Science & Business Media, 2011.
E. P. Duarte Jr and T. Nanya, “A hierarchical adaptive distributed system-level diagnosis algorithm,” IEEE Transactions on Computers, vol. 47, no. 1, pp. 34–45, Jan. 1998. [Online]. Available: https://ieeexplore.ieee.org/document/656078/
D. Jeanneau, L. A. Rodrigues, L. Arantes, and E. P. Duarte Jr., “An autonomic hierarchical reliable broadcast protocol for asynchronous distributed systems with failure detection,” Journal of the Brazilian Computer Society, vol. 23, no. 1, p. 15, Dec. 2017. [Online]. Available: https://doi.org/10.1186/s13173-017-0064-9
J. P. de Araujo, L. Arantes, E. P. Duarte Jr, L. A. Rodrigues, and P. Sens, “VCube-PS: A causal broadcast topic-based publish/subscribe system,” Journal of Parallel and Distributed Computing, vol. 125, pp. 18–30, 2019.
L. C. E. Bona, E. P. Duarte Jr, S. L. V. Mello, and K. V. O. Fonseca, “HyperBone: Uma Rede Overlay Baseada em Hipercubo Virtual sobre a Internet,” in XXIV Simp´osio Brasileiro de Redes de Computadores, 2006.
L. A. Rodrigues, E. P. Duarte Jr, and L. Arantes, “A distributed kmutual exclusion algorithm based on autonomic spanning trees,” Journal
of Parallel and Distributed Computing, vol. 115, pp. 41–55, 2018.
F. M. Kiotheka and D. R. Pereira, “HyperPaxos / LibHyperPaxos - GitLab,” https://gitlab.c3sl.ufpr.br/hyperpaxos/libhyperpaxos, 2022.
L. Lamport, “Generalized Consensus and Paxos,” Mar. 2005. [Online]. Available: https://www.microsoft.com/enus/research/publication/generalized-consensus-and-paxos/
I. Moraru, D. G. Andersen, and M. Kaminsky, “There is more consensus in Egalitarian parliaments,” in Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, ser. SOSP ’13. New York, NY, USA: Association for Computing Machinery, Nov. 2013, pp. 358–372. [Online]. Available: https://dl.acm.org/doi/10.1145/2517349.2517350
P. J. Marandi, M. Primi, and F. Pedone, “Multi-Ring Paxos,” in IEEE/IFIP International Conference on Dependable Systems and Networks (DSN 2012), Jun. 2012, pp. 1–12, iSSN: 2158-3927.
A. Charapko, A. Ailijiang, and M. Demirbas, “PigPaxos: Devouring the Communication Bottlenecks in Distributed Consensus,” in Proceedings of the 2021 International Conference on Management of Data, Jun. 2021, pp. 235–247. [Online]. Available: https://dl.acm.org/doi/10.1145/3448016.3452834
E. P. Duarte Jr, A. Weber, and K. V. O. Fonseca, “Distributed Diagnosis of Dynamic Events in Partitionable Arbitrary Topology Networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 8, pp. 1415–1426, Aug. 2012.
E. P. Duarte Jr and A. Weber, “A distributed network connectivity algorithm,” in The 6th International Symposium on Autonomous Decentralized Systems, 2003. ISADS 2003., Apr. 2003, pp. 285–292.
E. P. Duarte Jr and G. d. O. Mattos, “Diagn´ostico em Redes de Topologia Arbitr´aria: Um Algoritmo Baseado em Inundaç˜ao de Mensagens,” in Anais do Workshop de Testes e Tolerˆancia a Falhas (WTF). SBC, Jul. 2000, pp. 82–87, iSSN: 2595-2684. [Online]. Available: https://sol.sbc.org.br/index.php/wtf/article/view/23479
E. P. Duarte Jr and J. M. A. P. Cestari, “O Agente Chinˆes para Diagn´ostico de Redes de Topologia Arbitr´aria,” in Anais do Workshop de Testes e Tolerˆancia a Falhas (WTF). SBC, Jul. 2000, pp. 88–93, iSSN: 2595-2684. [Online]. Available: https://sol.sbc.org.br/index.php/wtf/article/view/23480
R. P. Ziwich and E. P. Duarte Jr, “A Nearly Optimal Comparison-Based Diagnosis Algorithm for Systems of Arbitrary Topology,” IEEE
Transactions on Parallel and Distributed Systems, vol. 27, no. 11, pp. 3131–3143, Nov. 2016.
R. Ziwich, E. Duarte, and L. Albini, “Distributed integrity checking for systems with replicated data,” in 11th International Conference on Parallel and Distributed Systems (ICPADS’05), vol. 1, Jul. 2005, pp. 363–369 Vol. 1, iSSN: 1521-9097.
B. T. Nassu, E. P. Duarte Jr, and A. T. Ramirez Pozo, “A comparison of evolutionary algorithms for system-level diagnosis,” in Proceedings of the 7th annual conference on genetic and evolutionary computation, Jun. 2005, pp. 2053–2060. [Online]. Available: https://doi.org/10.1145/1068009.1068350
E. P. Duarte, A. T. R. Pozo, and B. T. Nassu, “Fault diagnosis of multiprocessor systems based on genetic and estimation of distribution algorithms: a performance evaluation,” International Journal on Artificial Intelligence Tools, vol. 19, no. 01, pp. 1–18, Feb. 2010. [Online]. Available: https://www.worldscientific.com/doi/abs/10.1142/S0218213010000017
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 Journal of Computer Science
This work is licensed under a Creative Commons Attribution 4.0 International License.
