Vector clock synchronization algorithm

Why clock synchronization is necessary

Each machine has its own clock, and clocks drift (about 10⁻⁵ to 10⁻⁶ s/s). Without agreement, events recorded on different machines cannot be ordered correctly. Needed for: ordering of transactions and log entries, distributed mutual exclusion and deadlock detection, replica consistency, authentication tickets with expiry, and debugging. When real time is not important but order is, logical clocks such as vector clocks are used.

Vector clock

A vector clock is a logical clock where each of N processes keeps a vector VCi of N integers. VCi[i] counts local events of Pi, and VCi[j] is the number of events of Pj that Pi knows about. It captures causality exactly.

Algorithm

1. Initially VCi[j] = 0 for all j.
2. For each local event, Pi increments VCi[i] by 1.
3. On sending a message, Pi increments VCi[i] and attaches a copy of VCi as timestamp t.
4. On receiving a message with t, Pi sets VCi[j] = max(VCi[j], t[j]) for all j, then increments VCi[i].

Comparison: V(a) < V(b) if every V(a)[k] ≤ V(b)[k] and at least one is smaller. Then a → b. If neither vector is smaller, the events are concurrent.

Example with three processes

 P1: a(1,0,0) b(2,0,0)               e(3,3,0)
                  \                  ^
 P2: c(0,1,0)      d(2,2,0)--g(2,3,0)-+
 P3: f(0,0,1)

• a, b: events at P1 giving (1,0,0), (2,0,0); b sends m1 with (2,0,0).
• c: local event at P2, (0,1,0).
• d: P2 receives m1: max((0,1,0),(2,0,0)) = (2,1,0), then own entry +1 gives (2,2,0).
• g: P2 sends m2 with (2,3,0).
• e: P1 (at (2,0,0)) receives m2: max = (2,3,0), own entry +1 gives (3,3,0).
• f: local event at P3, (0,0,1).

Observations: b (2,0,0) < d (2,2,0), so b → d. c (0,1,0) and a (1,0,0) are incomparable, so concurrent. f (0,0,1) is concurrent with all P1 and P2 events shown.

Compared with Lamport clocks, vector clocks show both causality and concurrency, at the cost of vectors of size N in every message.