Two-Phase Commit
To make several machines agree on a change, ask them all to promise first and only then tell them to go through with it. The promise is what makes it work, and the promise is also the trap: a machine that has promised may not back out, and may not proceed either, until somebody tells it which. If nobody can, it waits, and no length of time helps: what it needs is not more patience but an answer that is no longer reachable.
New to distributed transactions? Start here
One machine changing its own data can do it all at once or not at all, because it controls the only copy. Several machines cannot: each can only speak for itself, and any of them can fail between one message and the next.
So the work is split in two. First everybody is asked to promise they can go through with it, and says yes or no. Only if all say yes is anybody told to actually do it. That promise is what makes the change atomic, and it is also what creates the failure this page is about, because a machine that has promised has given up the right to decide for itself.
A message that takes time and may not arrive
Two computers in one room are far apart by a processor's standards. A message crossing between them takes time you cannot argue with, and across a continent that floor is set by the speed of light in glass.
Worse, it may arrive after a message sent later, or arrive twice, or never arrive at all, and the sender is not told which. There is no moment at which both ends know the same thing. Every machine in this topic is a way of getting useful work done anyway, without that guarantee, and the ones that look overcomplicated are usually the ones that stopped pretending.
The machine for this idea on its own is Packet Switching, if you would rather press it than read about it.
Everyone promises before anyone acts
1 A choice of which failures to consider: the coordinator alone, or any combination
The coordinator's timeline, one row per instant at which it could stop. Every verdict below is computed by classifying that state, not looked up.
2 The coordinator's timeline, with the outcome computed at every instant it could stop
Only the coordinator has failed; every participant is still running and they can talk to each other.
| instant | it stopped | outcome |
|---|
3 The whole crash space, grouped by how many participants went down with it
The whole space: the coordinator stopped somewhere, and some set of participants is down with it. Grouped by how many participants are missing, because that is the axis along which asking a neighbour stops helping.
| participants also down | configurations | blocked | share |
|---|
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| every crash configuration is classified, and the two verdicts partition the space | yes | 72 configurations = 9 coordinator crash points x 8 subsets of participants that may also be down; 22 blocked, 50 safe |
| a protocol whose happy path is four messages has configurations it cannot finish | yes | 22 of 72 configurations leave a participant that has voted yes with no lawful move while the coordinator is away; the wait is unbounded rather than eternal, because a coordinator returning with its log ends it at once |
| with only the coordinator down the window is narrow and it is not empty | yes | 2 of 9 single-failure points block, and they are the two between the last vote arriving and the decision reaching anybody |
| a coordinator that dies before asking anything costs nothing | yes | no participant is prepared, so every one of them times out and aborts, which is always a legal outcome |
| one participant that heard the decision is enough to save the others | yes | as soon as a single participant knows, the survivors ask it rather than the coordinator; this is what keeps the window to two points instead of the whole protocol |
| and it stops working the moment that one participant is down too | yes | 20 of the blocked configurations are ones where somebody did know the decision and is no longer reachable |
| no timeout closes the window, because the question is not how long to wait | yes | a prepared participant may not abort, since the decision may have been commit, and may not commit, since it may have been abort; waiting longer does not make the answer knowable |
| three-phase commit is not the fix, and this page does not offer it as one | yes | it removes the blocking only by assuming the network never partitions, which is the assumption that fails in practice; trading a blocking protocol for one that can decide inconsistently is a different bargain, not a solution |
What is real here, and what is not
Every participant votes yes here, and a real one might not
A no vote makes the whole thing easy: the coordinator aborts and nobody is stuck, because abort is always a legal outcome for a participant that has not promised. The interesting states are the ones reached after everybody has promised, so that is what the enumeration covers. It is the hard half, not the whole protocol.
The blocked count depends on the number of participants, and three is a model
Seventy-two configurations is three participants. More participants means more places to crash and more subsets that can be missing, so the raw count is not a constant of the protocol. What does not change is that the blocked set is never empty, and that is the claim being made.
Cooperative termination is assumed, and it is not free
The classifier lets a surviving participant ask another one what the decision was, which is why the window is narrow rather than the whole protocol. Real implementations have to build that, keep the addresses of the other participants, and handle a neighbour that is itself uncertain. Assuming it makes the protocol look better here than a naive implementation would be.
Blocked means unbounded, which is not the same as forever
A participant in the blocked state is holding locks and waiting for information no survivor has. It is not that the timeout is too short: there is no length of time after which the answer becomes knowable from what is present, which is the difference between this and an ordinary retry. But unbounded is not permanent, and an outside review was right to press on the distinction. A coordinator that comes back with its log ends the wait immediately, because the decision was written down before it died. What the protocol cannot promise is any bound on when that happens, and a system holding locks meanwhile is stuck for as long as it takes.
Three-phase commit is not offered as the fix
It removes the blocking by assuming the network never partitions. That is precisely the assumption that fails in practice, and a protocol that can decide two different things in two halves of a split network is worse than one that stops. Presenting it as the answer is the common overclaim this page exists to avoid, so it is named and left alone.
1978 is the first publication, not necessarily the invention
Gray's chapter is the first published description. Butler Lampson and Howard Sturgis wrote one in 1976 at Xerox PARC that was never published, and Gray cites them. Where credit is contested this site says so rather than picking the tidier story.
Which of these sources were actually read
Gray's chapter was retrieved as a publisher landing page rather than the text, and Skeen and Stonebraker is behind the ACM sign-in. Both are verified against Crossref. The protocol modelled here is the standard one and the enumeration is this page's own work, so nothing on it rests on a sentence read in either paper.
Sources
- Jim Gray, Notes on Data Base Operating Systems, in Operating Systems: An Advanced Course, Lecture Notes in Computer Science 60:393-481, Springer, 1978.
- Dale Skeen and Michael Stonebraker, A Formal Model of Crash Recovery in a Distributed System, IEEE Transactions on Software Engineering SE-9(3):219-228, May 1983.
- Logical Art, the studio this belongs to.