Vector Clocks

Vector Clocks

Vector clocks are used to compare distributed events by causal ancestry instead of assuming one global timeline. In a distributed system, it is difficult to maintain a perfectly synchronized physical clock. Vector clocks provide a way to establish a partial ordering of events in the system by tracking causal dependencies.

Worked Example

Consider a system with 3 processes (P₀, P₁, P₂). Each process maintains a vector clock [v0, v1, v2], initially [0, 0, 0].

1. P₀ performs a local event. It increments its own counter: [1, 0, 0].
2. P₀ sends message ‘a’ to P₁. It increments its own counter: [2, 0, 0]. The message carries the timestamp [2, 0, 0].
3. P₁ receives message ‘a’. It takes the component-wise maximum of its current clock [0, 0, 0] and the message's clock [2, 0, 0], giving [2, 0, 0]. Then it increments its own counter: [2, 1, 0].
4. P₁ sends message ‘b’ to P₂. It increments its own counter: [2, 2, 0]. The message carries [2, 2, 0].
5. P₂ receives message ‘b’. It takes the max of [0, 0, 0] and [2, 2, 0], yielding [2, 2, 0]. Then it increments its own counter: [2, 2, 1].

Experiment

Observe the behavior of vector clocks in different scenarios:

1. Select the Chain scenario. Click Finish to reveal all events. Observe that Event 4 (recv a by P₁) happens after Event 2 (send a by P₀) because its vector clock [2, 1, 0] is strictly greater than [2, 0, 0].
2. Select the Concurrent scenario. Click Finish. Compare Event 3 (send a by P₀) and Event 4 (send b by P₁). Their vector clocks are [2, 0, 0] and [0, 2, 0]. Since neither is strictly greater than the other, they are Concurrent.
3. Try the Fork join scenario and use the Step button to see how the vector clocks are updated event by event. Compare Event 1 and Event 6 to see causality.

Launch Experiment

Limitations

This is a simplified logical clock model that illustrates causal boundaries without external real-time verification or network lag simulation.

• Storage Overhead: Vector clocks require O(N) storage per process and message, where N is the number of processes. This can be prohibitive for systems with a large number of dynamic processes.
• No Wall-Clock Time: Vector clocks only capture causality. “Concurrent” events might not happen at the exact same physical time; they simply do not have a causal relationship.

References

You can read more about logical clocks in the primary source provided below.

• Logical Clocks - James Aspnes, Yale University.