HyperPaxos: Uma Versão Hierárquica do Algoritmo de Consenso Paxos

• Fernando M. Kiotheka UFPR
• Djenifer R. Pereira UFPR
• Edson T. Camargo UTFPR
• Elias P. Duarte Jr. UFPR

DOI: https://doi.org/10.5753/sbrc.2023.495

Resumo

O consenso é um problema fundamental de sistemas distribuídos. Neste trabalho é proposto 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. O HyperPaxos organiza os acceptors em clusters e os proposers enviam suas mensagens para um acceptor dito difusor que faz a retransmissão para os demais acceptors usando difusão sobre o vCube. Inicialmente, o difusor envia a mensagem para o seu maior cluster na tentativa de conseguir uma maioria para a fase 1 ou 2. Caso não consiga, continua a difusão para seus próximos clusters, do maior para o menor. 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.

Referências

Benz, S. (2017). sambenz/URingPaxos: URingPaxos A high throughput atomic multicast protocol. https://github.com/sambenz/URingPaxos.

Bona, L. C., Duarte Jr, E. P., Mello, S. L., and Fonseca, K. V. (2006). Hyperbone: Uma rede overlay baseada em hipercubo virtual sobre a internet. XXIV SBRC.

Brewer, E. (2017). Spanner, TrueTime and the CAP Theorem. Technical report, Google.

Burrows, M. (2006). The Chubby lock service for loosely-coupled distributed systems. In 7th USENIX, pages 335-350.

Cachin, C., Guerraoui, R., and Rodrigues, L. (2011). Introduction to reliable and secure distributed programming. Springer Science & Business Media, 2nd edition.

De Araujo, J. P., Arantes, L., Duarte, E. P., Rodrigues, L. A., and Sens, P. (2017). A publish/subscribe system using causal broadcast over dynamically built spanning trees. In 2017 29th SBAC-PAD, pages 161-168. IEEE.

de Araujo, J. P., Arantes, L., Duarte, E. P., Rodrigues, L. A., and Sens, P. (2017). A publish/subscribe system using causal broadcast over dynamically built spanning trees. In 29th SBAC-PAD, pages 161-168.

Duarte, E. P., Rodrigues, L. A., Camargo, E. T., and Turchetti, R. (2022). A Distributed System-level Diagnosis Model for the Implementation of Unreliable Failure Detectors. CoRR, abs/2210.02847.

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.

Ellis, J. (2013). Lightweight transactions in Cassandra 2.0. https://www.datastax.com/blog/lightweight-transactions-cassandra-20.

Google (2023). Replication | Cloud Spanner | Google Cloud. https://cloud.google.com/spanner/docs/replication.

Hurfin, M., Mostefaoui, A., and Raynal, M. (1998). Consensus in asynchronous systems where processes can crash and recover. In 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. (2022). HyperPaxos / LibHyperPaxos GitLab. https://gitlab.c3sl.ufpr.br/hyperpaxos/libhyperpaxos.

Lamport, L. (1978). The implementation of reliable distributed multiprocess systems. Computer Networks (1976), 2(2):95-114.

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., Cohen, J., Arantes, L., and Duarte, E. P. (2013a). A robust permissionbased hierarchical distributed k-mutual exclusion algorithm. In 2013 IEEE 12th International Symposium on Parallel and Distributed Computing, pages 151-158. IEEE.

Rodrigues, L. A., Cohen, J., Arantes, L., and Duarte Jr, E. P. (2013b). A Robust Permission-Based Hierarchical Distributed k-Mutual Exclusion Algorithm. In 12th ISPDC, pages 151-158.

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.

Rodrigues, L. A., Jeanneau, D., Duarte Jr, E. P., and Arantes, L. (2017). Uma Solução de Difusão Confiável Hierárquica em Sistemas Distribuídos Assíncronos. In XXXV SBRC.

Sciascia, D. (2016). sciascid / libpaxos - Bitbucket. https://bitbucket.org/sciascid/libpaxos/.

Terra, A. d. C., Camargo, E. T. d., and Duarte Jr, E. P. (2020). A Caminho de Uma Alternativa Hierárquica para Implementação do Algoritmo de Consenso Paxos. In XXI WTF, pages 15-28.

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 2nd PDSW, pages 35-44.