Atomicity becomes an availability liability

Why does unanimity make atomic commit multiply unavailability, and which impossibility results bound every protocol?

CaseConstructed case · Tomas at Kestrel Tickets

Charged twice, or a seat with no e-ticket

Buying a ticket at Kestrel is now three steps in three systems:

order-service reserves the seat in orders-db.
payment-service charges the card through an external card gateway.
The order is announced on the event-bus ("order paid"), and the e-ticket service emails the e-ticket.

After a crash of payment-service during a busy evening, support receives two kinds of tickets. Some customers were charged twice. Some customers have a seat but no e-ticket. Tomas proposes a clean fix: "Let us just use two-phase commit across all of it, so it all happens or none of it does." Lena does not say no. She takes a pen and computes the lock hold time and the availability 0.999ⁿ. After five minutes the proposal is withdrawn. This article shows her arithmetic and what Kestrel does instead.

How it ends →

Distribution turns atomicity into an availability liability

In Transaction mechanics the designated atomic event and the writes it spoke for shared fate: one node, one log, one crash. Recovery could always find the designated record. The thing that lost the writes also lost the record, and the thing that kept the record also kept the writes.

Distribution breaks exactly that. The writes now sit on machines that fail independently of the machine holding the decision. "Atomicity over n items is atomicity over one item" still applies, since one designated write still means all the others, but the designated write can now be reached only through a message that may not arrive. Distribution does not change how atomicity is implemented. It converts atomicity from a correctness mechanism into an availability liability.

Two impossibility results

Two results bound every protocol in this article. State them first.

The Two Generals problem. No finite number of messages over an unreliable channel gives two parties certainty that the other acted, because the last message can always be lost; this is why exactly-once delivery does not exist.
Skeen's result. No atomic commit protocol is both safe and non-blocking in an asynchronous system with failures. (An asynchronous system is one where messages can take any amount of time, so a slow node cannot be told apart from a dead one.) Safe means no two participants decide differently; non-blocking means survivors can always finish without waiting for the failed node to come back.

Every mechanism below chooses which one to bend and decides who pays.

Consensus needs a majority; atomic commit needs unanimity

Consensus is the problem of getting several machines to agree on one value (used for replication, leader election). Its validity condition is "the decided value was proposed by someone". So any majority can decide, and a minority can be ignored. Atomic commit is the problem of getting all participants to either commit or abort a transaction together. Its validity condition is "commit if and only if every participant voted yes", because any single participant might have a local reason to refuse: a constraint violation, a lock conflict, a full disk. That stronger condition is not a detail. It is the entire cost.

	Consensus over 5 replicas	Atomic commit over 10 participants
Decision rule	Majority (3 of 5)	Unanimity (10 of 10)
Availability at 0.999 each	~0.99999999	0.999¹⁰ ≈ 0.99
Effect of one unreachable node	None	Abort at best, block at worst

Worked arithmetic for the right column: each participant is up 99.9% of the time. All ten must be up: 0.999¹⁰ = e^(10 × ln 0.999) ≈ e^(−0.01) ≈ 0.990. Downtime grows from 0.1% to 1%, which is ten times the downtime of one component, from the same components, purely because of the decision rule. (For the left column, five replicas at 0.999 that fail only when three or more are down give about 1 − 10 × 0.001³ = 0.99999999 under an independent model; correlated failures make the real figure lower.) Aⁿ also assumes that participants fail independently, and in reality they share racks, zones, deploys and configuration. For a unanimity protocol, correlation reduces how often you block (failures arrive together) while making each episode larger and simultaneous: the independent model is pessimistic about frequency and optimistic about severity, the opposite of its effect on quorum systems. Independence is assumed and false, and it does not always fail in the direction you expect.

Two-phase commit is not "consensus with two rounds". The confusion is common, and it hides the one number that matters.

RelationshipUnanimity multiplies unavailability →

0.99 9^{10} \approx 0.990

$A$: availability of one participant
$n$: participants that must all be up

each 99.9%each 99.99%

Data table

Availability of an all-participants commit, by participants
Participants n	series	Availability
1	each 99.9%	99.9%
1.05	each 99.9%	99.9%
1.1	each 99.9%	99.9%
1.16	each 99.9%	99.9%
1.22	each 99.9%	99.9%
1.28	each 99.9%	99.9%
1.34	each 99.9%	99.9%
1.41	each 99.9%	99.9%
1.48	each 99.9%	99.9%
1.55	each 99.9%	99.8%
1.63	each 99.9%	99.8%
1.71	each 99.9%	99.8%
1.8	each 99.9%	99.8%
1.89	each 99.9%	99.8%
1.98	each 99.9%	99.8%
2.08	each 99.9%	99.8%
2.19	each 99.9%	99.8%
2.3	each 99.9%	99.8%
2.41	each 99.9%	99.8%
2.53	each 99.9%	99.7%
2.66	each 99.9%	99.7%
2.79	each 99.9%	99.7%
2.93	each 99.9%	99.7%
3.08	each 99.9%	99.7%
3.23	each 99.9%	99.7%
3.4	each 99.9%	99.7%
3.57	each 99.9%	99.6%
3.74	each 99.9%	99.6%
3.93	each 99.9%	99.6%
4.13	each 99.9%	99.6%
4.34	each 99.9%	99.6%
4.55	each 99.9%	99.5%
4.78	each 99.9%	99.5%
5.02	each 99.9%	99.5%
5.27	each 99.9%	99.5%
5.54	each 99.9%	99.4%
5.81	each 99.9%	99.4%
6.11	each 99.9%	99.4%
6.41	each 99.9%	99.4%
6.73	each 99.9%	99.3%
7.07	each 99.9%	99.3%
7.43	each 99.9%	99.3%
7.8	each 99.9%	99.2%
8.19	each 99.9%	99.2%
8.6	each 99.9%	99.1%
9.03	each 99.9%	99.1%
9.48	each 99.9%	99.1%
9.96	each 99.9%	99%
10.5	each 99.9%	99%
11	each 99.9%	98.9%
11.5	each 99.9%	98.9%
12.1	each 99.9%	98.8%
12.7	each 99.9%	98.7%
13.4	each 99.9%	98.7%
14	each 99.9%	98.6%
14.7	each 99.9%	98.5%
15.5	each 99.9%	98.5%
16.2	each 99.9%	98.4%
17.1	each 99.9%	98.3%
17.9	each 99.9%	98.2%
18.8	each 99.9%	98.1%
19.7	each 99.9%	98%
20.7	each 99.9%	97.9%
21.8	each 99.9%	97.8%
22.9	each 99.9%	97.7%
24	each 99.9%	97.6%
25.2	each 99.9%	97.5%
26.5	each 99.9%	97.4%
27.8	each 99.9%	97.3%
29.2	each 99.9%	97.1%
30.7	each 99.9%	97%
32.2	each 99.9%	96.8%
33.8	each 99.9%	96.7%
35.5	each 99.9%	96.5%
37.3	each 99.9%	96.3%
39.2	each 99.9%	96.2%
41.1	each 99.9%	96%
43.2	each 99.9%	95.8%
45.3	each 99.9%	95.6%
47.6	each 99.9%	95.3%
50	each 99.9%	95.1%
1	each 99.99%	100%
1.05	each 99.99%	100%
1.1	each 99.99%	100%
1.16	each 99.99%	100%
1.22	each 99.99%	100%
1.28	each 99.99%	100%
1.34	each 99.99%	100%
1.41	each 99.99%	100%
1.48	each 99.99%	100%
1.55	each 99.99%	100%
1.63	each 99.99%	100%
1.71	each 99.99%	100%
1.8	each 99.99%	100%
1.89	each 99.99%	100%
1.98	each 99.99%	100%
2.08	each 99.99%	100%
2.19	each 99.99%	100%
2.3	each 99.99%	100%
2.41	each 99.99%	100%
2.53	each 99.99%	100%
2.66	each 99.99%	100%
2.79	each 99.99%	100%
2.93	each 99.99%	100%
3.08	each 99.99%	100%
3.23	each 99.99%	100%
3.4	each 99.99%	100%
3.57	each 99.99%	100%
3.74	each 99.99%	100%
3.93	each 99.99%	100%
4.13	each 99.99%	100%
4.34	each 99.99%	100%
4.55	each 99.99%	100%
4.78	each 99.99%	100%
5.02	each 99.99%	99.9%
5.27	each 99.99%	99.9%
5.54	each 99.99%	99.9%
5.81	each 99.99%	99.9%
6.11	each 99.99%	99.9%
6.41	each 99.99%	99.9%
6.73	each 99.99%	99.9%
7.07	each 99.99%	99.9%
7.43	each 99.99%	99.9%
7.8	each 99.99%	99.9%
8.19	each 99.99%	99.9%
8.6	each 99.99%	99.9%
9.03	each 99.99%	99.9%
9.48	each 99.99%	99.9%
9.96	each 99.99%	99.9%
10.5	each 99.99%	99.9%
11	each 99.99%	99.9%
11.5	each 99.99%	99.9%
12.1	each 99.99%	99.9%
12.7	each 99.99%	99.9%
13.4	each 99.99%	99.9%
14	each 99.99%	99.9%
14.7	each 99.99%	99.9%
15.5	each 99.99%	99.8%
16.2	each 99.99%	99.8%
17.1	each 99.99%	99.8%
17.9	each 99.99%	99.8%
18.8	each 99.99%	99.8%
19.7	each 99.99%	99.8%
20.7	each 99.99%	99.8%
21.8	each 99.99%	99.8%
22.9	each 99.99%	99.8%
24	each 99.99%	99.8%
25.2	each 99.99%	99.7%
26.5	each 99.99%	99.7%
27.8	each 99.99%	99.7%
29.2	each 99.99%	99.7%
30.7	each 99.99%	99.7%
32.2	each 99.99%	99.7%
33.8	each 99.99%	99.7%
35.5	each 99.99%	99.6%
37.3	each 99.99%	99.6%
39.2	each 99.99%	99.6%
41.1	each 99.99%	99.6%
43.2	each 99.99%	99.6%
45.3	each 99.99%	99.5%
47.6	each 99.99%	99.5%
50	each 99.99%	99.5%

Stated in 4 places →Principle: Independence is assumed →

Distributed atomicity is the local trick performed at a distance, and the distance converts the designated write from a bookkeeping device into a single point of reachability.