article

Free access

Bimodal multicast

Authors:

Kenneth P. Birman,

Yaron MinskyAuthors Info & Claims

ACM Transactions on Computer Systems (TOCS), Volume 17, Issue 2

Pages 41 - 88

https://doi.org/10.1145/312203.312207

Published: 01 May 1999 Publication History

Abstract

There are many methods for making a multicast protocol “reliable.” At one end of the spectrum, a reliable multicast protocol might offer tomicity guarantees, such as all-or-nothing delivery, delivery ordering, and perhaps additional properties such as virtually synchronous addressing. At the other are protocols that use local repair to overcome transient packet loss in the network, offering “best effort” reliability. Yet none of this prior work has treated stability of multicast delivery as a basic reliability property, such as might be needed in an internet radio, television, or conferencing application. This article looks at reliability with a new goal: development of a multicast protocol which is reliable in a sense that can be rigorously quantified and includes throughput stability guarantees. We characterize this new protocol as a “bimodal multicast” in reference to its reliability model, which corresponds to a family of bimodal probability distributions. Here, we introduce the protocol, provide a theoretical analysis of its behavior, review experimental results, and discuss some candidate applications. These confirm that bimodal multicast is reliable, scalable, and that the protocol provides remarkably stable delivery throughput.

References

[1]

BAILEY, N. 1975. The Mathematical Theory of Infectious Diseases. 2nd edition Charles Griffen and Company, London, England, United Kingdom.]]

[2]

BAJAJ, S., BRESLAU, L., ESTRIN, D., FALL, K., FLOYD, S., HALDAR, P., HANDLEY, M., HELMY, A., HEIDEMANN, J., HUANG, P., KUMAR, S., MCCANNE, S., REJAIE, R., SHARMA, P., VARADHAN, K., Xu, Y., Yu, H., AND ZAPPALA, D. 1999. Improving simulation for network research. Tech. Rep. 99-702. Computer Science Department, University of Southern California, Los Angeles, CA.]]

[3]

BALDONI, R., MOSTEFAOUI, A., AND RAYNAL, M. 1996a. Casual delivery of messages with real-time data in unreliable networks. Real-Time Syst. 10, 3, 245-262.]]

Digital Library

[4]

BALDONI, R., PRAKASH, R., RAYNAL, M., AND SINGHAL, M. 1996b. Broadcast with time and causality constraints for multimedia applications. INRIA, Rennes, France.]]

[5]

BIRMAN, K. 1994. A response to Cheriton and Skeen's criticism of causal and totally ordered communication. ACM SIGOPS Oper. Syst. Rev. 28, 1 (Jan. 1994), 11-21.]]

Digital Library

[6]

BIRMAN, K. P. 1997. Building Secure and Reliable Network Applications. Manning Publications Co., Greenwich, CT. http://www.browsebooks.com/Birman/index.html.]]

Digital Library

[7]

BIRMAN, K. P. 1999. A review of experiences with reliable multicast. Softw. Pract. Exper. 29, 9.]]

[8]

BIRMAN, K., FRIEDMAN, R., HAYDEN, M., AND RHEE, I. 1998. Middleware support for distributed multimedia and collaborative computing. In Proceedings of ACM Multimedia and Networking (MMCN '98, San Jose, CA). ACM, New York, NY.]]

[9]

CHERITON, D. R. AND SKEEN, D. 1993. Understanding the limitations of causally and totally ordered communication. ACM SIGOPS Oper. Syst. Rev. 27, 5 (Dec. 1993), 44-57.]]

Digital Library

[10]

COOPER, R. 1994. Experience with causally and totally ordered communication support: A cautionary tale. ACM SIGOPS Oper. Syst. Rev. 28, 1 (Jan. 1994), 28-31.]]

Digital Library

[11]

CRISTIAN, F., AGHILI, H., STRONG, R., AND DOLEV, D. 1985. Atomic broadcast: From simple message diffusion to Byzantine agreement. In Proceedings of the 15th IEEE International Symposium on Fault-Tolerant Computing (FTCS '85, Ann Arbor, MI, June). IEEE Press, Piscataway, NJ, 200-206.]]

[12]

CRISTIAN, F., DOLEV, D., STRONG, R., AND AGHILI, H. 1990. Atomic broadcast in a real-time environment. In Fault-Tolerant Distributed Computing, B. Simons and A. Spector, Eds. Springer lecutre notes in computer science. Springer-Verlag, Berlin, Germany, 51-71.]]

Digital Library

[13]

DEMERS, A., GREENE, D., HAUSER, C., IRISH, W., AND LARSON, J. 1987. Epidemic algorithms for replicated database maintenance. In Proceedings of the 6th Annual ACM Symposium on Principles of Distributed Computing (PODC '87, Vancouver, BC, Aug. 10-12), F. B. Schneider, Ed. ACM Press, New York, NY, 1-12.]]

Digital Library

[14]

FEIGE, U., PELEG, D., RAGHAVAN, P., AND UPFAL, E. 1990. Rndomized broadcast in networks. Random Struct. Alg. 1, 4, 447-460.]]

[15]

FLOYD, S., JACOBSON, V., MCCANNE, S., LIU, C.-G., AND ZHANG, L. 1995. A reliable multicast framework for light-weight sessions and application level framing. SIGCOMM Comput. Commun. Rev. 25, 4 (Oct.), 342-356. For more information see http://www.aciri.org/floyd/ srm.html.]]

Digital Library

[16]

GOLDING, R. AND TAYLOR, K. 1992. Group membership in the epidemic style. Tech. Rep. UCSC-CRL-92-13. Computer and Information Sciences Department, University of California at Santa Cruz, Santa Cruz, CA.]]

Digital Library

[17]

Guo, K. 1998. Scalable membership detection protocols. Ph.D. Dissertation. Department of Computer Science, Cornell University, Ithaca, NY. Available as Tech. Rep. 98-1684.]]

Digital Library

[18]

HAYDEN, M. 1998. The Ensemble system. Ph.D. Dissertation. Department of Computer Science, Cornell University, Ithaca, NY. Available as Tech. Rep. TR 98-1662.]]

Digital Library

[19]

HAYDEN, M. G. AND BIRMAN, K. P. 1996. Probabilistic broadcast. Tech. Rep. TR 96-1606. Department of Computer Science, Cornell University, Ithaca, NY.]]

Digital Library

[20]

LABOVITZ, C., MALAN, G., AND JAHANIAN, F. 1997. Internet routing instability. In Proceedings of the ACM Conference on Communications, Architecture, and Protocols (SIGCOMM '97, Oct.). ACM Press, New York, NY.]]

Digital Library

[21]

LADIN, R., LISKOV, B., SHRIRA, L., AND GHEMAWAT, S. 1992. Providing high availability using lazy replication. ACM Trans. Comput. Syst. 10, 4 (Nov. 1992), 360-391.]]

Digital Library

[22]

LIDL, K., OSBORNE, J., AND MALCOME, J. 1994. Drinking from the firehose: Multicast USENET news. In Proceedings of USENIX Winter (Jan.). USENIX Assoc., Berkeley, CA, 33-45.]]

Digital Library

[23]

LIN, J. C. AND PAUL, S. 1996. A reliable multicast transport protocol. In Proceedings of the IEEE Conference on Computers and Communication (INFOCOM '96). IEEE Press, Piscataway, NJ, 1414-1424. See also http://www.bell-labs.com/project/rmtp.]]

[24]

LIU, C.-G. 1997. Error recovery in scalable reliable multicast. Ph.D. Dissertation. Computer Science Department, University of Southern California, Los Angeles, CA.]]

Digital Library

[25]

LUCAS, M. 1998. Efficient data distribution in large-scale multicast networks. Ph.D. Dissertation. Department of Computer Science, University of Virginia, Charlottesville, VA.]]

Digital Library

[26]

OZKASAP, O., XIAO, Z., AND BIRMAN, K. P. 1999. Scalability of two reliable multicast protocols. Tech. Rep. TR 99-1748. Department of Computer Science, Cornell University, Ithaca, NY.]]

Digital Library

[27]

PAXSON, V. 1997. End-to-end Internet packet dynamics. In Proceedings of the ACM Conference on Communications, Architecture, and Protocols (SIGCOMM '97, Oct.). ACM Press, New York, NY, 139-154.]]

Digital Library

[28]

PIANTONI, R. AND STANCESCU, C. 1997. Implementing the Swiss Exchange Trading System. In Proceedings of the Conference on Fault Tolerant Computing Systems (FTCS '97, June). IEEE Press, Piscataway, NJ, 309-313.]]

Digital Library

[29]

PAUL, S., SABNANI, K. K., LIN, J. C., AND BHATTACHARYYA, S. 1997. Reliable Multicast Transport Protocol. IEEE J. Sel. Areas Commun. 15, 3 (Apr.).]]

Digital Library

[30]

VAN RENESSE, R. 1994. Why bother with CATOCS?. ACM SIGOPS Oper. Syst. Rev. 28, 1 (Jan. 1994), 22-27.]]

Digital Library

[31]

VAN RENESSE, R., BIRMAN, Z. P., AND MAFFEIS, S. 1996. Horus: a flexible group communication system. Commun. ACM 39, 4, 76-83.]]

Digital Library

[32]

VAN RENESSE, R., MINSKY, Y., AND HAYDEN, M. 1998. Gossip-based failure detection service. In Proceedings of Middleware '98.]]

[33]

XTP FORUM. 1995. Xpress Transfer Protocol specification. XTP Rev. 4.0, 95-20.]]

Cited By

Dou JScheideler CGramoli V(2024)Invited Paper: Blockchains made Lightweight: A Median Rule for State Machine ReplicationProceedings of the 2024 Workshop on Advanced Tools, Programming Languages, and PLatforms for Implementing and Evaluating algorithms for Distributed systems10.1145/3663338.3665452(1-5)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3663338.3665452
Barroso-Fernández CJiménez ELópez-Presa JMoreno-Cuesta MXulvi-Brunet R(2024)Optimizing Gossiping for Asynchronous Fault-Prone IoT Networks With Memory and Battery ConstraintsIEEE Access10.1109/ACCESS.2023.334902112(4701-4715)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2023.3349021
Hu ZGuan SXu WXiao ZShi JLi PDing QDing HZeng C(2023)A Data Flow Framework with High Throughput and Low Latency for Permissioned Blockchains2023 IEEE 43rd International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS57875.2023.00088(1-12)Online publication date: Jul-2023
https://doi.org/10.1109/ICDCS57875.2023.00088
Show More Cited By

Index Terms

Bimodal multicast
1. Networks
  1. Network protocols

Recommendations

Bimodal Multicast
Bimodal Multicast (revised)
Domain Constrained Multicast: A New Approach for IP Multicast Routing

One of major reasons why IP multicast has not been well deployed is the complexity of IP multicast routing. Since existing IP multicast routing protocols have been designed independently of IP unicast routing protocols, a router must maintain routing ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Computer Systems

ACM Transactions on Computer Systems Volume 17, Issue 2

May 1999

112 pages

ISSN:0734-2071

EISSN:1557-7333

DOI:10.1145/312203

Editor:
Kenneth P. Birman
Cornell Univ., Ithaca, NY

Issue’s Table of Contents

Copyright © 1999 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1999

Published in TOCS Volume 17, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

495
Total Citations
View Citations
3,086
Total Downloads

Downloads (Last 12 months)385
Downloads (Last 6 weeks)53

Reflects downloads up to 14 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dou JScheideler CGramoli V(2024)Invited Paper: Blockchains made Lightweight: A Median Rule for State Machine ReplicationProceedings of the 2024 Workshop on Advanced Tools, Programming Languages, and PLatforms for Implementing and Evaluating algorithms for Distributed systems10.1145/3663338.3665452(1-5)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3663338.3665452
Barroso-Fernández CJiménez ELópez-Presa JMoreno-Cuesta MXulvi-Brunet R(2024)Optimizing Gossiping for Asynchronous Fault-Prone IoT Networks With Memory and Battery ConstraintsIEEE Access10.1109/ACCESS.2023.334902112(4701-4715)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2023.3349021
Hu ZGuan SXu WXiao ZShi JLi PDing QDing HZeng C(2023)A Data Flow Framework with High Throughput and Low Latency for Permissioned Blockchains2023 IEEE 43rd International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS57875.2023.00088(1-12)Online publication date: Jul-2023
https://doi.org/10.1109/ICDCS57875.2023.00088
Stokkink QIleri CEpema DPouwelse J(2023)Web3 Sybil avoidance using network latencyComputer Networks10.1016/j.comnet.2023.109701227(109701)Online publication date: May-2023
https://doi.org/10.1016/j.comnet.2023.109701
Gorbunova AGuerraoui RKermarrec AKucherenko APinot R(2022)The Universal Gossip Fighter2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS53621.2022.00116(1162-1172)Online publication date: May-2022
https://doi.org/10.1109/IPDPS53621.2022.00116
Hu ZXiao Z(2022)Dino: A Block Transmission Protocol with Low Bandwidth Consumption and Propagation LatencyIEEE INFOCOM 2022 - IEEE Conference on Computer Communications10.1109/INFOCOM48880.2022.9796837(1319-1328)Online publication date: 2-May-2022
https://dl.acm.org/doi/10.1109/INFOCOM48880.2022.9796837
Tumas VRivera SMagoni DState R(2022)Probabilistic Edge Multicast Routing for the XRP NetworkGLOBECOM 2022 - 2022 IEEE Global Communications Conference10.1109/GLOBECOM48099.2022.10000650(5129-5134)Online publication date: 4-Dec-2022
https://doi.org/10.1109/GLOBECOM48099.2022.10000650
Lebre ANédelec BVan Kempen A(2022)AS-cast: Lock Down the Traffic of Decentralized Content Indexing at the EdgeAlgorithms and Architectures for Parallel Processing10.1007/978-3-031-22677-9_23(433-454)Online publication date: 10-Oct-2022
https://dl.acm.org/doi/10.1007/978-3-031-22677-9_23
Matt CNielsen JThomsen S(2022)Formalizing Delayed Adaptive Corruptions and the Security of Flooding NetworksAdvances in Cryptology – CRYPTO 202210.1007/978-3-031-15979-4_14(400-430)Online publication date: 15-Aug-2022
https://dl.acm.org/doi/10.1007/978-3-031-15979-4_14
Cason DMilosevic NMilosevic ZPedone FZhang KGherbi AVenkatasubramanian NVeiga L(2021)Gossip consensusProceedings of the 22nd International Middleware Conference10.1145/3464298.3493395(198-209)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.1145/3464298.3493395
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents