Daisy Chain Cast - um protocolo para Multicast Atômico
Abstract
Atomic multicast provides delivery and ordering guarantees to subsets of processes and is a fundamental mechanism to provide scalable services with strong consistency. While many genuine atomic multicast algorithms are derived from Skeen’s algorithm, which uses communication from all to all processes, we have on the other side of the spectrum the equally genuine [Delporte-Gallet and Fauconnier 2000] protocol. The second restricts the directionality of communication and is attractive for its simplicity. However, it suffers from the convoy effect. Based on evaluations of both, this article proposes an alternative protocol, with the aim of eliminating the convoy effect of [Delporte-Gallet and Fauconnier 2000].
References
Ahmed-Nacer, T., Sutra, P., and Conan, D. (2016). The convoy effect in atomic mcast. In 2016 IEEE 35th Symposium on Reliable Distributed Systems Workshops, pages 67–72.
Birman, K. P. and Joseph, T. A. (1987). Reliable communication in the presence of failures. ACM Transactions on Computer Systems (TOCS), 5(1):47–76.
Coelho, P., Schiper, N., and Pedone, F. (2017). Fast atomic multicast. In DSN.
Défago, X., Schiper, A., and Urbán, P. (2004). Total order broadcast and multicast algorithms: Taxonomy and survey. ACM Comput. Surv., 36(4).
Delporte-Gallet, C. and Fauconnier, H. (2000). Fault-tolerant genuine atomic multicast to multiple groups. In OPODIS.
Guerraoui, R. and Schiper, A. (2001). Genuine atomic multicast in asynchronous distributed systems. Theoretical Computer Science, 254(1-2):297–316.
Hadzilacos, V. and Toueg, S. (1994). A modular approach to fault-tolerant broadcasts and related problems. Technical report, Cornell University.
Lamport, L. (1978). Time, clocks, and the ordering of events in a distributed system. CACM, 21(7):558–565.
Pacheco, L., Dotti, F., and Pedone, F. (2022). Strengthening atomic multicast for partitioned state machine replication. In Proceedings of the Latin-American Symposium on Dependable Computing (LADC).
Schneider, F. (1990). Implementing fault-tolerant services using the state machine approach: A tutorial. ACM Computing Surveys, 22(4):299–319.
Serlin, O., Sawyer, T., and Gray, J. (1992). Tpc-c is an on-line transaction processing benchmark https://www.tpc.org/tpcc/.
Birman, K. P. and Joseph, T. A. (1987). Reliable communication in the presence of failures. ACM Transactions on Computer Systems (TOCS), 5(1):47–76.
Coelho, P., Schiper, N., and Pedone, F. (2017). Fast atomic multicast. In DSN.
Défago, X., Schiper, A., and Urbán, P. (2004). Total order broadcast and multicast algorithms: Taxonomy and survey. ACM Comput. Surv., 36(4).
Delporte-Gallet, C. and Fauconnier, H. (2000). Fault-tolerant genuine atomic multicast to multiple groups. In OPODIS.
Guerraoui, R. and Schiper, A. (2001). Genuine atomic multicast in asynchronous distributed systems. Theoretical Computer Science, 254(1-2):297–316.
Hadzilacos, V. and Toueg, S. (1994). A modular approach to fault-tolerant broadcasts and related problems. Technical report, Cornell University.
Lamport, L. (1978). Time, clocks, and the ordering of events in a distributed system. CACM, 21(7):558–565.
Pacheco, L., Dotti, F., and Pedone, F. (2022). Strengthening atomic multicast for partitioned state machine replication. In Proceedings of the Latin-American Symposium on Dependable Computing (LADC).
Schneider, F. (1990). Implementing fault-tolerant services using the state machine approach: A tutorial. ACM Computing Surveys, 22(4):299–319.
Serlin, O., Sawyer, T., and Gray, J. (1992). Tpc-c is an on-line transaction processing benchmark https://www.tpc.org/tpcc/.
Published
2023-05-26
How to Cite
LOUZADA, Carlos Renan Schick; DOTTI, Fernando.
Daisy Chain Cast - um protocolo para Multicast Atômico. In: FAULT TOLERANCE WORKSHOP (WTF), 24. , 2023, Brasília/DF.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 66-79.
ISSN 2595-2684.
DOI: https://doi.org/10.5753/wtf.2023.786.
