Why can't a distributed system simply order events by their timestamps?

Each machine's clock drifts and is only synced to within some error, so two events on different machines can be stamped in the wrong order, and a reply can even appear before its cause. Use a single writer for ordering, or logical clocks that follow cause and effect. The trade-off is that logical time does not match real time.

What is the difference between a Lamport clock and a vector clock?

A Lamport clock is one counter per node that guarantees an event that happened before another has a smaller number, but a smaller number does not prove a cause, so it cannot detect concurrency. A vector clock keeps one counter per node and can tell before, after or concurrent. The trade-off is metadata that grows with the number of nodes.

Two users edit the same record at nearly the same time on different replicas. What happens with last-write-wins?

The replica with the later timestamp wins and the other write is discarded silently, even if the clocks were skewed or the writes were concurrent. For important data keep both versions using version vectors and merge them, or use a data type designed to merge, such as a CRDT. The trade-off is more work for the application in return for no lost writes.

How do you get a reliable order of events across many producers?

Route events that must stay ordered to one partition or leader and give them sequence numbers there. Order is guaranteed within a partition, not across them. The trade-off is that one partition's throughput limits that stream, so choose the key carefully.

What is a hybrid logical clock and why would you use one?

It combines a node's wall-clock time with a small counter, and takes the larger stamp when a message arrives. Stamps stay close to real time, so they are useful for queries and debugging, and they never go backwards across a message, so cause and effect is respected. The trade-off is that it cannot detect concurrent writes the way a vector clock can, and it still depends on clocks being reasonably well synced.

A client holds a lock lease, pauses for a long time, then writes. How do you stay safe?

Issue a fencing token, a number that grows on every grant, and have the storage layer reject any request with a smaller token than one it has already seen. The stale client is refused even though it still believes its lease is valid. The trade-off is that the resource itself must check tokens, so it cannot be a plain store with no support for them.

How can a system like Spanner use time for ordering when clocks are unreliable?

It uses hardware clocks that report an uncertainty interval instead of a single instant, and a write waits out that uncertainty before it commits, so that timestamps are ordered correctly. The trade-off is special hardware and a small commit delay in return for global strong consistency.

Time and Ordering in Distributed Systems

Why time and ordering are hard, and when to care

On one machine, "which happened first?" is answered by the clock. Across many machines there is no shared clock. Each machine's clock drifts, and syncing them leaves errors of milliseconds or more. Messages arrive late or out of order. If a system sorts events by their wall-clock timestamps, it can put a reply before the question that caused it, or silently discard a write.

Ordering events correctly gives you two things interviewers always ask about:

Consistency: events are ordered in a way that respects cause and effect, so effects never appear before causes.
Correct conflict handling: the system can tell the difference between "after" and "at the same time", so concurrent writes are merged rather than lost.

Care about this when:

Several nodes write the same data and must agree on the latest version.
You build replication, collaborative editing, distributed logs or last-write-wins stores.
You compare timestamps from different machines for anything that matters.

Skip it, or use something simpler, when:

One node orders everything: a single database sequence is enough.
Timestamps are only for display or rough sorting.

Try it

Two events on different nodes must be put in order. Change how they are stamped, then change the situation.

Time and Ordering in Distributed Systems

Step 1 of 4 · Press Space to play, arrow keys to step

Ordering withSituation

Initial state. Three nodes keep their own clocks and must put events in a sensible order without a shared clock.

tick:: 0
causality violations:: 0
concurrent events ordered by mistake:: 0

1 tick = one step of the simulation.

Speed

Things to try:

Run Wall-clock timestamps with Ben's clock is 5 seconds behind. The reply sorts before the write it answers.
Switch to Lamport clocks and Vector clocks with the same skew, and note that cause and effect are respected.
Choose Ana and Cy write at the same time. Only the vector clock can tell the writes were concurrent.

What to watch:

The 5 second skew is exaggerated so the effect is easy to see. It is illustrative, not a typical clock error.
A vector such as [1, 1, 0] lists one counter per node, in the order Ana, Ben, Cy.
With Lamport clocks and concurrent writes, both writes get the same number, and the simulation breaks the tie by node name. That tie-break is an arbitrary rule, which is why the conflict goes unnoticed.
Ben's reply counter is the larger of his own and the received one, plus one. That is why it always follows the write.

Ways to order events

Approach	How it works	Good when	Weakness
Wall-clock time	Use each machine's clock	Display, rough sorting, logs	Clocks drift and jump, so order can be wrong
Logical (Lamport) clock	One counter per node, increased on each event and on each received message	A total order that respects cause and effect	Cannot tell concurrent events apart
Vector clock	One counter per node, kept as a list	Detecting concurrent writes and conflicts	Grows with the number of nodes
Hybrid logical clock	Wall time plus a counter	Timestamps close to real time that still respect causality	Slightly more complex
Central sequencer or single leader	One node assigns the order	Simplicity, strong order	The sequencer is a bottleneck and a single point of failure
Bounded-error clocks (TrueTime)	Hardware clocks with a known error, and writes wait out the error	Global strong consistency	Needs special hardware

Happens-before and concurrency

Event A happened before B if A could have caused B: they are on the same node in that order, or A is the sending of a message and B its receipt, or the relation follows through a chain. If neither happened before the other, they are concurrent: neither knew about the other.

Lamport clocks give each event a number so that if A happened before B then A's number is smaller. The reverse is not guaranteed, so a bigger number does not prove a cause.
Vector clocks keep one counter per node. Comparing two vectors tells you: A before B, B before A, or concurrent. That lets a system keep both versions of concurrent writes and merge them.

How the clocks work

Lamport clock: each node keeps a counter. Before an event it adds 1. When sending, it attaches the counter. On receiving, it sets its counter to the larger of its own and the received one, then adds 1.
Vector clock: each node keeps a list with one slot per node. A node increments its own slot for each event. On receiving a message, it takes the larger value in each slot, then increments its own.
Compare two vectors: if every slot of A is at most B's and some slot is smaller, A happened before B. If neither is at most the other everywhere, they are concurrent.
Resolve conflicts: for concurrent writes, keep both (and let the application or a data type such as a CRDT merge them), rather than letting a clock decide.
Hybrid logical clock: each node keeps its wall-clock time and a small counter. On a local event or on receiving a message, it takes the largest of its own stamp and the received stamp (and its current wall time), and increases the counter when the times tie. The stamp stays close to real time, yet it never goes backwards and always follows the message it answers.

Time and ordering vs the alternatives

Concern	Logical or vector clocks	Wall-clock last-write-wins	Single leader orders everything
Respects cause and effect	Yes	No, when clocks skew	Yes
Detects concurrent writes	With vector clocks	No	Not needed
Works with no coordination	Yes	Yes	No
Can lose a write silently	No, if vector clocks keep both versions. Yes, if a Lamport clock feeds last-write-wins	Yes	No
Metadata size	Small to growing	None	None
Best for	Multi-writer replication	Caches and non-critical data	Most databases

One caution about the "Can lose a write silently" row: it is true of vector clocks that keep both versions. A Lamport clock gives concurrent writes an arbitrary order (often by node name), so if it feeds a last-write-wins rule, one concurrent write is still dropped. Only vector clocks tell you the writes were concurrent.

For critical data prefer a single writer per item. Use logical clocks when several writers are required.

Avoiding a new single point of failure

Central sequencer: if you use one, make it a replicated service with a leader, and hand out ranges of numbers to cut calls.
Clock sync: run time synchronisation (NTP or a cloud time service) on every node and monitor offsets. Alert on large drift.
Metadata growth: prune old entries from vector clocks, or use a different mechanism such as version vectors per key.

You accept extra metadata on every write and the work of merging concurrent versions.

When clocks and messages misbehave

Clocks can step. A time sync can move a clock forwards or even backwards. Code that measures a duration should use a monotonic clock, which never goes backwards, not the wall clock.
Leap seconds. Some systems smear a leap second over a period, and others repeat a second. Either way, two machines can disagree about the time for a while.
Messages can be delayed, duplicated or lost. A message may arrive long after it was sent, so a logical clock only orders what it has seen. Design handlers so a repeated or late message does no harm.
A paused process still believes its old time. After a long pause (garbage collection, a stalled virtual machine) a node may act on a stale reading of the clock, which is why leases need fencing tokens.

Common mistakes

Comparing timestamps from different machines to decide who wrote last.
Assuming a synced clock is exact. Sync error and clock steps still exist.
Using last-write-wins on important data. It silently drops a concurrent write.
Assuming a bigger Lamport number means "after". It only means "not before".
Letting vector clocks grow without bound. Pruning old entries fixes the size, but it can lose information, so two versions may later look concurrent when one really followed the other. That costs an extra merge, not a lost write.
Ignoring leap seconds and time zones. Store times in UTC.

How to talk about time and ordering in an interview

Say you cannot trust wall clocks across machines, and explain drift and skew.
Name happens-before, then offer a single leader for ordering, or Lamport and vector clocks when several nodes write.
Mention concurrent writes, how you detect them, and how you resolve them (merge, application logic or CRDTs).
Name the trade-off: logical clocks give correct ordering with no coordination, but they do not map to real time and add metadata.

Where you meet time and ordering problems in real systems

Replicated databases, collaborative editors, event logs and caches all have to order events from several machines. Here are three drawn out, the first with code you can run, then more examples.

Example 1: Lamport and vector clocks in code

Both clocks are small: a counter, or a list of counters. The code below runs the scenario from the simulation. Open the example below to see the picture and the code.

Config: Lamport and vector clocksSetup a short function eachCode no dependencies

Ana's write is stamped with her counter and sent with the message. Ben takes the larger counter and adds one, so his reply is always stamped after the write.

# Lamport and vector clocks. No libraries are needed.

class Lamport:
    def __init__(self):
        self.t = 0
    def event(self):                 # a local event, or sending a message
        self.t += 1
        return self.t
    def receive(self, other):        # receiving a message stamped with the sender's clock
        self.t = max(self.t, other) + 1
        return self.t

def vc_event(vc, me):                # increment my own slot
    vc = dict(vc); vc[me] = vc.get(me, 0) + 1; return vc

def vc_receive(mine, theirs, me):    # take the larger value in each slot, then count this event
    merged = {k: max(mine.get(k, 0), theirs.get(k, 0)) for k in set(mine) | set(theirs)}
    return vc_event(merged, me)

def compare(a, b):                   # "before", "after", "equal" or "concurrent"
    keys = set(a) | set(b)
    le = all(a.get(k, 0) <= b.get(k, 0) for k in keys)
    ge = all(a.get(k, 0) >= b.get(k, 0) for k in keys)
    return "equal" if le and ge else "before" if le else "after" if ge else "concurrent"

# Ana writes and Ben replies, even though Ben's wall clock is behind.
ana, ben = Lamport(), Lamport()
write = ana.event()                  # 1
reply = ben.receive(write)           # 2 : always larger than the write it follows
assert write < reply

# Ana and Cy write without seeing each other: the vector clocks are concurrent.
a = vc_event({}, "A")                # {"A": 1}
c = vc_event({}, "C")                # {"C": 1}
assert compare(a, c) == "concurrent"
assert compare(a, vc_receive(a, c, "B")) == "before"
print("ok")

Both programs were run (Python 3 and Node.js) and printed ok with their checks passing. The examples use two or three nodes only.

Example 2: Concurrent writes in a replicated store

Two replicas accept writes to the same key at the same time. When they exchange data, a vector clock shows the writes are concurrent, so the store keeps both versions for a merge.

Replica A and replica B each accept a write to the same key. After they sync, their vector clocks are concurrent, so both versions are kept for a merge instead of one overwriting the other.

Example 3: Comparing two vectors

Each slot is one node's counter. Compare slot by slot.

Ana's write is [1, 0, 0] and Cy's is [0, 0, 1]. The slots are in the order Ana, Ben, Cy. Neither is at least as large as the other in every slot, so the writes are concurrent.

More real-world scenarios

4. Distributed databases

Replicas accept writes during a network split and must reconcile afterwards. Version vectors tell which versions are concurrent.

5. Collaborative editing

Two people type in the same document. Operations carry logical timestamps so every copy converges to the same text.

6. Event logs

Events from many services are merged into one stream. A partition or a sequence number gives a stable order within a key.

7. Caches with last-write-wins

A cache may use timestamps, and it accepts that a skewed clock can keep an older value, because the data can be refetched.

8. Distributed tracing

A trace follows a request across services using IDs and parent links, not clocks, to show the order of calls. Each span still records a start time and a duration from local clocks, so the timeline view can look slightly off when machine clocks differ.

9. Leases and locks

A lock's expiry compares times, so the system uses lease lengths with margins and fencing tokens for safety. A fencing token is a number that grows each time the lock is granted. The storage service rejects any request that carries a smaller token than one it has already seen, so a client that was paused past its lease cannot overwrite newer work.

10. Financial ledgers

Entries are ordered by a single writer or sequence number per account, never by wall-clock time across machines.

Tools and managed services

Kind	Name	Notes
Time sync	NTP, chrony, cloud time services	Keep clocks close, but never perfectly
Databases	Apache Cassandra, Amazon DynamoDB, Riak	Replicated stores. Cassandra resolves conflicts with write timestamps (last-write-wins), and Riak can keep concurrent versions using version vectors. Check each product's documentation for its current behaviour
Bounded-error time	Google Spanner TrueTime	Hardware clocks with a known error
Data types	CRDT libraries	Merge concurrent changes automatically
Sequence sources	Database sequences, Apache ZooKeeper, etcd	Hand out ordered numbers or revisions

The takeaway

Whenever several machines must agree on the order of events, do not trust their clocks: use one writer, or logical and vector clocks that follow cause and effect.

Time and Ordering in Distributed Systems

Key takeaways

Why time and ordering are hard, and when to care

Try it

Time and Ordering in Distributed Systems

Ways to order events

Happens-before and concurrency

How the clocks work

Time and ordering vs the alternatives

Avoiding a new single point of failure

When clocks and messages misbehave

Common mistakes

How to talk about time and ordering in an interview

Where you meet time and ordering problems in real systems

Example 1: Lamport and vector clocks in code

Example 2: Concurrent writes in a replicated store

Example 3: Comparing two vectors

More real-world scenarios

4. Distributed databases

5. Collaborative editing

6. Event logs

7. Caches with last-write-wins

8. Distributed tracing

9. Leases and locks

10. Financial ledgers

Tools and managed services

The takeaway

Interview questions