Highly concurrent logically synchronous multicast

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.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