A Caminho de Uma Alternativa Hierárquica para Implementação do Algoritmo de Consenso Paxos
Resumo
O Paxos está entre os mais importantes algoritmos de consenso, que permite que um conjunto de processos chegue em um acordo sobre um determinado valor proposto. Este trabalho propõe uma implementação hierárquica de uma instância do Paxos, na qual n processos acceptors estão organizados em uma topologia virtual denominada VCube. Um processo proposer se comunica utilizando um algoritmo de difusão sobre o VCube, para conseguir a maioria de votos para a decisão. As mensagens são propagadas de forma autonômica no VCube, que é escalável por definição, apresentando diversas propriedades logarítmicas, inclusive quando há processos falhos. Assume-se um sistema parcialmente síncrono com falhas de processos por parada, garantindo a segurança (safety), e a progressão (liveness), esta em condições de sincronia fraca. Resultados de simulação incluem uma comparação com o Ring Paxos, uma implementação do Paxos sobre uma rede de sobreposição virtual em anel.
Referências
Chandra, T. D. and Toueg, S. (1996). Unreliable failure detectors for reliable distributedsystems. J. ACM, 43(2):225-267.
Duarte, E. P., Bona, L. C. E., and Ruoso, V. K. (2014). Vcube: A provably scalabledistributed diagnosis algorithm. In 2014 5th Workshop on Latest Advances in ScalableAlgorithms for Large-Scale Systems, pages 17-22.
Fischer, M. J., Lynch, N. A., and Paterson, M. S. (1985). Impossibility of distributedconsensus with one faulty process. Journal of the ACM, 32(2):374-382.
Jalili Marandi, P., Primi, M., Schiper, N., and Pedone, F. (2017). Ring Paxos: High-Throughput Atomic Broadcast. The Computer Journal, 60(6):866-882.
Jeanneau, D., Rodrigues, L. A., Arantes, L., and Jr., E. P. D. (2017). An autonomic hierarchical reliable broadcast protocol for asynchronous distributed systems with failuredetection. J. Braz. Comp. Soc., 23(1):15:1-15:14.
Lamport (2001). Paxos made simple. SIGACTN: SIGACT News (ACM Special InterestGroup on Automata and Computability Theory), 32.
Lamport, L. (1998). The part-time parliament. ACM Trans. Comput. Syst., 16(2):133-169.
Lamport, L. (2006a). Fast paxos. Distributed Computing, 19(2):79-103.
Lamport, L. (2006b). Lower bounds for asynchronous consensus. Distributed Computing,19(2):104-125.
MacDougall, M. H. (1987). Simulating Computer Systems: Techniques and Tools. MITPress, Cambridge, MA, USA.
Moraru, I., Andersen, D. G., and Kaminsky, M. (2013). There is more consensus in ega-litarian parliaments. In Proceedings of the Twenty-Fourth ACM Symposium on Opera-ting Systems Principles, SOSP "13, pages 358-372, New York, NY, USA. ACM.
Parisa Jalili Marandi, Primi, M., Schiper, N., and Pedone, F. (2010). Ring paxos: A high-throughput atomic broadcast protocol. In 2010 IEEE/IFIP International Conferenceon Dependable Systems Networks (DSN), pages 527-536.
Rodrigues, L. A., Duarte Jr, E. P., and Arantes, L. (2014). Árvores geradoras mínimasdistribuídas e autonômicas. In Anais do 32º Simpósio Brasileiro de Redes de Compu-tadores e Sistemas Distribuídos — SBRC 2014, pages 1-14.
