Lamport Clocks and Vector Clocks: Ordering Without a Clock

Newer edits get thrown away. Each phone keeps its own time and nothing makes the phones agree, so sorting edits by phone time can keep an old edit and drop the newer one. Vector clocks and Lamport clocks order edits without trusting any clock.

Picture a common setup. A health programme gives its field health workers around Bhopal a shared notes app for household visits. Workers write notes on low-cost phones, often with no signal, and the notes sync to a server later. The setup is made up, but the problem is real.

The first sync rule is simple. Each edit carries the time shown on the phone, and the server keeps the edit with the latest time. This rule is called last write wins.

A review of 600 household notes finds 37 where a correction had vanished. One was a blood pressure reading that a worker had fixed after a second check. The review finds three causes.

• One phone's clock fell 40 minutes behind after a battery change. Its newer edits looked older, so they lost every time.
• Two workers edited the same household note while both were offline. The server kept one edit and dropped the other without telling anyone.
• Another phone jumped a day ahead after a bad time update. For a whole day, its old edits beat every honest edit.

Here is the first failure as a picture. Follow the two edits into the server and notice which one survives.

The team could try to keep the phone clocks closer together. That is a whole topic of its own, and it never makes clocks perfect. The better question is whether the app can order edits without trusting any clock.

Leslie Lamport answered that question in a 1978 paper. Vector clocks sharpened his answer about ten years later. This guide tries both ideas on the notes app.

Event A happened before event B when A could have affected B. Either both ran on one device in that order, or news of A reached B through a chain of messages.

A distributed system is a group of separate machines that work together only by sending messages. The notes app is one: many phones and one server. An event is anything a device does, such as saving a note, sending a sync message or receiving one.

Lamport's paper defines happened before with three rules. Here they are in notes-app terms.

• Same device: if phone A saves edit 1 and then edit 2, edit 1 happened before edit 2.
• Messages: sending a sync message happened before the server receives that same message.
• Chains: if X happened before Y, and Y happened before Z, then X happened before Z.

Two events are concurrent when neither happened before the other. Concurrent does not mean at the same moment. It means neither event could have known about the other.

Picture a bhishi, a savings circle where each member puts money into a shared pot every month. A member knows about a payment only if she made it or heard about it, directly or through someone who knew. Two payments in different villages, with no news passing between them, are concurrent.

This gives you a partial order: some pairs of events have a clear before and after, and other pairs have none. Lamport's paper defines this order without using physical clocks, looking only at events and the messages actually sent.

A Lamport clock is one counter on each device. It goes up by one for every event, travels with every message, and jumps ahead when a bigger number arrives.

The counter is called a logical clock, because it counts events rather than seconds. The number it gives an event is a Lamport timestamp. The team adds one to every phone and to the server.

1. 1

   Start at zero

   Every phone and the server begin with a counter of 0.

2. 2

   Add one before each event

   Saving a note, sending a sync and receiving a sync each add one. The new value is that event's timestamp.

3. 3

   Send the counter along

   Every sync message carries the sender's timestamp, like a stamp on a letter.

4. 4

   Jump ahead on receive

   The receiver sets its counter to the larger of its own value and the stamp, then adds one.

Now follow the household 14 note through the system. Watch each stamp come out bigger than the one before it, even though no clock is read.

Phone B's slow wall clock no longer matters. Its correction gets stamp 6, which is bigger than the original save at stamp 1. Sorting by Lamport timestamps puts the correction last, where it belongs.

Here is the whole clock in Python, with the diagram's journey replayed at the bottom. Each method returns the timestamp of the event it records.

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

    def tick(self):                       # any local event, like saving a note
        self.time += 1
        return self.time

    def send(self):
        return self.tick()                # this stamp travels with the message

    def receive(self, stamp):
        self.time = max(self.time, stamp) + 1
        return self.time


# Replay the note's journey from the diagram above
phone_a, server, phone_b = LamportClock(), LamportClock(), LamportClock()
phone_b.tick()                            # B's earlier save gets 1
phone_a.tick()                            # A saves the note: 1
stamp = phone_a.send()                    # A sends it with stamp 2
server.receive(stamp)                     # server: max(0, 2) + 1 = 3
stamp = server.send()                     # server sends it on with stamp 4
phone_b.receive(stamp)                    # B: max(1, 4) + 1 = 5
print(phone_b.tick())                     # B corrects the reading: prints 6

The receive line is the heart of it. Taking the max means the receiver's next event always gets a bigger number than anything that led to it. Lamport calls this guarantee the Clock Condition: if A happened before B, A's timestamp is smaller.

Lamport's own rule only says the receiver must move past the stamp and never go backwards. Max plus one is the usual way to meet it.

Back in the bhishi, imagine each member writes one number on the cover of her passbook. She adds one whenever she pays or hears news. When a friend shows a bigger number, she writes one more than that. The number grows with everything she has heard, but it does not say whose news it was.

Turning Lamport timestamps into one agreed order

Two events on different devices can get the same timestamp. Lamport breaks ties with any fixed order of the devices, such as their ids. Sort by timestamp first, then by device id, and every device agrees on one total order.

A total order means every pair of events has a before and after. Lamport used this to let processes share one resource fairly, granting requests in the order they were made.

A Lamport clock cannot tell you, in general, whether two events were concurrent. A smaller timestamp might mean the event came first, or it might mean the two events never knew about each other.

Lamport's paper says you cannot expect the reverse of the Clock Condition to hold. If it did, concurrent events would need equal timestamps. His own example shows two events, one before the other, that are both concurrent with a third, so that is impossible.

Here is the trouble in the notes app. After the sync above, both phones go out of signal. Phone A, at counter 2, adds a line saying the woman was referred to the clinic. That edit gets stamp 3.

Phone B, at counter 6, fixes the reading once more. That edit gets stamp 7. Both edits reach the server at the next sync.

Neither happened first. Neither phone saw the other's new edit, so the two edits are concurrent. If the server keeps the bigger stamp, the clinic referral disappears, and the server cannot even tell that anything was lost.

One case does tell you something. Equal Lamport timestamps on two different devices always mean concurrent events, because an event that could have affected another always gets a smaller number. Different timestamps prove nothing either way.

The paper also warns about a subtler problem. Say a coordinator saves a note asking for a recheck, then phones a worker to do it. The worker's edit can get a smaller stamp than the coordinator's note, because the system never saw the phone call. Lamport calls this anomalous behaviour.

Lamport clocks are still the right tool when you need one agreed order and do not need to detect conflicts. They cost one integer per device and one per message.

• Ordering entries in a shared log so every device applies them the same way.
• Deciding who gets a shared resource first, as in Lamport's own example.
• Giving log lines from several services an order that never puts an effect before its cause.

Vector clocks give each device a list of counters, one per device, instead of one number. Comparing two lists tells you exactly whether one event happened before another, or whether they were concurrent.

The idea appeared in 1988 in work by Colin Fidge and Friedemann Mattern, done separately. Mattern's paper shows that vector time captures happened before exactly, without losing information. A single Lamport number cannot do that.

Go back to the bhishi passbook. Now each member keeps a row for every member of the circle. Each row counts how many of that member's payments she has heard about. When two members meet, each copies the larger number in every row.

That copying is the vector clock rule. Each member is a device, each row is one entry in the vector, and a meeting is a message. The rules mirror the Lamport ones, with a list in place of a single number.

• Start: every device's list is all zeros.
• Local event: add one to your own entry only.
• Send: attach a copy of your whole list to the message.
• Receive: take the larger value in every entry, called the component-wise maximum, then add one to your own entry.

For stored data, systems usually use a close cousin called a version vector. It belongs to one item, such as one note, and it counts only writes to that item. The notes app keeps one version vector per household note.

Version vectors are older than vector clocks. Mattern's paper credits a 1983 paper by Parker and colleagues that used such vectors to detect copies of a file changed independently.

Compare them entry by entry. If every entry in A is less than or equal to the matching entry in B, and the two differ, A happened before B. If each has an entry bigger than the other's, they are concurrent.

The team stores each vector as a Python dict, a map from phone id to count. A phone that never wrote the note has no key, which counts as zero. Here are the two functions, with the clinic referral case at the bottom.

def compare(a, b):
    phones = set(a) | set(b)
    a_le_b = all(a.get(p, 0) <= b.get(p, 0) for p in phones)
    b_le_a = all(b.get(p, 0) <= a.get(p, 0) for p in phones)
    if a_le_b and b_le_a:
        return "same"
    if a_le_b:
        return "before"                   # a happened before b
    if b_le_a:
        return "after"                    # b happened before a
    return "concurrent"                   # neither saw the other

def merge(a, b):
    return {p: max(a.get(p, 0), b.get(p, 0)) for p in sorted(set(a) | set(b))}


# The clinic referral case from the steps below
a_copy = {"A": 2}                         # phone A added the referral
b_copy = {"A": 1, "B": 1}                 # phone B fixed the reading
print(compare(a_copy, b_copy))
combined = merge(a_copy, b_copy)
combined["A"] += 1                        # phone A saves the merged note
print(combined, compare(a_copy, combined), compare(b_copy, combined))

The two all() lines do the real work. If both are true, the vectors are equal. If neither is true, each side holds a write the other never saw, so the edits are concurrent.

The merge() function is the passbook copying step. It walks the phone ids in sorted order so the printed dict always looks the same. Python's set order for strings can change from one run to the next.

Now replay the clinic referral story with version vectors on the household 14 note.

1. 1

   Phone A creates the note

   The note's vector is {A: 1}. Phone A syncs it to the server.

2. 2

   Phone B downloads and corrects

   Phone B gets {A: 1}. Offline, its worker fixes the reading, so B's copy becomes {A: 1, B: 1}.

3. 3

   Phone A adds the referral

   Also offline, phone A adds the clinic referral. Its copy becomes {A: 2}.

4. 4

   The server compares

   {A: 2} has more from A. {A: 1, B: 1} has more from B. The compare function returns concurrent, so the server keeps both versions.

5. 5

   A worker merges

   Phone A shows both versions, and the worker writes one combined note. Its vector is merge({A: 2}, {A: 1, B: 1}) plus one for A: {A: 3, B: 1}.

6. 6

   The old versions go

   The new vector is bigger than or equal to both old ones in every entry. So both count as before it, and the server can drop them.

The diagram shows the decision the server makes each time two versions of a note meet. Start at the top and follow the answers.

Dynamo, a key-value store that Amazon described in a 2007 paper, uses the same idea with one entry per server rather than per phone. A key-value store is a database that saves each value under a key. The paper walks through two writes that branch from one version and get clocks that cannot be ordered.

A client then reads both branches, reconciles them, and writes a version whose clock covers both. The paper calls it syntactic reconciliation when the system can find the newest version from the clocks alone. When the client must merge branches with its own rules, it is semantic reconciliation.

A Lamport clock is one number that respects happened before, while a vector clock is a list that can also prove two events were concurrent. You pay for that extra power with size.

The team ends up using both. The server's own sync log uses Lamport timestamps, because it needs one order and never needs to detect conflicts. Each household note carries a version vector, because a lost correction is a health risk.

Lamport timestamps never broke their promise, but they were a poor guide to concurrency. Vector clocks matched the true happened-before order on every pair we checked.

We wrote a small simulator in Python 3.13.16. Each run has 4 devices and 30 random events: saves, sends and receives. We found the true happened-before order by following the messages, without using any clock, then checked both clocks against it.

Read the third row slowly. When two Lamport numbers differed, the pair was really ordered only 46.7 percent of the time in these runs. Sorting by Lamport number still gives one order that everyone agrees on. It just cannot tell you which edits clashed.

The percentages depend on the made-up workload, such as how often devices send messages. The rows that say all follow from the definitions, which is why they held in every run.

Vector clocks grow with the number of devices that write, and every conflict they find still needs someone to resolve it. Real systems spend most of their effort keeping both problems small.

The vector keeps growing

The notes app has 1,200 phones. A vector with an entry for every phone would add 1,200 numbers to each note. As compact JSON with ids like phone-0001, we measured 19,341 bytes, about 19 KB, against 46 bytes for three entries.

So the team stores only the phones that actually wrote the note. Most notes have two or three entries.

Dynamo's clocks hold one pair of server and counter for each server that coordinated a write, meaning it took charge of that write. The paper says writes usually go to one of the first few servers on the key's preference list, the servers chosen to store that key. During network splits or server failures, other servers take writes and the list grows.

Dynamo's fix is truncation. Each pair also stores when that server last updated the item. When the list reaches a threshold, for example 10 pairs in the paper, the oldest pair is removed.

We tested what truncation actually breaks, using one entry per phone, as in the notes app. Version X is {A: 1, B: 1}. Phone C edits on top of it, giving {A: 1, B: 1, C: 1}. With a limit of 2 entries, A's older pair is dropped.

Compare X with the trimmed {B: 1, C: 1} and the answer is concurrent, though the new version really came after X. The server keeps an extra sibling that nobody needed.

We then ran 300 random histories for each limit. Every mistake was this kind of false conflict. A limit of 2 got 15.05 percent of pairs wrong, a limit of 5 got 0.27 percent, and 10 got none with at most 12 writers.

No trimmed comparison made a concurrent or newer version look older, which would have dropped it silently. In our model, each writer always edits on top of its own latest copy. We did not test other designs.

Conflicts pile up

When a store keeps every concurrent version of a value, the versions are called siblings in the docs of Riak, a key-value database that uses vector clocks. Each sibling waits until the application or a person merges it.

Riak's docs call it sibling explosion when an object rapidly collects siblings that nobody reconciles. Each unreconciled sibling stays stored with the object, so the object keeps growing. The docs warn that reading an enormous object can crash the entire node.

Who gets an entry also matters. If every client gets one, the vector grows with the number of clients. Dotted version vectors, from a 2010 paper, claim to capture the full happened-before order while growing only with the servers that record updates.

As of 19 October 2026, Riak KV's docs for version 2.2.3 strongly recommend dotted version vectors over vector clocks. Every bucket type you create and activate, a bucket type being Riak's named group of settings, turns them on. Without bucket types, vector clocks stay the default.

Conflicts can also be rare. Over 24 hours of shopping cart traffic, the Dynamo paper reports that 99.94 percent of requests saw exactly one version.

Vector clocks know nothing about real time

A vector clock can say one edit came after another, but not whether that was a minute or a month later. It tracks the order of events, not the time of day.

Some databases need both, such as for a snapshot read: reading the data exactly as it stood at a certain time. A hybrid logical clock mixes a physical time reading with a small logical counter. NTP, the Network Time Protocol, is a standard way computers sync their clocks over a network.

The 2014 hybrid logical clock paper says it captures happened before like a logical clock and stays close to the NTP clock. It also fits in NTP's 64-bit timestamp format.

CockroachDB is one database that uses it. As of 19 October 2026, its v26.3 docs say each transaction gets a timestamp from hybrid logical clock time, used to track versions of values. The same docs say CockroachDB still needs moderately synchronised clocks.

One naming trap: Dynamo, the 2007 design, is not DynamoDB, Amazon's managed database service. DynamoDB global tables keep copies of one table in two or more AWS Regions, Amazon's separate geographic areas. In the default mode, multi-Region eventual consistency, each change is copied to the other Regions in the background. As of 19 October 2026, the docs say concurrent writes to one item are settled by last writer wins, using the latest internal timestamp.

Here are the guards the team adds so these problems stay small in the notes app.

• Store vectors as maps of only the phones that wrote, never a slot for all 1,200 phones.
• Give each phone a stable id at install, so a reinstall does not quietly add a new entry.
• Cap siblings at three per note, and flag the note for the programme's coordinators if it hits the cap.
• Show conflicts on the phone at the next sync, while the worker still remembers the visit.
• Log every conflict with both vectors, so the team can see which villages produce the most.

Explain them as two answers to one problem: ordering events when no clock can be trusted. Lead with a concrete failure, then show what each clock can and cannot prove.

1. 1

   Start with why wall clocks fail

   Clocks on different machines drift and jump. Show last write wins dropping a real correction because one phone ran slow.

2. 2

   Define happened before

   Same device in order, send before receive, and chains. Concurrent means neither event could know about the other.

3. 3

   Give the Lamport rules

   Add one per event, send the counter, take the max plus one on receive. State the one-way guarantee and the tie-break by id.

4. 4

   Show where Lamport stops

   Two offline edits get stamps 3 and 7. Explain that the bigger number proves nothing, so one edit is lost.

5. 5

   Add vector clocks

   One counter per writer, component-wise max on receive. Compare entry by entry to get before, after or concurrent.

6. 6

   Handle conflicts and cost

   Say who merges siblings and how. Then name the size problem and a fix, such as storing only writers or dotted version vectors, and say what truncation costs.