Causality and atomicity in distributed computations

作     者：Kshemkalyani, AD 

作者机构：Univ Illinois Dept Elect Engn & Comp Sci MC 154 Chicago IL 60680 USA 

出 版 物：《DISTRIBUTED COMPUTING》 (分布式计算)

年 卷 期：1998年第11卷第4期

页      面：169-189页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：distributed computation distributed system atomicity time causality synchronization global predicates concurrency 

摘      要：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 \Nx\ x \N-Y(\) integer comparisons, where \N-X\ and \N-Y\, 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 min(\N-X\, \N-Y\) integer comparisons, some in \N-X\ integer comparisons, and the others in \N-Y\ 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.