ISSN:
1432-0452
Keywords:
Key words: Distributed computation
;
Message passing
;
Synchronous communication
;
Asynchronous communication
;
Causal order
;
Distributed termination detection
;
Distributed system
;
Causality relation
;
Communication
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Summary. This article 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s004460050018
Permalink
