The power of logical clock abstractions.

*(English)*Zbl 1448.68129Summary: Vector and matrix clocks are extensively used in asynchronous distributed systems. This paper asks, “how does the clock abstraction generalize?” To address this problem, the paper motivates and proposes logical clocks of arbitrary dimensions. It then identifies and explores the conceptual link between such clocks and knowledge. It establishes the necessary and sufficient conditions on the size and dimension of clocks required to attain any specified level of knowledge about the timestamp of the most recent system state for which this is possible without using any messages in the clock protocol. The paper then gives algorithms to determine the timestamp of the latest system state about which a specified level of knowledge is attainable in a given system state, and to compute the timestamp of the earliest system state in which a specified level of knowledge about a given system state is attainable. The results are applicable to applications that deal with a certain class of properties, identified as monotonic properties.

##### MSC:

68M14 | Distributed systems |

68Q85 | Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) |

PDF
BibTeX
XML
Cite

\textit{A. D. Kshemkalyani}, Distrib. Comput. 17, No. 2, 131--150 (2004; Zbl 1448.68129)

Full Text:
DOI

##### References:

[1] | Bogart KP: Introductory combinatorics. Pitman Publishing, 1983 · Zbl 0545.05001 |

[2] | Chandy KM, Misra J: How processes learn. Distributed Computing 1(1): 40-52 (1986) · Zbl 0602.68026 |

[3] | Chandy KM, Lamport L: Distributed snapshots: Determining global states of distributed systems. ACM Transactions on Computer Systems 3(1): 63-75 (1985) |

[4] | Charron-Bost B: Concerning the size of clocks in distributed systems. Information Processing Letters 39(1): 11-16 (1991) · Zbl 0735.68003 |

[5] | Critchlow C, Taylor K: The inhibition spectrum and the achievement of causal consistency. Distributed Computing 10(1): 11-27 (1996) |

[6] | Fagin R, Halpern J, Moses Y, Vardi M: Reasoning about knowledge. MIT Press, 1995 · Zbl 0839.68095 |

[7] | Fidge CJ: Timestamps in message-passing systems that preserve partial ordering. Australian Computer Science Communications 10(1): 56-66 (1988) |

[8] | Fidge CJ: Logical time in distributed computing systems. IEEE Computer 24(8): 28-33 (1991) |

[9] | Halpern J, Fagin R: Modeling knowledge and action in distributed systems. Distributed Computing 3(4): 159-179 (1989) · Zbl 0685.68076 |

[10] | Halpern J, Moses Y: Knowledge and common knowledge in a distributed environment. Journal of the ACM 37(3): 549-587 (1990) · Zbl 0699.68115 |

[11] | Holliday J, Agrawal D, El-Abbadi A: Disconnection modes for mobile databases. Wireless Networks 8(4): 391-402 (2002) · Zbl 1030.68698 |

[12] | Krishnakumar A, Bernstein A: Bounded ignorance: A technique for increasing concurrency in a replicated system. ACM Transactions on Database Systems 19(4): 586-625 (1994) |

[13] | Kshemkalyani AD: On continuously attaining levels of concurrent knowledge without control messages. Technical Report UIC-EECS-98-6, University of Illinois at Chicago, 1998 |

[14] | Kshemkalyani AD: Concurrent knowledge and logical clock abstractions. In: Kapoor S, Prasad S (eds) Proc. 20th Conference on Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science 1974, Springer, Berlin Heidelberg New York 2000, pp 489-502 |

[15] | Lamport L: Time, clocks, and the ordering of events in a distributed system. Communications of the ACM 21(7): 558-565 (1978) · Zbl 0378.68027 |

[16] | Mattern F: Virtual time and global states of distributed systems. In: Cosnard M et al. (eds) Proc. Workshop on Parallel and Distributed Algorithms. North-Holland, Elsevier, 1989, pp 215-226 |

[17] | Meldal S, Sankar S, Vera J: Exploiting locality in maintaining potential causality. Proc. 10th ACM Symposium on Principles of Distributed Computing, 1991, pp 231-239 · Zbl 1314.68383 |

[18] | Panangaden P, Taylor K: Concurrent common knowledge: Defining agreement for asynchronous systems. Distributed Computing 6(2): 73-94 (1992) · Zbl 0773.68009 |

[19] | Ruget F: Cheaper matrix clocks. In: Tel G, Vitanyi P (eds) Proc. 8th Workshop on Distributed Algorithms, Lecture Notes in Computer Science 857, Springer, Berlin Heidelberg New York 1994, pp 355-369 |

[20] | Sarin S, Lynch N: Discarding obsolete information in a distributed database system. IEEE Transactions on Software Engineering 13(1): 39-46 (1987) |

[21] | Schwarz R, Mattern F: Detecting causal relationships in distributed computations: In search of the holy grail, Distributed Computing 7(3): 149-174 (1994) · Zbl 0813.68096 |

[22] | Singhal M. Kshemkalyani A: Efficient implementation of vector clocks. Information Processing Letters 43(1): 47-52 (1992) · Zbl 0780.68050 |

[23] | Torres-Rojas FJ, Ahamad M: Plausible clocks: Constant size logical clocks for distributed systems. Distributed Computing 12(4): 179-195 (1999) |

[24] | Wuu G, |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.