Clocks, ordering and conflict resolution

Every replicated system must eventually answer: which of these two writes came first? Wall clocks can’t answer reliably across machines, so distributed systems order events with logical clocks (Lamport, vector, hybrid) or tightly bounded physical time (TrueTime). When two writes really are concurrent, no clock can pick a correct winner, so you resolve the conflict by design: last-write-wins, an application merge, a CRDT, or one writer per key.

Picture it first: two scorers, one match

Two scorers sit at opposite ends of a cricket ground, each noting every ball with the time on their own wristwatch. At stumps, someone merges the two books by sorting on those times, and it goes wrong at once: one watch runs two minutes fast, so a boundary appears before the ball that produced it.

Real scorers order balls by over and ball number. 14.3 is the third ball of the fifteenth over whatever any watch says, because the number comes from one authority, the sequence of deliveries.

Entries from two different matches at the same moment have no meaningful order: they are concurrent. And when the two scorers at one match disagree about the same ball, “four runs” against “leg bye”, someone needs a rule: the official scorer wins, or both entries are reviewed.

Map it back: the wristwatches are server clocks, close but never identical; the over-and-ball number is a logical clock or a leader’s sequence number; two matches are causally unrelated events; the disputed ball is a write conflict, and the rule is your conflict-resolution strategy.

Why wall clocks can’t order events

Clocks drift, and synchronisation is approximate

A server’s clock is a quartz oscillator, and no two tick at exactly the same rate; the error is measured in parts per million (ppm). In one AWS example, chrony reported an EC2 instance’s clock running 7.1 ppm fast; Spanner budgets a conservative worst case of 200 ppm (200 µs per second). Over a day of 86,400 seconds, that is 7 × 86,400 µs ≈ 0.6 s and 200 × 86,400 µs ≈ 17 s of drift.

So a daemon (ntpd or chrony) keeps nudging each clock towards a reference. The HLC paper puts NTP at usually tens of milliseconds over the public internet and about 1 ms on a LAN under ideal conditions, with congestion and asymmetric routes occasionally causing 100 ms or more. Cloud time services do better: AWS’s Time Sync Service went from about 1 ms to the low tens of microseconds on supported instances. Even 1 ms matters: at 10,000 writes a second, that is 10 writes per millisecond whose order is a guess.

Clocks jump, repeat and pause

• Steps. A clock that is far off may be stepped instead of slewed, and a step backwards hands out the same timestamp twice. Linux documents CLOCK_REALTIME as subject to such jumps.
• Leap seconds. Google and AWS smear the occasional extra UTC second over many hours, and CockroachDB warns that every node must then smear the same way: don’t mix them with the default NTP pool, which doesn’t.
• Pauses. A garbage-collection pause or a VM migration freezes a process while real time moves on. CockroachDB’s FAQ describes a node resumed after VMware vMotion running briefly on a stale clock, then jumping forward.

Time-of-day vs monotonic clocks

The time-of-day clock (CLOCK_REALTIME, System.currentTimeMillis(), time.time()) tells you the date and can jump either way. The monotonic clock (CLOCK_MONOTONIC, System.nanoTime(), time.monotonic()) counts from an arbitrary point, the boot on Linux, and never goes backwards. Measure timeouts, backoff and latency with the monotonic one. Neither orders events across machines: one isn’t synchronised tightly enough, the other means nothing off its own machine.

The bug this causes: last-write-wins with skew

Many stores settle conflicts with last-write-wins (LWW): keep the version with the highest timestamp. Cassandra does this per column, with timestamps from the client or the coordinator, and its documentation says plainly that correctness depends on synchronised clocks. The quorums article shows two independent writers colliding; the nastier case is a write that depends on the one it loses to.

The dispatch service saw PAID and wrote 50 ms after it, yet lost because Node A’s clock was 80 ms ahead. No error, no log line: the order is stuck in PAID while a rider is on the way. Better NTP shrinks the window; it never closes it.

Happened-before: the order that actually matters

Leslie Lamport’s 1978 paper, “Time, Clocks, and the Ordering of Events in a Distributed System”, starts by giving up on physical time. Event a happened before event b, written a → b, if:

1. a and b are on the same process and a comes first; or
2. a is the sending of a message and b is the receipt of that message; or
3. there is some event c with a → c and c → b.

If neither a → b nor b → a, the events are concurrent: not simultaneous, just unable to influence each other. So happened-before is a partial order, and the paper warns that problems arise when people forget it. It is the cause-and-effect that causal consistency protects; here we want the mechanism to stamp it.

Lamport clocks

A Lamport clock is one integer per process, kept by two rules:

1. Tick. Increment the counter before each event, including a send.
2. Receive. Every message carries the sender’s counter. On receipt, set your counter to max(local, received) + 1.

class LamportClock:
    def __init__(self):
        self.t = 0

    def tick(self):               # local event, or just before a send
        self.t += 1
        return self.t

    def receive(self, t_msg):     # message arrives carrying t_msg
        self.t = max(self.t, t_msg) + 1
        return self.t

The guarantee, Lamport’s clock condition: if a → b, then L(a) < L(b). The converse does not hold. A smaller number means “a might have caused b, or they were concurrent and a’s process happened to count slower”.

Lamport clocks earn their keep in two ways:

• A total order everyone agrees on. Sort events by (counter, process id). Every node sorts the same events identically, and the order never contradicts causality. Lamport used it for mutual exclusion without a lock server: requests are granted in timestamp order. Paxos proposal numbers, a counter made unique with a server id, borrow the idea; see consensus and leader election.
• Cheap causal metadata. One integer per message, whatever the cluster size.

The limit shows up when you replicate data. Replica X holds a value stamped 41, replica Y one stamped 42. Was 42 written by someone who had seen 41, so it can replace it, or by someone who hadn’t, so they conflict? One number can’t say.

Vector clocks and version vectors

A vector clock, proposed independently by Colin Fidge and Friedemann Mattern around 1988, keeps one counter per process. A process increments its own entry on every event; a message carries the sender’s whole vector, and the receiver takes the entry-by-entry maximum, then increments its own entry. To compare V and W:

• Every entry of V ≤ the matching entry of W (and not equal): V happened before W.
• Every entry of W ≤ V: W happened before V.
• Some bigger, some smaller: concurrent.

That is the converse Lamport clocks lack: V is less than W exactly when V’s event happened before W’s, so concurrency becomes detectable.

Version vectors apply the same comparison to copies of data: each stored value carries one counter per replica that has updated it. Papers often use the names loosely. Dynamo’s “vector clocks” are version vectors: lists of (node, counter) pairs where a version whose counters are all ≤ another’s is an ancestor and can be forgotten, and anything else is a conflict to reconcile.

The price is size: one entry per writer, so key vectors by server, never by end user. Dynamo’s vectors stayed short because a key’s top N nodes usually coordinated its writes, but failures pushed writes elsewhere, so Dynamo truncated them: once a clock reached about 10 (node, counter) pairs, the oldest pair was dropped. The paper admits descendant relationships can then no longer be derived exactly, though the problem never surfaced in production. Riak later adopted dotted version vectors; the quorums article covers how siblings are stored.

Hybrid logical clocks

Logical clocks ignore real time, so you can’t ask “what did the data look like at 10:00?”; physical clocks break causality. Sandeep Kulkarni, Murat Demirbas and colleagues proposed hybrid logical clocks (HLC) in 2014 to get both. An HLC timestamp is a pair (l, c): l is the largest physical time the node has heard of, from its own clock or any message, and c is a counter that orders events sharing the same l. The paper’s rules:

def send_or_local(self):
    pt, old = physical_clock(), self.l
    self.l = max(old, pt)
    self.c = self.c + 1 if self.l == old else 0
    return (self.l, self.c)

def receive(self, l_msg, c_msg):
    pt, old = physical_clock(), self.l
    self.l = max(old, l_msg, pt)
    if self.l == old == l_msg:
        self.c = max(self.c, c_msg) + 1
    elif self.l == old:
        self.c += 1
    elif self.l == l_msg:
        self.c = c_msg + 1
    else:
        self.c = 0          # our own physical clock is ahead of everything we've seen
    return (self.l, self.c)

The paper proves what makes it useful:

• Causal. If e → f, then (l, c) of e is smaller than that of f, compared as a pair. It is a Lamport clock.
• Close to real time. l is never behind the local physical clock and never more than the sync error ε ahead of it, so you can query by it.
• Compact. 48 bits of physical time (microsecond granularity) plus a 16-bit counter fit in 64 bits.
• Tolerant. If NTP steps the clock back, l stays put and c keeps counting, so timestamps never repeat.

Replay Figure 1 with HLC. If the dispatch write carries the timestamp it read, as CockroachDB’s causality tokens do, Node B must stamp above (.080, 0), say (.080, 1), and RIDER_ASSIGNED wins. For two truly concurrent writes, though, last-write-wins on an HLC still throws one away. CockroachDB timestamps transactions with HLCs, and YugabyteDB uses the same idea as “hybrid time”.

CockroachDB: uncertainty instead of atomic clocks

CockroachDB runs on ordinary NTP-synced machines and assumes a maximum clock offset, 500 ms by default. A node out of sync with at least half the others by 80% of that (400 ms) shuts itself down.

A transaction takes a provisional timestamp t and an uncertainty interval [t, t + max offset]. If a read meets a value written inside that interval, CockroachDB can’t tell whether it happened before the transaction began, so it does an uncertainty restart: bump the timestamp above the value and re-read. The upper bound stays fixed, so the window shrinks and restarts are bounded. In Cockroach Labs’ words: Spanner always waits after writes; CockroachDB sometimes retries reads. You gain consistency on commodity hardware; you pay with occasional restarts on freshly written keys and a hard dependence on bounded clocks.

TrueTime: bound the error, then wait it out

Spanner went the other way: make clock error small and known. TT.now() returns an interval, [earliest, latest], guaranteed to contain the true time; half its width is the error bound ε.

Each data centre has time masters with GPS receivers or atomic clocks, which fail in unrelated ways. Every machine polls several masters every 30 seconds and assumes its own clock may drift 200 µs per second in between. So ε rises like a sawtooth: 30 s × 200 µs/s = 6 ms, plus about 1 ms of network delay, gives ε of roughly 1 to 7 ms, usually about 4 ms.

Commit wait turns that bound into external consistency: if T1 commits before T2 starts, T1 gets the smaller timestamp, wherever they run.

1. The coordinator picks a commit timestamp s no smaller than TT.now().latest.
2. Nobody may see the commit until TT.after(s) is true: earliest has passed s, so s is in the past on every machine.

The expected wait is about 2ε, roughly 8 ms at ε = 4 ms; it usually overlaps with Paxos replication, and the paper’s microbenchmarks measured about 5 ms. You gain real-time ordering across continents with no central timestamp server, and consistent snapshot reads from any up-to-date replica. You pay for GPS and atomic-clock infrastructure and a few milliseconds per read-write transaction, and when ε spikes, every commit slows.

The idea is no longer Google-only: AWS’s ClockBound returns an interval, earliest to latest, around the current time on EC2, and with the hardware reference clock AWS quotes accuracy in the low tens of microseconds. If the error bound is, say, 40 µs, commit wait costs about 2 × 40 µs = 80 µs, not 8 ms.

Comparing the clocks

Ordering without clocks at all

Often the best clock is no clock: if one place hands out the numbers, there is nothing to skew.

• A single sequencer. A leader appends every write to a log, and the position is the order: a Raft log index, a Kafka partition offset, a write-ahead-log sequence number. You pay with one leader’s throughput per log and consensus to replace it. Kafka orders within a partition only; see message ordering.
• Per-key versions. Writers compare-and-set: UPDATE orders SET status = 'RIDER_ASSIGNED', version = 8 WHERE id = 4471 AND version = 7. A stale writer fails loudly instead of overwriting silently. That’s optimistic locking, and it would have caught Figure 1’s bug.
• Fencing tokens. A lock service hands out ever-growing numbers, and storage rejects writes carrying a smaller one than it has seen; see distributed locking.
• Roughly time-ordered IDs. Snowflake-style IDs start with a millisecond timestamp, so IDs minted on two machines inside the skew can sort either way: fine for a feed, wrong for picking a winner. See design a unique ID generator.

Resolving conflicts when writes are concurrent

Active-active regions, leaderless stores and offline-first apps all replicate writes accepted in more than one place, so concurrent writes will happen. Version vectors detect them; something still has to decide the result.

Last-writer-wins

Keep the version with the highest timestamp (wall clock, HLC or counter plus node id) and drop the rest. It always converges and needs no application code. Cassandra applies it per column; Dynamo offered it per service, for example for customer session data. What you pay: every concurrent write but one is silently lost, and with wall-clock stamps some non-concurrent ones too. Use it where a lost update is harmless: a cache entry, a “last seen” time, a profile field one person edits. Appending immutable rows instead of overwriting one cell makes it safer.

Keep siblings and merge in the application

Store every concurrent version as a sibling, return them all on read, and let the application merge them and write back with the combined version vector. Dynamo’s cart merged by union, so an add-to-cart was never lost, but, as the paper admits, deleted items could resurface: a union can’t tell “never added” from “removed”.

Custom merge rules

Many conflicts have a business answer. For an order’s status, take the state furthest along its lifecycle, so DELIVERED beats OUT_FOR_DELIVERY whatever the timestamps say. For a field-sales order, merge line items and send a clash on the same line to a person. The rule must give the same answer in any merge order, or replicas diverge; CRDTs guarantee that by construction.

CRDTs: data types that merge themselves

A conflict-free replicated data type (CRDT) merges concurrent updates automatically, so any two replicas that have received the same updates are in the same state; Marc Shapiro and colleagues call this strong eventual consistency. State-based CRDTs ship whole states and merge with a function that is commutative, associative and idempotent, so duplicated or reordered messages are harmless, at the cost of bigger messages. Operation-based CRDTs ship small operations that commute, but need exactly-once delivery in causal order. The building blocks:

• G-Counter: one slot per replica; each replica increments only its own; merge takes the per-slot maximum; the value is the sum.
• PN-Counter: two G-Counters, for increments and decrements; the value is the difference.
• LWW-Register: a value plus a timestamp. Last-write-wins, formalised.
• OR-Set (observed-remove): each add gets a hidden unique tag, and a remove deletes only the tags it has seen, so a concurrent add survives and deleted cart items stay deleted.
• Sequence CRDTs (Treedoc, Logoot, RGA) give every character a unique position id, so concurrent edits interleave identically everywhere.

CRDTs have costs. Metadata grows with replicas and, for sets, with history. And they guarantee convergence, not business rules: the CRDT study shows a counter can’t be kept non-negative locally, because two replicas at 1 can each decrement and converge to −1. The escape is to synchronise, for example by reserving decrements in advance (escrow).

Operational transformation

Before CRDTs, collaborative editors used operational transformation (OT), from Ellis and Gibbs in 1989. Each edit is an operation such as “insert ‘IT’ at position 3”; an operation made against an older version is transformed, say shifted past a concurrent insert, before it is applied. Google Docs uses OT, with changes flowing through a server. That server matters: the CRDT authors note that most published fully decentralised OT algorithms turned out to be incorrect, while sequence CRDTs need no server at all. Design Google Docs walks through both.

Avoid the conflict: one writer per key

The most reliable resolution is not needing one. Give every key a home, one region or leader that accepts its writes, and route writes there while serving reads locally. A wallet homed in Mumbai takes every debit in Mumbai; its owner travelling in Singapore pays a round trip per write but never causes a conflict. You pay with write latency far from home and a failover plan; see multi-region and active-active.

Choosing a strategy per feature

Ask what a lost or merged update costs, then pick the cheapest mechanism that makes it acceptable.

Going deeper: traps that bite in production

Client-supplied timestamps. Cassandra accepts write timestamps from clients. A client whose clock is a year ahead wins every conflict it touches until real time catches up, and earlier-stamped deletes can’t remove its data. Let servers assign timestamps, or validate them.

Monitor clocks like disks. Alert on the offset chrony or ntpd reports, and on jumps. As in CockroachDB, a node whose clock leaves the safe bound should stop serving, not limp on.

Deletes need history. LWW needs tombstones and OR-Sets need tags, both kept until every replica has seen the delete; the quorums article shows how expired tombstones bring data back.

Snapshots across shards. A read “as of 10:00:00” across shards is consistent with HLC or TrueTime stamps; with raw wall clocks you can see an effect without its cause.

Cheat sheet

How to say it in the interview

“Clocks on different machines disagree by milliseconds and can jump, so a wall-clock timestamp never decides which write wins unless losing a write is fine. I get order from one place where I can: a leader per key, a partition offset, a version number with compare-and-set. Where several regions accept writes, values carry version vectors so I can tell newer from concurrent, and I resolve per data type: likes are a G-Counter, the cart an OR-Set, the profile last-writer-wins, and the wallet has one home region with consensus. For globally ordered transactions, I’d use hybrid logical clocks with a bounded offset, like CockroachDB, or TrueTime-style commit wait, like Spanner.”

Why not just sync clocks with NTP and use timestamps? NTP gets you about a millisecond on a good LAN and tens over the internet, and clocks still step and pause. Writes inside that skew can be misordered, and last-write-wins silently drops the newer one.

What’s the difference between a Lamport clock and a vector clock? Both respect causality. A Lamport clock is one number: a total order, but it can’t tell ordered from concurrent. A vector clock keeps a counter per writer, so it detects concurrency, at a size that grows with writers.

How does Spanner get external consistency? TrueTime returns an interval with error ε of a few milliseconds, backed by GPS and atomic clocks. A commit takes s = latest and stays invisible until s is definitely past, about 2ε, so any later transaction gets a larger timestamp.

How does CockroachDB manage without atomic clocks? HLC timestamps plus an assumed maximum offset, 500 ms by default. A read that meets a value inside its uncertainty window restarts at a higher timestamp, and nodes whose clocks drift too far shut down.

When are CRDTs the wrong answer? When the rule spans replicas: a balance that must stay positive, a seat sold once. CRDTs converge but can’t refuse a write; use a single writer, consensus or escrow budgets.

Where to go next

• Strong vs eventual consistency: session guarantees and causal consistency.
• Quorums and leaderless replication: LWW in Cassandra, siblings, read repair, tombstones.
• CAP theorem and PACELC: why writes on both sides of a partition conflict.
• Consensus and leader election: the single sequencer, done safely.
• Distributed locking: fencing tokens and lease clock assumptions.
• Gossip protocol: how replicas spread versioned state.
• Multi-region and active-active: homing keys across regions.
• Design Google Docs: OT and sequence CRDTs in a real design.
• Design a unique ID generator: roughly time-ordered IDs and their limits.

References and further reading

1. Time, Clocks, and the Ordering of Events in a Distributed System (Lamport, CACM 1978)lamport.azurewebsites.netDefines happened-before as a partial order, the clock condition, the two implementation rules and the (counter, process) total order used for mutual exclusion.
2. Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases (Kulkarni et al., 2014)cse.buffalo.eduThe hybrid logical clock algorithm, its proofs (causality, l within ε of physical time), the 48 + 16 bit encoding, and typical NTP accuracy figures.
3. Spanner: Google’s Globally-Distributed Database (Corbett et al., OSDI 2012)static.googleusercontent.comTrueTime’s interval API, GPS and atomic-clock time masters, the 1–7 ms sawtooth for ε, 200 µs/s drift budget, and the commit-wait rule.
4. Dynamo: Amazon’s Highly Available Key-value Store (DeCandia et al., SOSP 2007)allthingsdistributed.comVector clocks on every version, syntactic versus semantic reconciliation, truncation at about 10 entries, and the cart merge that can resurrect deleted items.
5. A comprehensive study of Convergent and Commutative Replicated Data Types (Shapiro et al., INRIA RR-7506, 2011)inria.hal.scienceState- and operation-based CRDTs, G-Counter, PN-Counter, LWW-Register, OR-Set, sequence CRDTs, and why a non-negative counter needs synchronisation.
6. Living Without Atomic Clocks (Cockroach Labs blog)cockroachlabs.comHow CockroachDB uses an uncertainty interval and read restarts instead of Spanner-style commit wait, plus causality tokens.
7. CockroachDB operational FAQs: what happens when node clocks are not properly synchronized?cockroachlabs.comThe 500 ms default maximum offset, self-shutdown at 80% of it, leap-second smearing compatibility, and stale clocks after VM migration.
8. Apache Cassandra documentation: Dynamo architecture (data versioning)cassandra.apache.orgPer-column last-write-wins using client or coordinator timestamps, and the warning that correctness depends on synchronised clocks.
9. It’s About Time: Microsecond-Accurate Clocks on Amazon EC2 Instances (AWS Compute Blog, 2023)aws.amazon.comAmazon Time Sync Service accuracy (from about 1 ms to tens of microseconds), clock error bounds, and ClockBound’s confidence intervals.
10. clock_gettime(2), Linux manual pageman7.orgCLOCK_REALTIME can jump and is adjusted by NTP; CLOCK_MONOTONIC never goes backwards and counts from boot.