A large number of tasks in distributed systems are based on the fundamental problem of tracing the causal dependencies among the events that characterize a run of the computation. This problem is commonly solved by appliance of vector clocks as a means of capturing the flow of information 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.
展开▼
