Timestamping messages in synchronous computations
Vijay K. Garg, Chakarat Skawratananond · 2003
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.