Communications of the ACM

execution rule.

Now, in the East Coast datacenter, the operations can appear only in an order that agrees with causality:

Op1 [Alice uploads photos.] Then

Op1 [Alice uploads photos.]

Op2 [Alice creates an album.] Then

Op1 [Alice uploads photos.]

Op2 [Alice creates an album.]

Op3 [Alice adds photos to the album.] but never in a different order that results in an empty album or complicates what a programmer must think about.

What causal consistency cannot do. Anomaly 4 represents the primary limitation of causality consistency: it cannot enforce global invariants. Anomaly 4 has an implicit global invariant—that bank accounts cannot go below $0— that is violated. This invariant cannot be enforced in an ALPS system. Availability dictates that operations must complete, and low latency ensures they are faster than the time it takes to communicate between datacenters. Thus, the operations must return before the datacenters can communicate and discover the concurrent withdrawals.

True global invariants are quite rare, however. E-commerce sites, where it seems inventory cannot go below 0, have back-order systems in place to deal with exactly that scenario. Even some banks do not enforce global $0 invariants, as shown by a recent concurrent withdrawal attack on ATMs that extracted $40 million from only 12 account numbers. 14

tion and b is a read operation that returns the value written by a, then a → b.

3. Transitivity. For operations a, b, andc, if a → b and b → c, then a → c. Thus, the causal relationship between operations is the transitive closure of the first two rules.

Causal consistency ensures operations appear in an order that agrees with these rules. This makes users happy because their operations are applied everywhere in the order they intended. It makes programmers happy because they no longer have to reason about out-of-order operations.

Causal consistency prevents each of our first three anomalies, turning them into regularities.

Regularity 1: No Missing Comments In the West Coast datacenter, Alice posts, and then she and Bob comment:

Op1 Alice: I’ve lost my wedding ring.

Op2 Alice: Whew, found it upstairs.

Op3 [Bob reads Alice’s post and comment.]

Op4 Bob: I’m glad to hear that.

Op1 → Op2 by the thread-of-execu-tion rule; Op2 → Op3 by the reads-from rule; Op3 → Op4 by the thread-of-execu-tion rule.

Write operations are only propagated and applied to other datacenters, so the full causal ordering that is enforced is Op1 → Op2 → Op4.

Now, in the East Coast datacenter, operations can appear only in an order that agrees with causality. Thus:

Op1 Alice: I’ve lost my wedding ring.

Then

Op1 Alice: I’ve lost my wedding ring. Op2 Alice: Whew, found it upstairs. Then

Op1 Alice: I’ve lost my wedding ring. Op2 Alice: Whew, found it upstairs. Op4 Bob: I’m glad to hear that.

but never the anomaly that makes Bob look unkind.

Regularity 2: No Leaked Photos3

In the West Coast datacenter, a grad student carefully deletes incriminating photos before accepting an advisor as a friend:

Op1 [Student deletes incriminating photos.]

Op2 [Student accepts advisor as a friend.]

Op1 → Op2 by the thread-of-execu-tion rule.

Now, in the East Coast datacenter,
operations can appear only in an order
that agrees with causality, which is:
Then
[Student deletes incriminating
photos.]
[Student accepts advisor as a friend.]
but never the anomaly that leaks pho-
tos to the student’s advisor.