Análise comparativa do algoritmo Paxos e suas variações
Abstract
Distributed consensus protocols are fundamental building blocks for developing dependable distributed systems. They help design systems with high availability and strong consistency guarantee, even in the presence of failures in some participants. Paxos is the main consensus algorithm of the last decades, and several variations and optimizations have been presented since the original algorithm was proposed. This paper surveys the main variations and optimizations of the Paxos algorithm, emphasizing the differences, advantages, and disadvantages between the variants and the traditional protocol.
References
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.
Published
2022-05-27
How to Cite
REGIS, Sofia; MENDIZABAL, Odorico M..
Análise comparativa do algoritmo Paxos e suas variações. In: FAULT TOLERANCE WORKSHOP (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.
