What Does "First Come, First Served" Mean in Distributed Systems?
The opening of a 1978 paper hides a telephone example.
Imagine a nationwide networked system. A person in city A submits a request on machine A, then picks up the phone, calls a friend in city B, and asks them to submit another request on machine B. Which came first? Anyone would say: A came first — B happened *because* A already happened.
Yet the system might assign B an earlier timestamp. Because as far as the system is concerned, that phone call does not exist: machines A and B exchanged no messages, so the system has no way to know that A and B are causally related. This is not a bug — it is the nature of distributed systems. They can only see messages flowing inside themselves.
The person who wrote this example is Leslie Lamport. The paper, *Time, Clocks, and the Ordering of Events in a Distributed System*, was published in the July 1978 issue of Communications of the ACM — eight pages that became one of the foundational texts of distributed systems.
Causality Instead of Clocks
The most intuitive way to define "first come, first served" is to look at a clock. But every machine has its own clock, drifting at different rates, and two machines have no consensus on "what time it is now." Lamport's move is to throw the clocks away and directly define a relation, written as an arrow: *a happened before b*.
There are three rules. Two actions on the same process: the earlier one comes first. One machine sends a message before another machine receives it. If a precedes b and b precedes c, then a precedes c.
This arrow is called *happened-before*. Its trouble: some pairs of events are incomparable — neither comes before the other. Two machines each doing their own work with no messages in between are mutually incomparable. In the physical world we are used to saying "simultaneous"; in a distributed system, "simultaneous" simply has no definition. Lamport warned in the paper that many problems arise from people not fully realizing this.
The Clocks Are Just a Side Dish
Next comes the part that gives the paper its name. It attaches numbers to this relation: each process keeps a counter, incrementing it on every action it performs; when sending a message, it includes its current number; upon receiving a message, a process sets its counter to "the larger of its own number and the number in the message, plus one."
These numbers are called *logical clocks*. They have a beautiful property: if a happened before b, then a's clock is strictly less than b's clock. Because clocks only increase, and messages can only push clocks forward — numbers rise monotonically along the direction of causality.
A sequence of numbers is much easier to order than a relation graph. For two incomparable events, break the tie by process ID, extending the partial order into a total order. The total order is not unique — with a different set of clocks, ties may resolve differently — but every such order strictly follows the direction of causality. Queuing now has a uniform rule.
The paper applies this total order to a serious problem: mutual exclusion. When multiple machines contend for a resource, who enters first? Each machine maintains a request queue ordered by the total order. To request the resource, it broadcasts its request with its timestamp; it enters only after receiving acknowledgments from all machines and its own request sits at the front of its queue. The algorithm's cost is not computation but messages — every entry and exit requires a round of chatter across the network. More machines, more messages. Slow, but correct.
The Trouble on the Other End of the Phone
Logical clocks have a natural blind spot: the phone-call example at the start. They propagate only along messages within the system; causality outside the system is invisible to them.
The last two pages of the paper address this: bring real physical clocks back and synchronize them. Lamport derives a bound. Let κ be the clock drift rate (a second of work makes the clock advance 1 + κ seconds), μ the minimum message flight time between two machines, and ξ the maximum difference between two clocks after synchronization. The paper proves: as long as ξ/(1−κ) does not exceed μ, the anomalous "phone call inverting causality" behavior can never happen.
This inequality deserves a pause. The more accurate the clocks (smaller ξ) and the faster the messages (larger μ), the safer. It turns a philosophical question — "what is time in a distributed system?" — into an engineering parameter: buy clocks accurate enough and accept a fast enough network, and the whole system achieves physically meaningful consensus on first-come-first-served.
Four decades later, Google's Spanner database turned this inequality into infrastructure: GPS receivers and atomic clocks in data centers worldwide, clock differences compressed to a few milliseconds, and transactions made to wait briefly over time intervals. What that money buys is pushing ξ down.
Smaller Numbers Do Not Imply Earlier
Logical clocks guarantee one direction only: causally earlier means a smaller number. The converse fails — an event with a smaller number need not be a cause. It might be an unrelated old event on another machine.
What fixes the reverse direction is the vector clock: each machine keeps not a number but a table — "where each machine stands in my view." On receiving a message, take the per-entry maximum. Compare two tables and causality becomes visible immediately; even incomparability can be recognized at a glance. This was added independently by Mattern and Fidge around 1988. Later, the 1985 distributed snapshot algorithm (Chandy and Lamport) answered "how to take a global photo of a constantly changing system," using the same causal framework.
In 2013, Lamport received the Turing Award, with the citation explicitly naming "causality and logical clocks." The paper won the first Most Influential Paper award in distributed computing in 2000; a few years later the award was renamed after Dijkstra and continues annually. The copyright page of the paper still shows its original price: 75 cents.