Vector clocks: detecting concurrency (Fidge and Mattern 1988)

A Lamport timestamp orders events but cannot tell whether two events are causally related. Fidge and Mattern independently gave each process a vector of counters, one per process. Entry q of an event’s vector counts the events at process q that happened before or at it, so comparing two vectors entry by entry answers exactly whether one event caused the other or the two are concurrent.

What to look for

For every pair of events, vectors and Lamport timestamps never disagree on a causal pair, but only vectors recognize the concurrent pairs. Concurrent updates are the ones a replicated system must reconcile; two conflicting transactions broadcast at the same time are concurrent in exactly this sense.

The history behind this experiment: Breakthroughs in Peer-to-Peer Networking. See Exercises: networking for a worked solution to the exercise.

The same history as the Lamport example

import itertools

import matplotlib.pyplot as plt
import numpy as np

import blockchainkit as bk

history = [
    [("send", "m1"), ("local", "a"), ("receive", "m3")],
    [("receive", "m1"), ("send", "m2")],
    [("local", "b"), ("receive", "m2"), ("send", "m3")],
]
vectors = bk.network.vector_timestamps(history)
lamport = bk.network.lamport_timestamps(history)
events = [(p, i) for p, row in enumerate(history) for i in range(len(row))]
names = [f"P{p}:{history[p][i][1]}" for p, i in events]
for name, (p, i) in zip(names, events, strict=True):
    print(f"{name:7s} Lamport {lamport[p][i]}  vector {vectors[p][i]}")

P0:m1   Lamport 1  vector (1, 0, 0)
P0:a    Lamport 2  vector (2, 0, 0)
P0:m3   Lamport 6  vector (3, 2, 3)
P1:m1   Lamport 2  vector (1, 1, 0)
P1:m2   Lamport 3  vector (1, 2, 0)
P2:b    Lamport 1  vector (0, 0, 1)
P2:m2   Lamport 4  vector (1, 2, 2)
P2:m3   Lamport 5  vector (1, 2, 3)

Classify every pair

relation = np.zeros((len(events), len(events)))
for (x, (p, i)), (y, (q, j)) in itertools.product(enumerate(events), repeat=2):
    a, b = vectors[p][i], vectors[q][j]
    if bk.network.happened_before(a, b):
        relation[x, y] = 1
        assert lamport[p][i] < lamport[q][j]  # Causal order implies Lamport order.
    elif bk.network.happened_before(b, a):
        relation[x, y] = -1
concurrent = int((relation[np.triu_indices(len(events), 1)] == 0).sum())
print(concurrent, "concurrent pairs")
assert bk.network.concurrent(vectors[0][1], vectors[2][0])  # "a" and "b".

fig, ax = plt.subplots(figsize=(6, 5))
ax.imshow(relation, cmap="coolwarm", vmin=-1, vmax=1)
ax.set_xticks(range(len(events)), names, rotation=60)
ax.set_yticks(range(len(events)), names)
ax.set_title("row -> column (red), column -> row (blue), concurrent (grey)")
fig.tight_layout()

8 concurrent pairs

Exercise

A vector clock grows with the number of processes. Why can no scalar clock capture concurrency exactly? Hint: in this history, find events x, y, z with x concurrent to y and y concurrent to z, but x before z. Could “equal timestamps” ever mean “concurrent”?