Determining order relationship between events in distributed computations is a fundamental problem with applications in distributed monitoring systems and faulttolerance. Fidge and Mattern’s vector clocks capture the order relationship with vectors of size in a system with processes. Since many distributed applications use synchronous messages, it is natural to ask if the overhead can be reduced for these applications. In this paper, we present a new method of timestamping messages and events in synchronous computations that capture the order relationship with vectors of size less than or equal to the size of the vertex cover of the communication topology of the system. Our method is fundamentally different from that of Fidge and Mattern’s technique. The timestamps in our method do not use one component per process but still guarantee that the order relationship is captured accurately. Our algorithm is online and only requires piggybacking of timestamps on program messages. It is applicable to all programs that either use programming languages which use synchronous communication such as CSP, or use synchronous remote procedure calls.

In this paper, we show the connection between vector clocks used in distributed computing and dimension theory of partially ordered sets. Based on this connection, we provide lower bounds on the number of coordinates for timestamping events in a distributed computation for capturing the happened- before relation. To this end, we introduce the notion of a string realizer and the string dimension of a poset. For distributed computing and other applications, the concept of string realizer is more natural than the chain realizer used in the classical dimension theory. We establish the relationship between the string dimension and the chain dimension of a poset. Using this relationship and Dilworth's theorem for the chain dimension of finite distributive lattices, we obtain the desired lower bound. The concept of strings also has applications in efficient encoding of partial orders because it requires fewer bits to encode a string realizer than a chain realizer.