3 Topics
Chapter•140 Minutes

Advanced Distributed Systems: Clocks, Consensus, and CRDTs

Reason about causal ordering, quorum protocols, replica repair, stale ownership, and concurrent updates.

Lamport Clocks, Vector Clocks, and Causality

Physical clocks drift and cannot establish a perfect global event order. Lamport clocks assign logical counters that preserve the happens-before relation: if A causally precedes B, A receives a smaller timestamp. The reverse does not hold; a smaller timestamp does not prove causality.

Vector clocks track version counters across participants and can identify concurrent versions, but metadata grows and membership changes complicate the model. Hybrid logical clocks combine physical-time information with logical counters to provide useful time locality while preserving protocol-specific ordering properties.

Choose the smallest ordering scope that meets the requirement. A chat system may need order within each conversation; a global total order across unrelated entities is much more expensive. Timestamps, logical clocks, and consensus solve different problems.

Key Takeaways
  • Wall-clock timestamps do not prove causality.
  • Lamport clocks preserve causal order but cannot fully identify concurrency.
  • Specify the scope of ordering before choosing coordination.

Raft, Quorums, Gossip, and Replica Repair

Consensus protocols such as Raft allow a group to agree on a replicated log under specified failure assumptions. Majority quorums intersect, helping preserve committed decisions, but a partition without a quorum may be unable to make progress safely. Membership changes require protocol-specific procedures; changing a node list casually can break safety.

Gossip spreads membership or state information gradually. Anti-entropy compares replicas and repairs divergence; Merkle trees summarize ranges of data so replicas can locate mismatches without transferring every record. Repair consumes network and storage capacity and should not overwhelm foreground traffic.

Consensus does not make external side effects atomic. A leader-elected worker can become stale after a pause, so protected resources may need fencing tokens or idempotency. Use mature implementations and understand their operational assumptions instead of implementing a consensus protocol inside ordinary business code.

Key Takeaways
  • Consensus safety depends on quorum and membership rules.
  • Gossip convergence is gradual, not instantaneous.
  • Replica repair needs capacity and observability.

CRDTs and Conflict Resolution

Conflict-Free Replicated Data Types (CRDTs) define data structures whose concurrent updates can be merged predictably under specified conditions. Examples include grow-only sets, counters, and registers with explicit conflict semantics. Some CRDTs merge states; others propagate operations.

The merge behavior must match product meaning. A mergeable counter is not automatically appropriate for inventory, because concurrent decrements must not violate a no-negative-stock invariant. Financial balances, reservations, and permissions need domain-specific correctness guarantees.

Before choosing a CRDT, specify offline duration, tombstone retention, replica membership, conflict semantics, and compaction. CRDTs simplify particular convergence problems; they do not replace authorization, validation, or business invariants.

Key Takeaways
  • CRDT guarantees apply to specific operations and data types.
  • Choose conflict semantics that match the domain.
  • Do not use eventual merge semantics for invariants they cannot preserve.