Análise comparativa do algoritmo Paxos e suas variações
Resumo
Protocolos de consenso distribuído são blocos de construção fundamentais para o desenvolvimento de sistemas distribuídos confiáveis. Eles auxiliam na elaboração de sistemas com alta disponibilidade e garantia de consistência forte, mesmo no caso de falhas em alguns participantes. O Paxos é o principal algoritmo de consenso das últimas décadas com diversas variações e otimizações sendo pesquisadas e desenvolvidas desde que o algoritmo original foi proposto. Este artigo apresenta um levantamento sobre as principais variações e otimizações do algoritmo Paxos, observando diferenças, vantagens e desvantagens entre as variantes e o protocolo tradicional.
Referências
Ailijiang, A., Charapko, A., Demirbas, M., and Kosar, T. (2019). Wpaxos: Wide area network flexible consensus. IEEE Transactions on Parallel and Distributed Systems, 31(1):211-223.
Chandra, T. D., Griesemer, R., and Redstone, J. (2007). Paxos made live: An engineering perspective. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, PODC '07, page 398-407.
Charapko, A., Ailijiang, A., and Demirbas, M. (2021). Pigpaxos: Devouring the communication bottlenecks in distributed consensus. In Proceedings of the 2021 International Conference on Management of Data, pages 235-247.
Dang, H. T., Bressana, P., Wang, H., Lee, K. S., Zilberman, N., Weatherspoon, H., Canini, M., Pedone, F., and Soulé, R. (2020). P4xos: Consensus as a network service. IEEE/ACM Transactions on Networking, 28(4):1726-1738.
Esposito, E. G., Coelho, P., and Pedone, F. (2018). Kernel paxos. In 2018 IEEE 37th Symposium on Reliable Distributed Systems (SRDS), pages 231-240. IEEE.
Fischer, M. J., Lynch, N. A., and Paterson, M. S. (1985). Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM), 32(2):374-382.
Howard, H., Malkhi, D., and Spiegelman, A. (2016). Flexible paxos: Quorum intersection revisited. arXiv preprint arXiv:1608.06696.
Junqueira, F. P., Reed, B. C., and Serafini, M. (2011). Zab: High-performance broadcast for primary-backup systems. In 2011 IEEE/IFIP 41st International Conference on Dependable Systems & Networks (DSN), pages 245-256. IEEE.
Lamport, L. (1998). The part-time parliament. ACM Transactions on Computer Systems, 16(2):133-169.
Lamport, L. (2001). Paxos made simple. SIGACTN: SIGACT News (ACM Special Interest Group on Automata and Computability Theory), 32(4):18-25.
Lamport, L. (2005). Generalized consensus and paxos. Technical Report MSR-TR-2005-33, Microsoft Research.
Lamport, L. (2006). Fast paxos. Distributed Computing, 19(2):79-103.
Lamport, L., Malkhi, D., and Zhou, L. (2009). Vertical paxos and primary-backup replication. In Proceedings of the 28th ACM symposium on Principles of distributed computing, pages 312-313.
Lamport, L. and Massa, M. (2004). Cheap paxos. In International Conference on Dependable Systems and Networks, 2004, pages 307-314. IEEE.
Marandi, P. J., Primi, M., and Pedone, F. (2012). Multi-ring paxos. In DSN.
Marandi, P. J., Primi, M., Schiper, N., and Pedone, F. (2010). Ring paxos: A high-throughput atomic broadcast protocol. In 2010 IEEE/IFIP International Conference on Dependable Systems & Networks (DSN), pages 527-536. IEEE.
Moraru, I., Andersen, D. G., and Kaminsky, M. (2013). There is More Consensus in Egalitarian Parliaments. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, SOSP '13.
Oki, B. and Liskov, B. (1988). Viewstamped Replication: A general primary-copy method to support highly-available distributed systems. In PODC.
Ongaro, D. and Ousterhout, J. (2014). In search of an understandable consensus algorithm. In USENIX ATC 2014.
Pedone, F. and Schiper, A. (1999). Generic broadcast. In Proceedings of the 13th International Symposium on Distributed Computing (DISC'99, formerly WDAG).
Rystsov, D. (2018). CASPaxos: Replicated State Machines without logs. arXiv e-prints, page arXiv:1802.07000.
Schneider, F. B. (1990). Implementing fault-tolerant services using the state machine approach: A tutorial. ACM CSUR 1990.
Chandra, T. D., Griesemer, R., and Redstone, J. (2007). Paxos made live: An engineering perspective. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, PODC '07, page 398-407.
Charapko, A., Ailijiang, A., and Demirbas, M. (2021). Pigpaxos: Devouring the communication bottlenecks in distributed consensus. In Proceedings of the 2021 International Conference on Management of Data, pages 235-247.
Dang, H. T., Bressana, P., Wang, H., Lee, K. S., Zilberman, N., Weatherspoon, H., Canini, M., Pedone, F., and Soulé, R. (2020). P4xos: Consensus as a network service. IEEE/ACM Transactions on Networking, 28(4):1726-1738.
Esposito, E. G., Coelho, P., and Pedone, F. (2018). Kernel paxos. In 2018 IEEE 37th Symposium on Reliable Distributed Systems (SRDS), pages 231-240. IEEE.
Fischer, M. J., Lynch, N. A., and Paterson, M. S. (1985). Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM), 32(2):374-382.
Howard, H., Malkhi, D., and Spiegelman, A. (2016). Flexible paxos: Quorum intersection revisited. arXiv preprint arXiv:1608.06696.
Junqueira, F. P., Reed, B. C., and Serafini, M. (2011). Zab: High-performance broadcast for primary-backup systems. In 2011 IEEE/IFIP 41st International Conference on Dependable Systems & Networks (DSN), pages 245-256. IEEE.
Lamport, L. (1998). The part-time parliament. ACM Transactions on Computer Systems, 16(2):133-169.
Lamport, L. (2001). Paxos made simple. SIGACTN: SIGACT News (ACM Special Interest Group on Automata and Computability Theory), 32(4):18-25.
Lamport, L. (2005). Generalized consensus and paxos. Technical Report MSR-TR-2005-33, Microsoft Research.
Lamport, L. (2006). Fast paxos. Distributed Computing, 19(2):79-103.
Lamport, L., Malkhi, D., and Zhou, L. (2009). Vertical paxos and primary-backup replication. In Proceedings of the 28th ACM symposium on Principles of distributed computing, pages 312-313.
Lamport, L. and Massa, M. (2004). Cheap paxos. In International Conference on Dependable Systems and Networks, 2004, pages 307-314. IEEE.
Marandi, P. J., Primi, M., and Pedone, F. (2012). Multi-ring paxos. In DSN.
Marandi, P. J., Primi, M., Schiper, N., and Pedone, F. (2010). Ring paxos: A high-throughput atomic broadcast protocol. In 2010 IEEE/IFIP International Conference on Dependable Systems & Networks (DSN), pages 527-536. IEEE.
Moraru, I., Andersen, D. G., and Kaminsky, M. (2013). There is More Consensus in Egalitarian Parliaments. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, SOSP '13.
Oki, B. and Liskov, B. (1988). Viewstamped Replication: A general primary-copy method to support highly-available distributed systems. In PODC.
Ongaro, D. and Ousterhout, J. (2014). In search of an understandable consensus algorithm. In USENIX ATC 2014.
Pedone, F. and Schiper, A. (1999). Generic broadcast. In Proceedings of the 13th International Symposium on Distributed Computing (DISC'99, formerly WDAG).
Rystsov, D. (2018). CASPaxos: Replicated State Machines without logs. arXiv e-prints, page arXiv:1802.07000.
Schneider, F. B. (1990). Implementing fault-tolerant services using the state machine approach: A tutorial. ACM CSUR 1990.
Publicado
27/05/2022
Como Citar
REGIS, Sofia; MENDIZABAL, Odorico M..
Análise comparativa do algoritmo Paxos e suas variações. In: WORKSHOP DE TESTES E TOLERÂNCIA A FALHAS (WTF), 23. , 2022, Fortaleza.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 71-84.
ISSN 2595-2684.
DOI: https://doi.org/10.5753/wtf.2022.223461.
