article

Free access

Fast causal multicast

Authors:

Pat Stephenson,

Kenneth BirmanAuthors Info & Claims

ACM SIGOPS Operating Systems Review, Volume 25, Issue 2

Pages 75 - 79

https://doi.org/10.1145/122120.122127

Published: 01 April 1991 Publication History

PDF eReader

Abstract

We begin by outlining a new protocol that efficiently implements a reliable, causally ordered multicast primitive and is easily extended into a totally ordered one. Since measurements show that the dominant cost of this protocol is message transport, the design of a lower level multicast transport protocol is discussed. The overall scheme scales with bounded overhead. Our first conclusion is that systems such as Isis can achieve performance competitive with the best existing multicast facilities - a finding contradicting the widespread concern that fault-tolerance may be unacceptably costly. Our second conclusion is that the paradigm of multicast transport is extremely useful for constructing fault-tolerant applications. Our final conclusion is that the framework for fault-tolerant programming provided by Isis is very useful in the design and construction of these extensions to the basic system.

References

[1]

[AHL89] M. Stella Atkins, Garnik Haftevani, and Wo Shun Luk. An efficient kernel-level dependable multicast protocol for distributed systems. In Proceedings of the Eighth Symposium on Reliable Distributed Systems, pages 94-101. IEEE, 1989.

Crossref

Google Scholar

[2]

[BJ87] Kenneth P. Birman and Thomas A. Joseph. Exploiting virtual synchrony in distributed systems. In Proceedings of the Eleventh ACM Symposium on Operating Systems Principles, pages 123- 138, Austin, Texas, November 1987. ACM SIGOPS.

Digital Library

Google Scholar

[3]

[BSS90] Ken Birman, Andre Schiper, and Pat Stephenson. Fast causal multicast. Technical Report TR90-1105, Cornell University Computer Science Department, Ithaca, NY, April 1990. Submitted to ACM Transactions on Computer Systems.

Digital Library

Google Scholar

[4]

[CM84] J. Chang and N. Maxemchuk. Reliable broadcast protocols. ACM Transactions on Computer Systems, 2(3):251-273, August 1984.

Digital Library

Google Scholar

[5]

[Dan89] Peter Danzig. Finite buffers and fast multicast. In Proceedings of the ACM Conference on Measurement and Modelling of Computer Systems, Berkeley, California, 1989. ACM SIGMETRICS.

Digital Library

Google Scholar

[6]

[Dee88] S. Deering. Multicast routine in internetworks and extended lans. In Proceedings of the Symposium on Communications Architectures & Protocols, pages 55-64, Stanford, California, August 1988. ACM SIGCOMM.

Digital Library

Google Scholar

[7]

[KTH89] M. Frans Kaashoek, Andrew S. Tanenbaum, Susan Flynn Hummel, and Henri E. Bal. An efficient reliable broadcast protocol. Operating Systems Review, 23(4):5-19, October 1989.

Digital Library

Google Scholar

[8]

[Lam78] Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7):558- 565, July 1978.

Digital Library

Google Scholar

[9]

[LL86] Barbara Liskov and Rivka Ladin. Highly-available distributed services and fault-tolerant distributed garbage collection. In Proceedings of the Fifth ACM Symposium on Principles of Distributed Computing, pages 29-39, Calgary, Alberta, August 1986. ACM SIGOPS-SIGACT.

Digital Library

Google Scholar

[10]

[PBS89] Larry L. Peterson, Nick C. Bucholz, and Richard Schlichting. Preserving and using context information in interprocess communication. ACM Transactions on Computer Syslems, 7(3):217-246, August 1989.

Digital Library

Google Scholar

[11]

[SES89] A. Schiper, J. Eggli, and A Sandoz. A new algorithm to implement causal ordering. In Proceedings of the 3rd International Workshop on Distributed Algorithms, Lecture Notes on Computer Science 392, pages 219-232. Springer-Verlag, 1989.

Digital Library

Google Scholar

[12]

[Ste91] Pat Stephenson. Fast Causal Multicast. PhD thesis, Cornell University, January 1991. To appear.

Google Scholar

Cited By

View all

Meiklejohn C(2017)A Certain Tendency Of The Database CommunityCompanion Proceedings of the 1st International Conference on the Art, Science, and Engineering of Programming10.1145/3079368.3079414(1-5)Online publication date: 3-Apr-2017
https://dl.acm.org/doi/10.1145/3079368.3079414
Agha GCallsen C(1993)ActorSpace: an open distributed programming paradigmACM SIGPLAN Notices10.1145/173284.15533528:7(23-32)Online publication date: 1-Jul-1993
https://dl.acm.org/doi/10.1145/173284.155335
Agha GCallsen CChen MHalstead R(1993)ActorSpace: an open distributed programming paradigmProceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming10.1145/155332.155335(23-32)Online publication date: 1-Aug-1993
https://dl.acm.org/doi/10.1145/155332.155335
Show More Cited By

Index Terms

Fast causal multicast
1. Networks
  1. Network protocols
2. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems

Recommendations

Fast causal multicast
EW 4: Proceedings of the 4th workshop on ACM SIGOPS European workshop

We begin by outlining a new protocol that efficiently implements a reliable, causally ordered multicast primitive and is easily extended into a totally ordered one. Since measurements show that the dominant cost of this protocol is message transport, ...
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 ...
Configurable active multicast congestion control

A multicast congestion control and avoidance scheme is indispensable for group-based applications to fairly share and efficiently use network resources with unicast applications and maintain the stability of the Internet. It is difficult for the ...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGOPS Operating Systems Review

ACM SIGOPS Operating Systems Review Volume 25, Issue 2

April 1991

139 pages

ISSN:0163-5980

DOI:10.1145/122120

Editor:
Roy Levin
Digital Equipment Corp., Palo Alto, CA

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1991

Published in SIGOPS Volume 25, Issue 2

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
274
Total Downloads

Downloads (Last 12 months)65
Downloads (Last 6 weeks)9

Reflects downloads up to 14 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Meiklejohn C(2017)A Certain Tendency Of The Database CommunityCompanion Proceedings of the 1st International Conference on the Art, Science, and Engineering of Programming10.1145/3079368.3079414(1-5)Online publication date: 3-Apr-2017
https://dl.acm.org/doi/10.1145/3079368.3079414
Agha GCallsen C(1993)ActorSpace: an open distributed programming paradigmACM SIGPLAN Notices10.1145/173284.15533528:7(23-32)Online publication date: 1-Jul-1993
https://dl.acm.org/doi/10.1145/173284.155335
Agha GCallsen CChen MHalstead R(1993)ActorSpace: an open distributed programming paradigmProceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming10.1145/155332.155335(23-32)Online publication date: 1-Aug-1993
https://dl.acm.org/doi/10.1145/155332.155335
Wills C(1991)Strategies for using multicasting to locate resources[1991] Proceedings 16th Conference on Local Computer Networks10.1109/LCN.1991.208112(589-598)Online publication date: 1991
https://doi.org/10.1109/LCN.1991.208112

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

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

Abstract

References

Cited By

Index Terms

Recommendations