How do you take stock of a whole system that never stops moving, when no one can see all of it at once? And what can such a count reliably tell you?
We find out by exploring how ancient Greek trading houses, hearing that bandits were taking their carts, counted every jar they owned, including those in transit, without interrupting ongoing trades.
After K. Mani Chandy and Leslie Lamport, Distributed Snapshots: Determining Global States of Distributed Systems, 1985
Each link is an idea one paper took from another. Point at one, or tap it, to read how.
a paper this book retells a paper retold in another book a paper outside the series
A distributed system is many machines passing messages. Some questions about it need its global state: every machine's own state, plus the messages still on their way between machines.
No machine can see all the others. Reading them one after another gives a total that is wrong by whatever moved between one reading and the next, as the two machines here show. Stopping the whole system to look does work, but it is costly, and knowing that the channels have drained already needs a marker on every channel. One method records the state while the system runs.
The recorded state is one the system could have passed through, and that is enough for those properties. We tell it with three trading houses and their carts on the ring road of Arche.
Each machine holds 300 units. A is counted first, then B, and in between some units move.
House 1, House 2 and House 3 stand round the coast of Arche with a mountain between them. Carts and messengers go from house to house by the cliff road, and there are bandits about the island.
In a winter of busy trade, the three houses kept hearing that their goods had been stolen. A cart that left one house and had not come in at the next was said to have been taken on the cliff road, and no house could tell a cart that was taken from one that was only late.
To find out, the houses want to know how much grain and oil is really there, everywhere at once, to set against what the account scrolls say they should hold. Whatever falls short is what the bandits took.
The goods lie in two kinds of place. Some sit in the three storehouses. The rest are on the road, in carts and pack-trains that take as long as they take.*
The scribes' first plan is the plain one: send an auditor to each house, count each storehouse, and add the three counts. The recorder of the customs rolls sent the auditors out, went down to the cliff road to watch the carts pass, and came back to say that the plan would not do. Two mornings show why.
House 3's auditor counts at dawn and House 2's late in the day. In between, a cart carries two hundred jars of oil from House 3 to House 2. House 3 counted them before they left, and House 2 counts them again when they arrive. The total is two hundred jars too high, though nothing was added to the island.
The counts are taken as before, but the cart carries two hundred jars from House 2 to House 3. They left House 2's storehouse before its auditor looked, and had not reached House 3 when its auditor closed the slate. Nobody counted them. The jars have vanished from the total, and no bandit took them.
Counting the houses one after another is wrong by exactly the goods that moved along the road between one counting and the next. It can run either way, no one can say in advance by how much, and no account scroll shows that it happened.
On both mornings the auditors counted the storehouses rightly and the road wrongly. The goods that slipped through their counts were goods on the move, and a count taken house by house has no place to put them.
The plain remedy is to stop the road, so that nothing is on it to count.
Stopping the road is the houses' first thought. From a given morning no cart moves, every storehouse is counted while everything stands still, and then the trains move again. With nothing on the road, the three counts add up.
Two objections stand against the plan. The first is its price. The second can be answered, and answering it turns up a catch that changes the whole plan.
The houses feed the three port towns, and a road that stops moving food stops serving the island. A count that halts all trade will be tolerated once and never repeated.
The order to stop goes by messenger and takes as long as the road takes. House 2 may hear it before House 3, and House 3, knowing nothing, quite properly sends a cart. That does no harm. Each house stops sending when the order reaches it, keeps taking in whatever arrives, and counts when its incoming roads are empty. Houses that stop at different hours still give a true total, so long as each waits until nothing more is coming.
A house has to know that nothing more is coming. It cannot see the road, and a cart may be out round the next headland behind a lame mule. So each house, the moment it stops, sends down each of its roads a last messenger who means nothing behind me. Nobody overtakes, so when that messenger comes in, the road behind them is empty.
So stopping the island needs a messenger on every road anyway. The recorder of the customs rolls saw what follows from that. A messenger who can mark the end of a road's traffic for a stopped house can mark a place in that traffic for a house that keeps trading, and once the houses have such messengers they have no need to stop at all.
The accountant of House 1 took away a second burden. The stopped road was meant to catch the island at one instant, and the count need not do that. What the houses need is a total that is sound: no cart counted twice, none gone missing. Whether the total was ever true of the island at a single moment is a separate question, and the houses have no practical need to ask it.
The houses want a sound total, then, taken while the carts keep moving. The goods on the road are exactly what the auditors got wrong, and no house ever sees the road.
The goods on the road must first be admitted as part of what is counted. Each house thinks of its stock as what sits under its own roof. Oil in a cellar is stock, while oil in jars lashed to a mule on the cliff road is in no house's storehouse and on no house's slate. Yet it exists, it is owned, and it is exactly what the auditors counted twice or lost.
So the island is counted in nine places: the three storehouses, and, separately, what each of the six tracks is holding. Each house has a track to each other house, and each track carries only its own traffic.*
The picture shows all nine. Choose each in turn, and notice which of them a scribe could count from a desk.
Three storehouses and six tracks. Choose any of them.
Three of the nine can be counted from a desk, and the auditors counted only those. A method that records only the storehouses gives a complete account of a different island, one where carts take no time to travel. On Arche the six tracks have to be recorded as well.
A scribe at a desk cannot count a road. A cart rounding a headland is hidden behind rock, and nobody can post watchers along the surf. What a house can do is write down what comes in at its own gate. The recorder of the customs rolls saw that this is enough, provided the house knows exactly when to start writing down arrivals and when to stop.
When to start is easy: a house starts when it counts its own storehouse. When to stop is harder. Something has to tell a house, standing at its gate, that the last cart sent before the count has now come in.
The signal to stop is the same messenger the stopped road needed, now wearing a plain red sash. Nothing overtakes on a track, so when the sash comes in at a gate, everything sent down that track ahead of it has already arrived.
The messenger carries no goods, no orders and no tallies. The messenger's whole purpose is to divide what was sent down a track before the sash from what was sent after.
Two rules govern the sash, one for sending and one for receiving, and the rule of receiving depends on whether the house has already recorded. The three cards are the entire method.
A house records the inventory of its own storehouse. At once, before it sends any further cart or order down any road, it sends one messenger in a red sash down each of its roads.
The house records its storehouse at once, writes down that this road holds nothing, and then follows the rule of sending, with a sash down each of its own roads.
The house writes down, as that road's holding, every item that came in along that road between its own recording and this sash's arrival.
Any house may start the count, and it makes no difference which. No cart is delayed and no mule stopped, and no house needs to know another's stock. Scroll to watch one morning's count. Beside the picture, each house shows its stock, its record, and the slate it keeps for each incoming road.
Three storehouses, and two carts on the road. A cart of 30 jars is on the track from House 3 to House 2, and one of 10 on the track from House 2 to House 3. A coloured dot is a cart, and its number is the jars it carries.
House 3 sends a cart of 15 jars to House 2. Nobody has started a count. House 3 now holds 45.
House 1 writes down its stock, 100, and at once sends a messenger in a red sash down each of its roads, before anything else. The red dots are the sashes.
House 1 sends a cart of 20 jars to House 2. It holds 80 now, but its record says 100, so these jars are already counted at House 1. The cart cannot pass the sash.
The cart of 30 arrives, and then the sash. House 2 records 100, the 30 jars included. It writes that the road from House 1 holds nothing, and sends sashes down its own roads.
That slate is closed. The 20 jars were sent after House 1 recorded, so House 1 already counted them. House 2 does not count them again.
House 2 has recorded, and its slate for the road from House 3 is open. The cart of 15 arrives, and the slate says 15.
The sash from House 1 reaches House 3. It records 45, which leaves out the 15 already sent, writes that the road from House 1 holds nothing, and sends sashes of its own.
The cart of 10 from House 2 reaches House 3 after it recorded. Its slate for that road says 10.
The last sashes come in, and each closes the slate for the road it came along. Every slate is closed, and no cart stopped.
Three stocks and two slates: jars. Before anything began, the stocks and carts on the road came to . Nothing was bought, sold or taken on this day. No jar was counted twice and none was missed.
The second case of the rule of receiving does the work. A house that has recorded goes on taking in carts as usual, but from then on it keeps a slate for each incoming road, listing every jar and sack that arrives along it. When the sash comes through the gate, that road's slate is closed, and its sum is the road's holding. The house never saw the road. It only needed to know when to open the slate and when to close it, and the sash marked both.
The method relies on two things about the road.* Nothing overtakes on a track. A sash sent after a cart cannot pass that cart, and a cart sent after the sash cannot pass the sash, so the sash divides a track's traffic cleanly in two. Every sash arrives. A messenger with a sash and nothing on their back is not worth a bandit's while, and none falls from the cliff. If either fails, the count fails.
Carts are another matter, because bandits do take them. A taken cart does not spoil the count. Its jars leave the island's goods as surely as jars sold into a port town, and the count counts what is left. A taken messenger would spoil it, because the slate that messenger was to close would never be closed.
Each slate is closed by a sash, and every house records at its own hour. It remains to show that nine numbers taken at different hours fit together, and that the auditors' error cannot come back in another form.
To see whether the nine numbers fit together, draw the island's morning in the round: each house a line running outward, later moments further out, each cart an arc from its departure to its arrival.
The count draws a loop through each house at the moment it recorded. The recorder of the customs rolls called the loop a cut. Everything inside it is counted as past, and everything outside it comes after. The houses record at different moments, so the loop is not round.
A cart that leaves from inside the loop and arrives outside it was sent before its sender recorded and came in after its receiver recorded. Such carts are exactly the goods on the road, and the slates catch them. A cart that crosses the loop inward is the fatal error: goods received that, by the other house's record, had not yet been sent. Those jars stand in both records, which is the auditors' first morning over again.
The figure draws the morning of the red sashes, with its four carts. Choose any cart to see where its jars were counted. Then let each house count at an hour of its own choosing, and one cart crosses the loop inward.
Each line is one house. Each dot marks when that house recorded its storehouse, and the dashed loop joins the dots. Each arc is a cart, and the number is its jars.
Nobody has to watch for the inward crossing, because the rule of sending rules it out. A house sends the sash down a track before any further cart. No cart can overtake the messenger, so no cart sent after a house records can reach a neighbour before the sash does, and none can be counted as arrived before the neighbour recorded.
The count also finishes. Every house has a road to every other, so a sash sent by any one house reaches both the others. Each house that receives one records and sends sashes down all its roads. The island is finite and every messenger arrives in the end, so every house records and every slate is closed.
No cart is counted twice, none is lost, and the count ends. The nine numbers therefore describe the island. At what moment they describe it is still to be said, since each house recorded at a different hour.
The marker-sending rule: a process records its state, then sends a marker on each outgoing channel before sending any further message on it. The marker-receiving rule: on receiving a marker, a process that has not recorded records its state, and a process that has recorded closes that channel's record. Channels are FIFO and every marker arrives. Claim. No message is sent after its sender recorded and received before its receiver recorded.
The nine numbers describe the island at no single moment. When they came in, the recorder of the customs rolls summed them for the houses, and then showed that the total described a morning the island never had.
House 1 recorded first and House 2 some while later. Soon after House 1 recorded, it sold forty jars of oil into its own port town. Later, and still before House 2 recorded, House 2 milled eighty measures of barley into flour. Neither touched a road, a cart or a sash.
So the total describes an island in which House 1 still holds the forty jars and House 2 has already milled its barley. The island was never in that state. While House 1 still held the jars, the barley was not yet milled, and by the time it was, the jars were gone.
The four entries are set out below in the order they were lived. Put the milling ahead of the sale, and see which of the two mornings passes through the picture the count recorded.
The total is still not false, and saying why takes three names. Call the island as it stood when the count began its start, the island as the scribes recorded it the recorded island, and the island when the last slate closed its end.
First, the recorded island can be reached from the start by the very events that happened, taken in an order that keeps every chain of carts and messengers intact. Second, the end can be reached from the recorded island by the rest of those same events.
So the recorded island lies on a lawful path from the start to the end. It is not an idle fiction. It is a state Arche could have passed through, had independent events on opposite sides of Mount Phyle come in another, equally lawful order.
The count may reorder the sale and the milling because nothing joins them. Neither touched a road, so neither could have known of the other. Two events at different houses with no chain of messengers between them stand in no natural order,* and the count may take either first. What it may never do is reverse events that one chain of messengers joins, and the red sash sees to it that it never does.
The houses hold a morning that could have happened and did not. What they can do with such a total is the last thing to settle.
Let Sbegin be the global state when the snapshot was initiated, S* the global state recorded, and Send the global state when the last channel's record was closed. Theorem. (1) S* is reachable from Sbegin by a valid execution sequence consisting of the events that actually occurred, in an order that preserves causality. (2) Send is reachable from S* by the remainder of those events. Hence S* lies on a valid path from Sbegin to Send.
“You asked for a morning, and I have given you a morning. It is only not the particular morning you lived through.”
What the recorder of the customs rolls told the houses
A total that describes a morning nobody lived through is good for some questions and useless for others, and it is best to start with what it cannot do. If a merchant swears that House 2 held three hundred jars of oil at the moment a ship dropped anchor, the count cannot settle it. The count was taken at no one moment, so it cannot speak for that moment.
The questions it can answer are those whose answer, once it becomes true, stays true for ever. The recorder of the customs rolls called these settled properties. Counting only the trade between the houses, with the port towns' buying and selling set aside, some examples are:
For these, the count decides. If the property holds on the recorded island, it holds on the island now, because the end can be reached from the recorded island and a settled property, once true, remains true. If it does not hold there, it did not hold when the count began, because had it held at the start, it would still hold on the recorded island.
Either way, the count gives a sure answer about a real state of the island. That the recorded island itself never happened does not matter, because a settled property cannot tell the path the island took from a path it could have taken.
The houses' own question, whether the bandits have robbed them, is of this kind on the right day. Below, the count is taken on a day with no buying or selling. Choose when a bandit takes one cart off the road, and compare what the count says with how the island stood when the count began and when it ended.
The account scrolls say the houses hold 270 jars between them. Choose when a bandit takes one cart of 30 jars off the road.
The count can answer the houses' own question because it gives a sound inventory, with no jar lost and none counted twice. A cart that was only late turns up on a road slate and is counted. A cart that was taken turns up nowhere.
So the houses take their count on a day when nothing is bought from or sold into the port towns. Then goods only move between the houses, and every move takes jars from one of the nine places and adds the same jars to another. Only the bandits can change the total. The account scrolls say what the houses should hold between them, and the houses set the count against it. A shortfall is a deficit, and a deficit is settled. If the count shows one, the houses have been robbed, and the shortfall is what the bandits hold now. If it shows none, nothing had been taken when the count began.
On a day of buying and selling, the account scrolls move with every sale, and the recorded total is true of the recorded island and of no moment anyone lived through. What was true at one particular moment, nothing on an island without a common hour will ever tell.
A property y is stable if for every state S where y(S) holds, y(S') holds for all states S' reachable from S. Let Sbegin, S* and Send be as in the theorem. Rule. Evaluate the stable property y on S*. If y(S*) is true, then y(Send) is true. If y(S*) is false, then y(Sbegin) is false.
Examples counting only the trade between the houses: distribution termination (every cart has arrived and all houses are idle), deadlock (every house is blocked waiting for carts from another), exhaustion of supply, and deficit.
Read the island again with machines in the storehouses. Every house is a process, every track is a channel, and the messenger in the red sash is a marker. Hover over a row, or tap it, to see who is who.
A running system can be recorded without stopping it, in a state it may never have passed through but could have.
Because that state lies on a lawful path from the start to the end, it settles every question whose answer, once true, stays true.
Distributed snapshots are still how running systems record a global state without halting, for instance in Apache Flink.
Setting The Ring Road
The system is a set of processes (the houses) connected by directed channels (the one-way tracks of the ring road). A channel delivers messages in the order sent (FIFO), without corruption, after an arbitrary but finite delay, and never loses a marker. There is no shared clock, and no process can directly observe another's state. A global state consists of the local state of every process together with the state of every channel.
The paper behind this book. K. Mani Chandy and Leslie Lamport, “Distributed Snapshots: Determining Global States of Distributed Systems,” ACM Transactions on Computer Systems 3, 1 (February 1985), 63–75. The definition of global state, the marker rules, the theorem, and the detection of stable properties.
The ideas. A distributed system has no single vantage point from which its total state can be observed simultaneously. Halting all processes and waiting for the channels to drain does work, but it is costly, and detecting the drain already needs a marker on every channel. The Chandy–Lamport snapshot algorithm records a consistent global state, both process states and channel states, while normal computation proceeds uninterrupted.
By dispatching markers along all outgoing channels immediately upon recording local state, and before sending further application messages, processes partition each channel's stream. Because channels are FIFO, markers cannot overtake messages, and messages cannot overtake markers. This guarantees that no message sent after a sender records can be received before a receiver records, the fundamental condition of cut consistency.
The resulting snapshot S* may never have occurred in physical time. However, it is causally valid: reachable from the initial state Sbegin, with the final state Send reachable from it. This makes it sufficient to evaluate stable properties like deadlock, garbage collection, and termination: if the property holds in S*, it holds in the running system.
Chandy, K. M., and Lamport, L. Distributed snapshots: determining global states of distributed systems. ACM Trans. Comput. Syst. 3, 1 (1985), 63–75.