Tree Clocks: An Efficient and Entirely Dynamic Logical Time System

T. Landes (Germany)


distributed systems, logical time, dynamic, vector clocks


A large number of tasks in distributed systems are based on the fundamental problem of tracing the causal dependen cies among the events that characterize a run of the compu tation. This problem is commonly solved by appliance of vector clocks as a means of capturing the flow of informa tion within and among distributed processes. In the paper at hand a new kind of logical clock concept is presented and examined that is meant to overcome the vector clocks’ great drawback: that the number of processes in the distributed system has to be constant and known in advance. Tree clocks are designed to naturally and efficiently scale with the dynamic creation and termination of processes without losing their primary functionality, such as causality tracing, event ordering, and gap detection. In most aspects, they even are more efficient than vector clocks.

Important Links:

Go Back