Bernadette Charron-Bost, Friedemann Mattern, and Gerard Tel
Synchronous, Asynchronous, and Causally Ordered Communication. Distributed
Computing, Vol. 9 No. 4, pp. 173 - 191, 1996
Summary
This article studies characterisic properties of synchronous and asynchronous
message communications in distributed systems. Based onthe causality relation
between events in computations with asynchronous communications, we
characterize computations which are realizable with synchronous
communications, which respect causal order, or where messages between two
processes are always received in the order sent. It is shown that the
corresponding computation classes form a strict hierarchy. Furthermore, an
axiomatic definition of distributed computations with synchronous
communications is given, and it is shown that several informal
characterizations of such computations are equivalent when they are formalized
appropriately. As an application, we use our results to show that the
distributed termination detection algorithm by Dijkstra et al. is correct
under a weaker synchrony assumption than originally stated.