Implement Vector Clock Increment and Merge

Vector Clocks and Logical Time

Physical clocks on different machines drift and cannot be trusted for ordering distributed events. Two servers may disagree by milliseconds or more, making it impossible to determine which of two writes arrived "first." Vector clocks solve this with logical time: a mathematical structure that captures causality precisely, without relying on wall-clock synchronisation.

Structure

A vector clock for a system with N nodes is a map from node identifiers to integer counters, initialised to zero:

VC = {A: 0, B: 0, C: 0}

Each node maintains its own copy of this entire vector. The three rules are:

1. Local event (a write): increment only your own counter. No other component changes.
2. Sending a message: attach your current vector clock to the message so the receiver can learn your causal history.
3. Receiving a message: take the component-wise maximum of your clock and the received clock (the merge), then increment your own counter to record this receive event.

Why Component-Wise Max?

When node B receives a message from node A, A's clock encodes everything A knew at the time of sending — including things A learned from other nodes. Taking the max of each component ensures B's clock now reflects all events that causally precede this message:

A sends: {A:3, B:1, C:0}
B has:   {A:1, B:2, C:0}
merge:   {A:3, B:2, C:0}   # component-wise max
B ticks: {A:3, B:3, C:0}   # B increments own counter

Lamport Clocks vs Vector Clocks

Property	Lamport Clock	Vector Clock
Structure	Single integer per node	N integers (one per node)
Causality detection	Partial: if A→B then ts(A) < ts(B), but not vice versa	Full bidirectional: A→B iff VC(A) < VC(B)
Concurrency detection	No — cannot distinguish concurrent from causal	Yes — CONCURRENT when neither dominates
Storage overhead	O(1) per value	O(N) per value

Dynamo uses vector clocks because it needs to detect genuine write conflicts — two writes where neither was aware of the other. Lamport clocks cannot do this. When Dynamo finds two versions where neither clock dominates (CONCURRENT), it stores both versions and returns them both to the next reader, who must resolve the conflict.

Why It Matters in Dynamo

Every PUT operation in Dynamo attaches a vector clock to the stored value. When a GET returns multiple versions (because different replicas diverged), the client sees all conflicting versions and their clocks. The application can then merge them — for example, a shopping cart application takes the union of all cart versions to ensure no item is ever silently lost.

Common Pitfalls

• Tick after merge, not before: the receive event is recorded by incrementing your own counter after the merge, not before. Incrementing before the merge would claim you "knew about" the incoming message before it arrived.
• Missing nodes in the clock: when comparing two clocks, treat missing node entries as zero. A clock that predates a node's existence should not fail comparison.
• SEND is a receive event for the recipient: in the simulator, SEND from A to B means B receives — B merges A's current clock, then increments its own counter.