CRDTs, Vector Clocks and Causal Ordering
CRDTs and causal metadata help replicas converge under concurrent updates, but the merge rule must preserve product semantics.
CRDTs, Vector Clocks and Causal Ordering
CRDTs and causal metadata help replicas converge under concurrent updates, but the merge rule must preserve product semantics. State-based CRDTs exchange states and use a merge operation that is associative, commutative and idempotent over a semilattice. Operation-based CRDTs disseminate operations with delivery assumptions. Lamport clocks order events consistently with happens-before but cannot distinguish all concurrent events. Vector clocks can detect causal order versus concurrency under tracked replicas.
Mechanism and worked example
A grow-only set merges by union. A multi-value register can retain concurrent values for application-level resolution. A last-writer-wins register may discard meaningful concurrent updates. Collaborative documents need stable sequence identities, tombstones and causal dependencies to preserve edit and deletion semantics.
| Clock/structure | Can establish | Cannot establish alone |
|---|---|---|
| Lamport clock | Order respecting causality | Whether events are concurrent |
| Vector clock | Causal order or concurrency | Wall-clock time or total order |
| G-counter | Monotonic increments | Bounded inventory |
| OR-set | Concurrent add/remove semantics | Arbitrary business conflict policy |
Failure modes and operations
Replica identity churn grows vector metadata. Dropping tombstones too early can resurrect deleted values. Last-writer-wins timestamps can be wrong under clock skew. Operation-based merging may require reliable causal delivery. Convergence does not guarantee a desirable product result.
Trade-offs and design boundary
CRDTs support local writes and eventual convergence without a single leader, but metadata, conflict semantics and garbage collection are nontrivial. A central sequencer or transaction authority is simpler when scarce-resource invariants need one winner.
Interview transfer exercise
Would a simple counter CRDT enforce a limited inventory count? No. Use coordination or a bounded-counter design with rights allocation so concurrent increments cannot exceed the limit.
Read the diagram
Replicas update independently → Vector metadata reveals concurrent histories → CRDT merge combines compatible state → Application invariant is checked after convergence
Would a simple counter CRDT enforce a limited inventory count? No. Use coordination or a bounded-counter design with rights allocation so concurrent increments cannot exceed the limit.
Your design draft
Clarify assumptions, explain your approach, and test the difficult cases. Save your draft, then compare it with the study notes.
Self-review checklist
Self-guided practice. Automated AI feedback and code execution are not connected.