View Related Documents

Abstract

Vector and matrix clocks are extensively used in asynchronous distributed systems. This paper asks, ldquohow does the clock abstraction generalize?rdquo 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.

Keywords:  Causality - Clocks - Concurrency - Distributed system - Knowledge - Logical time - Time

Received: 15 March 2002, Accepted: 15 January 2004, Published online: 9 June 2004
This material is based on work supported by the National Science Foundation under Grant No. 9875617. A conference version appeared in [14] and the full technical report is in [13].

Fulltext Preview

Image of the first page of the fulltext document