Distributed Systems Foundations
Vector Clocks
Problem: Detecting causal relations
If L(e) < L(e’)
– Cannot conclude that ee’
Looking at Lamport timestamps
– Cannot conclude which events are causally related
Solution: use a vector clock
CS171 2
Vector Clocks
• Developed independently by Fidge, Mattern
and Schmuck.
• Time is represented by a set of n-dimensional
non-negative integer vectors.
• Each process has a clock Ci consisting of a
vector of length n, the total number of
processes vt[1..n]. vt[j ] is the local logical clock
of Pj and describes the logical time progress at
process Pj
CS171 3
Vector Clock Protocol
• Pi ticks by incrementing its own component of
its clock
– Ci[i] += 1
• Timestamp C(e) of event e is the clock value
after ticking
• Each message is piggybacked with the local
vector u
• Recipient updates local vector to max of u and
local vector v
CS171 4
5
Vector Clock Protocol
• Each process i has a local vector C
• Increment C[i] at each “local computation” and “send” event
• When sending a message, vector clock value V is attached to the
message. At each “receive” event, C = pairwise-max(C, V)
user1 (process1)
user2 (process2)
user3 (process3)
(1,0,0) (2,0,0) (3,0,0)
(0,0,2)
(0,2,2)(0,1,0)
(0,0,1)
(2,3,2)
(0,0,3)
C = (0,1,0), V = (0,0,2)
pairwise-max(C, V) = (0,2,2)
CS171
Vector clocks Protocol
1. Vector initialized to 0 at each process
Vi [j] = 0 for i, j =1, …, N
2. Process increments its element of the vector
in local vector before event:
Vi [i] = Vi [i] +1
3. Piggyback Vi with every message sent from
process Pi
4. When Pj receives message, compares vectors
element by element and sets local vector to
higher of two values
Vj [k] = max(Vj [k], Vi [k]) for k=1, …, N
CS171 6
Comparing vector timestamps
Define
V = V’ iff V [i ] = V’[i ] for i = 1 … N
V V’ iff V [i ] V’[i ] for i = 1 … N
V < V’ iff V V’ and V ≠ V’
For any two events e, e’
e e’ if and only if V(e) < V(e’)
Two events are concurrent if neither
V(e) V(e’) nor V(e’) V(e)
CS171 7
Structure of the Vector Clock
• In order to determine if two events e,e’ are
causally related or not, just take their vector
timestamps V(e) and V(e’):
– if V(e)