Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Highly concurrent logically synchronous multicast

  • Published:
Distributed Computing Aims and scope Submit manuscript

Abstract

We define thelogically synchronous multicast problem which imposes a natural and useful structure on message delivery order in an asynchronous system. In this problem, a computation proceeds by a sequence ofmulticasts, in which a process sends a message to some arbitrary subset of the processes, including itself. A logically synchronous multicast protocol must make it appear to every process as if each multicast occurs simultaneously at all participants of that multicast (sender plus receivers). Furthermore, if a process continually wishes to send a message, it must eventually be permitted to do so.

We present a highly concurrent solution in which each multicast requires at most 4|S| messages, whereS is the set of participants in that multicast. The protocol's correctness is shown using a careful problem specification stated in the I/O automaton model. We conclude the paper by describing how the logically synchronous multicast protocol can be used for distributed simulation of algorithms expressed as I/O automata.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles and news from researchers in related subjects, suggested using machine learning.

References

  1. Ada programming language. Tech Rep ANSI/MIL-STD-1815A-1983, Department of Defense

  2. Awerbuch B: Complexity of network synchronization. J ACM 32(4): 804–823 (1985)

    Google Scholar 

  3. Back RJR, Kurki-Suonio R: Distributed cooperation with action systems. ACM Trans Program Lang Syst 10(4): 513–554 (1988)

    Google Scholar 

  4. Bagrodia R: On the design of high performance distributed systems. Ph.D. dissertation, University of Texas, Austin, 1987

    Google Scholar 

  5. Birman KP, Joseph TA: Reliable communication in the presence of failures. ACM Trans Comput Syst 5(1): 47–76 (1987)

    Google Scholar 

  6. Bloom B: Constructing two-writer atomic registers. IEEE Trans Comput (Special Issue on Parallel and Distributed Algorithms) 37(12): 1506–1514 (1988). Also in 6th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, Vancouver, British Columbia, Canada, August 1987, pp 249–259

    Google Scholar 

  7. Buckley GN, Silberschatz A: An effective implementation for the generalized input-output construct of CSP. ACM Trans Program Lang Syst 5(2): 223–235 (1983)

    Google Scholar 

  8. Dolev D, Dwork C, Stockmeyer L: On the minimal synchronism needed for distributed consensus. J ACM 34(1): 77–97 (1987)

    Google Scholar 

  9. Fekete A, Lynch N: The need for headers: an impossibility result for communication over unreliable channels. In Goos G, Hartmanis J (eds) CONCUR'90, Theories of concurrency: unification and extension. (Lect Notes Comput Sci, vol 458) Springer, Berlin Heidelberg New York 1990, pp 199–216

    Google Scholar 

  10. Fekete A, Lynch N, Mansour Y, Spinelli J: The data link layer: the impossibility of implementation in face of crashes. Tech Memo MIT/LCS/TM-355.b, MIT Laboratory for Computer Science, August 1989 (submitted for publication)

  11. Fekete A, Lynch N, Shrira L: A modular proof of correctness for a network synchronizer. In: The 2nd International Workshop on Distributed Algorithms, July 1987: Amsterdam, The Netherlands

  12. Fischer MJ, Lynch NA, Paterson MS: Impossibility of distributed consensus with one faulty process. J ACM 32(2): 374–382 (1985)

    Google Scholar 

  13. Goldman K, Lynch N: Modelling shared state in a shared action model. In: Proceedings of the 5th Annual IEEE Symposium on Logic in Computer Science, June 1990

  14. Goldman KJ: Distributed algorithm simulation using Input/Output automata. Tech Rep MIT/LCS/TR-490, MIT Laboratory for Computer Science, July 1990. Ph.D. Thesis

  15. Goldman KJ, Lynch NA: Quorum consensus in nested transaction systems. In: Proceedings of the 6th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp 27–41, August 1987. A full version is available as MIT Tech Rep MIT/LCS/TR-390

  16. Herlihy M: Impossibility and universality results for wait-free synchronization. In: Proceedings of the 7th ACM SIGACT-SIGOPS Symposium on Prinicples of Distributed Computing, pp 276–290, August 1988

  17. Hoare CAR: Communicating sequential processes, Prentice-Hall, Englewood Cliffs, New Jersey, 1985

    Google Scholar 

  18. Joseph TA, Birman KP: Reliable broadcast protocols. In: Mullender (ed) An advanced course on distributed computing, chap 14. ACM Press, 1989

  19. Lamport L: Time, clocks, and the ordering of events in a distributed system. Commun ACM, 27(7): 558–565 (1978)

    Google Scholar 

  20. Lynch N, Merritt M: Introduction to the theory of nested transactions. In: International Conference on Database Theory, pp 278–305, Rome, Italy, September 1986. Also, expanded version in Tech Rep, MIT/LCS/TR-367, MIT Laboratory for Computer Science, July 1986. Revised version in Theor Comput Sci 62(1988): 123–185

  21. Lynch N, Merritt M, Weihl W, Fekete A: Atomic transactions. (in progress)

  22. Lynch N, Goldman KJ: Distributed algorithms. Tech Rep MIT/LCS/RSS-5, MIT Laboratory for Computer Science, May 1989. MIT Research Seminar Series

  23. Lynch N, Mansour Y, Fekete A: Data link layer: two impossibility results. In: Proceedings of the 7th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp 149–170, August 1988

  24. Lynch NA, Tuttle MR: Hierarchical correctness proofs for distributed algorithms. In: Proceedings of the 6th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp 137–151, August 1987. A full version is available as MIT Tech Rep MIT/LCS/TR-387

  25. Lynch NA Tuttle MR: An introduction to input/output automata. CWI-Quarterly 2(3) (1989)

  26. Misra J: Distributed discrete-event simulation. Comput Surv 1(18): 39–65 (1986)

    Google Scholar 

  27. Modugno F, Merritt M, Tuttle MR: Time constrained automata. Unpublished manuscript, November 1988

  28. Schneider FB: Synchronization in distributed programs. ACM Trans Program Lang Syst 2(4): 179–195 (1982)

    Google Scholar 

  29. Welch J, Lamport L, Lynch N: A lattice-structured proof of a minimum spanning tree algorithm. In: Proceedings of the 7th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp 28–43, August 1988

  30. Welch J, Lynch NA: Synthesis of efficient drinking philosophers algorithms. Tech Rep MIT/LCS/TM-417, MIT, Laboratory for Computer Science, November 1989 (submitted for publication)

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Washington University, 63130, St. Louis, MO, USA

    Kenneth J. Goldman

Authors
  1. Kenneth J. Goldman
    View author publications

    Search author on:PubMed Google Scholar

Additional information

Kenneth J. Goldman received the Sc.B. degree in Computer Science from Brown University in 1984, the S.M. degree in Electrical Engineering and Computer Science from the Massachusetts Institute of Technology in 1987, and the Ph.D. degree in Electrical Engineering and Computer Science from the Massachusetts Institute of Technology in 1990. As part of his doctoral work, he designed and implemented the Spectrum Simulation System, a distributed algorithm development tool based on the I/O automaton model of Lynch and Tuttle. His publications include papers in the areas of models for distributed computing, database concurrency control, human interfaces, and image processing. He is currently Assistant Professor in the Department of Computer Science at Washington University in St. Louis.

A preliminary version of this paper appeared in the Proceedings of the 3rd International Workshop on Distributed Algorithms, Lecture Notes in Computer Science 392, Bermond and Raynal, Eds., Springer-Verlag, Berlin, 1989, pp 94–109.

This research was conducted at the Massachusetts Institute of Technology Laboratory for Computer Science and was supported in part by the National Science Foundation under Grant CCR-86-11442, by the Office of Naval Research under Contract N00014-85-K-0168, by the Defense Advanced Research Projects Agency (DARPA) under Contract N00014-83-K-0125, and by an Office of Naval Research graduate fellowship

Rights and permissions

Reprints and permissions

About this article

Cite this article

Goldman, K.J. Highly concurrent logically synchronous multicast. Distrib Comput 4, 189–207 (1991). https://doi.org/10.1007/BF01784720

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01784720

Key words