Document Type

Technical Report

Publication Date

1990-10-01

Filename

WUCS-90-38.pdf

DOI:

10.7936/K7SN079V

Technical Report Number

WUCS-90-38

Abstract

We define the logically 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 of multicasts, in which a process sends a message to some arbitrary subset of the processes, including itself. A logically synchronously 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 sends a message, it must eventually be permitted to do so. We present a highly concurrent solution in which each multicast requires at most 4ISI messages, where S is the set of participants in the 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.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7SN079V

Download

Share

COinS