Causality and atomicity in distributed computations |
| |
Authors: | Ajay D Kshemkalyani |
| |
Affiliation: | (1) Department of Electrical Engineering and Computer Science (MC 154), University of Illinois at Chicago, 851 South Morgan Street, Chicago, IL 60607-7053, USA (e-mail: ajayk@eecs.uic.edu) , US |
| |
Abstract: | Summary. In a distributed system, high-level actions can be modeled by nonatomic events. This paper proposes causality relations between
distributed nonatomic events and provides efficient testing conditions for the relations. The relations provide a fine-grained
granularity to specify causality relations between distributed nonatomic events. The set of relations between nonatomic events
is complete in first-order predicate logic, using only the causality relation between atomic events. For a pair of distributed
nonatomic events X and Y, the evaluation of any of the causality relations requires integer comparisons, where and , respectively, are the number of nodes on which the two nonatomic events X and Y occur. In this paper, we show that this polynomial complexity of evaluation can by simplified to a linear complexity using
properties of partial orders. Specifically, we show that most relations can be evaluated in integer comparisons, some in integer comparisons, and the others in integer comparisons. During the derivation of the efficient testing conditions, we also define special system execution prefixes
associated with distributed nonatomic events and examine their knowledge-theoretic significance.
Received: July 1997 / Accepted: May 1998 |
| |
Keywords: | :Distributed computation – Distributed system – Atomicity – Time – Causality – Synchronization – Global predicates – Concurrency |
本文献已被 SpringerLink 等数据库收录! |
|