Failure and Time in Distributed Systems

Every distributed systems proof assumes a system model that bounds what can go wrong.

• Synchronous model: message delivery has a known upper bound $\Delta$; clock drift is bounded; steps complete in bounded time. Rare in practice — a GC pause or a busy NIC can blow the bound.
• Partially synchronous model (Dwork-Lynch-Stockmeyer): the system is eventually synchronous — bounds exist but you don't know when they kick in. Matches real WANs and cloud networks.
• Asynchronous model: no timing guarantees whatsoever. Messages can be delayed arbitrarily. Hardest to work with — algorithms that are correct here are correct everywhere.

Most production consensus protocols (Raft, Paxos) are designed for partial synchrony: they are safe (never return wrong answers) in an asynchronous model, but live (eventually return answers) only under partial synchrony.

Failures fall into a hierarchy — each level strictly includes the one above.

The hierarchy matters for algorithm design: a protocol that tolerates crash-stop failures fails catastrophically against Byzantine nodes. Most data-center systems assume crash-recovery; Byzantine tolerance (BFT) is reserved for blockchains or safety-critical systems where nodes may be adversarially controlled.

Physical clocks on separate machines drift — even NTP-synchronized clocks have error on the order of milliseconds (wide-area) to microseconds (GPS-disciplined PTP). The fundamental constraint is the speed of light: a clock sync message takes nonzero time in transit, so you can never know the sender's clock reading right now.

The consequence: you cannot order events across nodes by wall-clock time. Consider two writes at $t_1 = 10:00:00.001$ on node A and $t_2 = 10:00:00.000$ on node B — which came first? Without coordination, you don't know. Spanner's TrueTime API bounds clock uncertainty and forces transactions to wait out the uncertainty window — expensive hardware, not a free lunch. For most systems the answer is logical clocks.

Leslie Lamport's 1978 insight: define a partial order directly from communication — no wall-clock needed.

Happens-before ($\to$) is the smallest relation satisfying:

1. If $a$ and $b$ are events on the same process and $a$ comes before $b$, then $a \to b$.
2. If $a$ = "send message $m$" and $b$ = "receive $m$", then $a \to b$.
3. Transitivity: $a \to b$ and $b \to c$ implies $a \to c$.

Events not related by $\to$ are concurrent. Lamport assigns integer timestamps:

On every event: L = L + 1
On send: attach L to message
On receive(msg): L = max(L, msg.L) + 1

Guarantee: $a \to b \Rightarrow L(a) < L(b)$. The converse is false — identical or higher timestamps don't imply causality. Lamport clocks capture direction but not full causal history.

Vector clocks fix Lamport's converse gap. Each of $n$ processes maintains a vector $V$ of $n$ counters.

# Process i initializes: V = [0] * n
# On internal event: V[i] += 1
# On send: V[i] += 1; attach V
# On receive from j with timestamp T:
#   V[k] = max(V[k], T[k]) for all k
#   V[i] += 1

Comparison rules:

• $V_a \leq V_b$ iff $V_a[k] \leq V_b[k]$ for all $k$.
• $a \to b$ iff $V_a \leq V_b$ and $V_a \neq V_b$.
• $a \parallel b$ (concurrent) iff neither $V_a \leq V_b$ nor $V_b \leq V_a$.

Vector clocks are characterize happens-before: $a \to b \Leftrightarrow V_a < V_b$. The cost is $O(n)$ space per message — fine for small clusters, painful for thousands of nodes (use version vectors or dotted version vectors instead).

Three processes $P_1, P_2, P_3$ with vector clocks $[v_1, v_2, v_3]$:

Now: $e_1 \to e_6$ because $[1,0,0] < [2,2,2]$. And $e_1 \parallel e_4$ because $[1,0,0]$ and $[0,0,1]$ are incomparable — $P_1$ and $P_3$ never communicated before $e_4$. This is the causality structure vector clocks expose that Lamport timestamps cannot.

Arrows show happens-before relationships derived from message passing.

Logical clocks aren't academic — they drive production systems:

• Conflict detection in CRDTs and eventual-consistent stores: Dynamo and Riak use vector clocks (actually version vectors) to detect when two writes are concurrent and hand the conflict to the application.
• Distributed tracing: systems like Jaeger propagate a Lamport-style counter in HTTP headers (traceparent) to reconstruct request causality across microservices.
• Optimistic replication: a replica accepts a write only if its vector clock shows the write's causal dependencies are already applied — preventing you from seeing a reply before its question.
• Debugging distributed bugs: tools like Molly and DistSys-Tester inject failures and check vector clock orderings to find violations of expected causal constraints.

The core lesson: when you cannot trust clocks, define order through communication — and vector clocks make that order computable.