Daisy Chain Cast - um protocolo para Multicast Atômico
Resumo
O multicast atômico provê garantias de entrega e ordem a subconjuntos de processos destinatários, sendo um mecanismo fundamental para o provimento de serviços escaláveis com consistência forte. Enquanto muitos algoritmos genuínos de multicast atômico são derivados do algoritmo de Skeen, que usa comunicação de todos para todos processos, temos em outro lado do espectro o protocolo também genuíno de [Delporte-Gallet and Fauconnier 2000]. Este restringe a direcionalidade da comunicação e é atrativo por sua simplicidade. Sofre porém do efeito comboio. A partir de avaliações de ambos, este artigo propõe um protocolo alternativo, com o objetivo de eliminar o efeito comboio de [Delporte-Gallet and Fauconnier 2000].
Referências
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/.
Publicado
26/05/2023
Como Citar
LOUZADA, Carlos Renan Schick; DOTTI, Fernando.
Daisy Chain Cast - um protocolo para Multicast Atômico. In: WORKSHOP DE TESTES E TOLERÂNCIA A FALHAS (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.
