Accession Number : ADA213747

Title :   Highly Concurrent Logically Synchronous Multicast.

Descriptive Note : Technical rept.,

Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s) : Goldman, Kenneth J.

Report Date : JUL 1989

Pagination or Media Count : 30

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 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, where S is the set of participants is that multicast. The protocol's correctness is shown using a remarkable simple problem specification stated in the input/output automation model. We also show that implementing a wait-free solution to the logically synchronous multicast problem is impossible. Keywords: Distributed computing. (KR)

Descriptors :   *ASYNCHRONOUS COMPUTERS, PROBLEM SOLVING, AUTOMATION, DELIVERY, DISTRIBUTED DATA PROCESSING, INPUT OUTPUT MODELS, MESSAGE PROCESSING, SOLUTIONS(GENERAL), SPECIFICATIONS.

Subject Categories : Computer Systems

Distribution Statement : APPROVED FOR PUBLIC RELEASE