Generic Multicast: One Group Communication Primitive to Rule Them All
DOI:
https://doi.org/10.5753/jisa.2025.5920Keywords:
Consensus, Multicast, Broadcast, Generalized ConsensusAbstract
Group communication primitives have a central role in modern computing infrastructures. They offer a panel of reliability and ordering guarantees for messages, enabling the implementation of complex distributed interactions. In particular, atomic broadcast is a pivotal abstraction for implementing fault-tolerant distributed services. This primitive allows disseminating messages across the system in a total order. There are two group communication primitives closely related to atomic broadcast. Atomic multicast permits targeting a subset of participants, possibly stricter than the whole system. Generic broadcast leverages the semantics of messages to order them only where necessary, that is, when they do not commute at the application level (a conflict). In this paper, we propose to combine all these primitives into a single, more general one, called generic multicast. We formally specify the guarantees offered by generic multicast and present efficient algorithms. Compared to prior works, our solutions offer appealing properties in terms of time and space complexity. In particular, when a run is conflict-free, that is no two messages conflict, a message is delivered after at most three message delays. We explain the logic of of our algorithms, detail their main invariants, and prove them correct. We also present a variation that delivers messages across the system in an order consistent with real-time at the cost of a message delay. This variation is particularly interesting to implement partially-replicated data storage systems
Downloads
References
Ahmed-Nacer, T., Sutra, P., and Conan, D. (2016). The convoy effect in atomic multicast. In 2016 IEEE 35th Symposium on Reliable Distributed Systems Workshops (SRDSW), pages 67-72. IEEE. DOI: 10.1109/SRDSW.2016.22.
Amazon (2008). Aws simple storage service. Available at: [link]. Accessed: 2025-08-18.
Benz, S., Marandi, P. J., Pedone, F., and Garbinato, B. (2014). Building global and scalable systems with atomic multicast. In Proceedings of the 15th International Middleware Conference, Middleware, page 169–180, New York, NY, USA. Association for Computing Machinery. DOI: 10.1145/2663165.2663323.
Bezerra, C. E. B., Pedone, F., and van Renesse, R. (2014). Scalable state-machine replication. In 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN, pages 331-342. IEEE Computer Society. DOI: 10.1109/DSN.2014.41.
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. DOI: 10.1145/7351.7478.
Bolina, J., Sutra, P., Antunes, D., and Camargos, L. (2024). Generic multicast. In Proceedings of the 13th Latin-American Symposium on Dependable and Secure Computing, LADC '24, page 81–90, New York, NY, USA. Association for Computing Machinery. DOI: 10.1145/3697090.3697095.
Camaioni, M., Guerraoui, R., Monti, M., Roman, P., Vidigueira, M., and Voron, G. (2024). Chop chop: Byzantine atomic broadcast to the network limit. In 18th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2024, Santa Clara, CA, USA, July 10-12, 2024, pages 269-287. USENIX Association. DOI: 10.48550/arxiv.2304.07081.
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, New York, NY, USA. Association for Computing Machinery. DOI: 10.1145/1281100.1281103.
Chandra, T. D. and Toueg, S. (1996). Unreliable failure detectors for reliable distributed systems. J. ACM, 43(2):225–267. DOI: 10.1145/226643.226647.
Coelho, P. R., Schiper, N., and Pedone, F. (2017). Fast atomic multicast. In 2017 47th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), pages 37-48. DOI: 10.1109/DSN.2017.15.
Corbett, J. C., Dean, J., Epstein, M., Fikes, A., Frost, C., Furman, J. J., Ghemawat, S., Gubarev, A., Heiser, C., Hochschild, P., Hsieh, W., Kanthak, S., Kogan, E., Li, H., Lloyd, A., Melnik, S., Mwaura, D., Nagle, D., Quinlan, S., Rao, R., Rolig, L., Saito, Y., Szymaniak, M., Taylor, C., Wang, R., and Woodford, D. (2013). Spanner: Google’s globally distributed database. ACM Trans. Comput. Syst., 31(3). DOI: 10.1145/2491245.
Cowling, J. and Liskov, B. (2012). Granola: low-overhead distributed transaction coordination. In Proceedings of the 2012 USENIX Conference on Annual Technical Conference, USENIX ATC'12, page 21, USA. USENIX Association. Available online [link].
Défago, X., Schiper, A., and Urbán, P. (2004). Total order broadcast and multicast algorithms: Taxonomy and survey. ACM Comput. Surv., 36(4):372–421. DOI: 10.1145/1041680.1041682.
Delporte-Gallet, C. and Fauconnier, H. (2000). Fault-tolerant genuine atomic multicast to multiple groups. In Butelle, F., editor, Procedings of the 4th International Conference on Principles of Distributed Systems, OPODIS 2000, Paris, France, December 20-22, 2000, Studia Informatica Universalis, pages 107-122. Suger, rue Catulienne Saint-Denis France. Available at:.
Enes, V., Baquero, C., Gotsman, A., and Sutra, P. (2021). Efficient replication via timestamp stability. In Proceedings of the Sixteenth European Conference on Computer Systems, EuroSys '21, page 178–193, New York, NY, USA. Association for Computing Machinery. DOI: 10.1145/3447786.3456236.
Fritzke, U., Ingels, P., Mostefaoui, A., and Raynal, M. (1998). Fault-tolerant total order multicast to asynchronous groups. In Proceedings Seventeenth IEEE Symposium on Reliable Distributed Systems (Cat. No.98CB36281), pages 228-234. DOI: 10.1109/RELDIS.1998.740503.
Gotsman, A., Lefort, A., and Chockler, G. (2019). White-box atomic multicast. In 2019 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), pages 176-187. DOI: 10.1109/DSN.2019.00030.
Gray, J. (1978). Notes on data base operating systems. In Operating Systems, An Advanced Course, page 393–481, Berlin, Heidelberg. Springer-Verlag. DOI: 10.1007/3-540-08755-9_9.
Guerraoui, R. and Schiper, A. (1997). Genuine atomic multicast. In Distributed Algorithms, 11th International Workshop, WDAG '97, Saarbrücken, Germany, September 24-26, 1997, Proceedings, volume 1320 of Lecture Notes in Computer Science, pages 141-154. Springer. DOI: 10.1007/BFB0030681.
Guerraoui, R. and Schiper, A. (2001). Genuine atomic multicast in asynchronous distributed systems. Theoretical Computer Science, 254(1):297-316. DOI: 10.1016/S0304-3975(99)00161-9.
Hunt, P., Konar, M., Junqueira, F. P., and Reed, B. (2010). Zookeeper: wait-free coordination for internet-scale systems. In Proceedings of the 2010 USENIX Conference on USENIX Annual Technical Conference, USENIXATC'10, page 11, USA. USENIX Association. Available online [link].
Lakshman, A. and Malik, P. (2010). Cassandra: a decentralized structured storage system. 44(2):35-40. DOI: 10.1145/1773912.1773922.
Lamport, L. (2005). Generalized consensus and Paxos. Technical Report MSR-TR-2005-33, Microsoft Research. Available online [link].
Lamport, L. (2006). Lower bounds for asynchronous consensus. Distributed Comput., 19(2):104-125. DOI: 10.1007/S00446-006-0155-X.
Lampson, B. W. and Sturgis, H. E. (1979). Crash recovery in a distributed data storage system. Xerox Palo Alto Research Center Palo Alto, California. Available online [link].
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, page 358–372, New York, NY, USA. Association for Computing Machinery. DOI: 10.1145/2517349.2517350.
Ongaro, D. and Ousterhout, J. (2014). In search of an understandable consensus algorithm. In Proceedings of the 2014 USENIX Conference on USENIX Annual Technical Conference, USENIX ATC'14, page 305–320, USA. USENIX Association. Available online [link].
Pacheco, L., Coelho, P., and Pedone, F. (2023a). Primcast: A latency-efficient atomic multicast. In Proceedings of the 24th International Middleware Conference, Middleware '23, page 124–136, New York, NY, USA. Association for Computing Machinery. DOI: 10.1145/3590140.3629110.
Pacheco, L., Dotti, F., and Pedone, F. (2023b). Strengthening atomic multicast for partitioned state machine replication. In Proceedings of the 11th Latin-American Symposium on Dependable Computing, LADC '22, page 51–60, New York, NY, USA. Association for Computing Machinery. DOI: 10.1145/3569902.3569909.
Park, S. J. and Ousterhout, J. (2019). Exploiting commutativity for practical fast replication. In Proceedings of the 16th USENIX Conference on Networked Systems Design and Implementation, NSDI'19, page 47–64, USA. USENIX Association. Available online [link].
Pedone, F. and Schiper, A. (1999). Generic broadcast. In International Symposium on Distributed Computing (PODC), pages 94-106. Springer. DOI: 10.1007/3-540-48169-9_7.
Pedone, F. and Schiper, A. (2002). Handling message semantics with generic broadcast protocols. Distributed Computing, 15(2):97-107. DOI: 10.1007/s004460100061.
Ryabinin, F., Gotsman, A., and Sutra, P. (2024). Swiftpaxos: fast geo-replicated state machines. In Proceedings of the 21st USENIX Symposium on Networked Systems Design and Implementation, NSDI'24, USA. USENIX Association. Available online [link].
Schiper, N. (2009). On Multicast Primitives in Large Networks and Partial Replication Protocols. PhD thesis. Available online [link].
Schiper, N. and Pedone, F. (2007). Optimal atomic broadcast and multicast algorithms for wide area networks. DOI: 10.1145/1281100.1281185.
Schiper, N., Sutra, P., and Pedone, F. (2009). Genuine versus non-genuine atomic multicast protocols for wide area networks: An empirical study. In 2009 28th IEEE International Symposium on Reliable Distributed Systems (SRDS), pages 166-175. IEEE. DOI: 10.1109/SRDS.2009.12.
Sutra, P. (2022). The weakest failure detector for genuine atomic multicast. In 36th International Symposium on Distributed Computing, DISC 2022, October 25-27, 2022, Augusta, Georgia, USA, volume 246 of LIPIcs, pages 35:1-35:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. DOI: 10.4230/LIPICS.DISC.2022.35.
Sutra, P. and Shapiro, M. (2011). Fast genuine generalized consensus. In 2011 IEEE 30th International Symposium on Reliable Distributed Systems, pages 255-264. DOI: 10.1109/SRDS.2011.38.
The etcd Authors (2014). etcd. Available online [link]. Accessed: 2025-08-18.
Wang, C., Jiang, J., Chen, X., Yi, N., and Cui, H. (2017). Apus: fast and scalable paxos on rdma. In Proceedings of the 2017 Symposium on Cloud Computing, SoCC, page 94–107, New York, NY, USA. Association for Computing Machinery. DOI: 10.1145/3127479.3128609.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Journal of Internet Services and Applications
This work is licensed under a Creative Commons Attribution 4.0 International License.
