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.
Keywords: Causality - Clocks - Concurrency - Distributed system - Knowledge - Logical time - Time
Received: 15 March 2002, Accepted: 15 January 2004, Published online: 9 June 2004This 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].