CAUSALITY AND ATOMICITY IN DISTRIBUTED COMPUTATIONS

In a distributed system, high-level actions can be modeled by nonatomi c events. This paper proposes causality relations between distributed nonatomic events and provides efficient testing conditions for the rel ations. The relations provide a fine-grained granularity to specify ca usality relations between distributed nonatomic events. The set of rel ations between nonatomic events is complete in first-order predicate l ogic, using only the causality relation between atomic events, for a p air of distributed nonatomic events X and Y, the evaluation of any of the causality relations requires \Nx\ x \N-Y(\) integer comparisons, w here \N-X\ and \N-Y\, respectively, are the number of nodes on which t he two nonatomic events X and Y occur. In this paper: we show that thi s polynomial complexity of evaluation can by simplified to a linear co mplexity using properties of partial orders. Specifically, we show tha t most relations can be evaluated in min(\N-X\, \N-Y\) integer compari sons, some in \N-X\ integer comparisons, and the others in \N-Y\ integ er comparisons. During the derivation of the efficient testing conditi ons, we also define special system execution prefixes associated with distributed nonatomic events and examine their knowledge-theoretic sig nificance.