Synchronous, Asynchronous, and Causally Ordered Communication Distributed
Computing, Vol. 9 No. 4, pp. 173 - 191, 1996
This paper studies characteristic properties of synchronous and asynchronous
message communications in distributed systems. Based on the 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.