Necessary and sufficient conditions on information for causal message ordering and their optimal implementation |
| |
Authors: | Ajay D Kshemkalyani Mukesh Singhal |
| |
Affiliation: | (1) ECECS Department, P.O. Box 210030, University of Cincinnati, Cincinnati, OH 45221-0030, USA (e-mail: ajayk@ececs.uc.edu) , US;(2) Department of Computer and Information Science, The Ohio State University, 2015 Neil Avenue, Columbus, OH 43210, USA (e-mail: singhal@cis.ohio-state.edu) , US |
| |
Abstract: | Summary. This paper formulates necessary and sufficient conditions on the information required for enforcing causal ordering in a
distributed system with asynchronous communication. The paper then presents an algorithm for enforcing causal message ordering.
The algorithm allows a process to multicast to arbitrary and dynamically changing process groups. We show that the algorithm
is optimal in the space complexity of the overhead of control information in both messages and message logs. The algorithm
achieves optimality by transmitting the bare minimum causal dependency information specified by the necessity conditions,
and using an encoding scheme to represent and transmit this information. We show that, in general, the space complexity of
causal 0message ordering in an asynchronous system is , where is the number of nodes in the system. Although the upper bound on space complexity of the overhead of control information
in the algorithm is , the overhead is likely to be much smaller on the average, and is always the least possible.
Received: January 1996 / Accepted: February 1998 |
| |
Keywords: | :Causal message ordering – Distributed systems – Synchronization – Concurrency |
本文献已被 SpringerLink 等数据库收录! |
|