Vector Clocks and Detecting Concurrency

One counter per node

A vector clock keeps a counter for every process. Process i increments its own entry on each event, sends the whole vector with messages, and on receipt takes the element-wise maximum before incrementing its own entry. Comparing two vectors gives the full story: V1 happens before V2 if every entry of V1 is less than or equal to the matching entry in V2 (and they differ); if some entries are bigger on each side, the events are concurrent. This is exactly what Lamport clocks cannot tell you. Leaderless stores in the Dynamo style use vector clocks (or related version vectors) to detect conflicting writes and keep both siblings for the application or a merge rule (such as a CRDT) to resolve. The cost is size: vectors grow with the number of writers, which is why systems prune them or bound the participants. Consensus systems avoid this whole problem by agreeing on a single order up front.

Comparing vector clocks

A small comparison function that returns before, after, equal or concurrent.

def compare(v1, v2):
    keys = v1.keys() | v2.keys()
    le = all(v1.get(k, 0) <= v2.get(k, 0) for k in keys)
    ge = all(v1.get(k, 0) >= v2.get(k, 0) for k in keys)
    if le and ge:
        return "equal"
    if le:
        return "before"
    if ge:
        return "after"
    return "concurrent"

print(compare({"A": 1, "B": 0}, {"A": 2, "B": 1}))  # A's write was seen
print(compare({"A": 2, "B": 0}, {"A": 1, "B": 1}))  # neither saw the other
print(compare({"A": 3, "B": 2}, {"A": 1, "B": 2}))

Output:

before
concurrent
after

Lamport vs vector, in one line

Lamport clocks give a cheap total order consistent with causality. Vector clocks cost O(n) per message but can prove that two events are concurrent. Pick vectors only when you must detect conflicts, not merely order events.

त्वरित जाँच: Vectors {A:2, B:0} and {A:1, B:1} are compared. What is the relationship?

• Concurrent
• The first happened before the second
• The second happened before the first
• They are equal