Safety and Liveness

Two families hold every correctness property ever stated. A safety property says nothing bad ever happens: a quiet, uneventful room is perfectly safe, and the promise must hold at every instant of every execution. A liveness property says something good eventually happens: a busy pub is lively because, over time, good things do — the promise says nothing about any single instant, only about the limit. Consistency is the textbook safety property — every response a client receives is correct — and availability is the textbook liveness property — every request eventually receives a response. Name the two families and the theorem stops being about storage.

Because consistency and availability are one of each, the CAP theorem is not a special law of registers; it is one instance of the oldest fact in distributed computing — safety and liveness cannot both be guaranteed in an unreliable system. The register under CAP is the gentlest witness: a single atomic read/write cell, the smallest object that still needs coordination. The impossibility is a family trait, not a quirk of the example — its sharper cousin is consensus, whose agreement and validity are safety and whose termination is liveness, and which Fischer, Lynch, and Paterson proved impossible with a single crash and no partition at all.

The two families are not mirror images, and the difference is where the network gets its leverage. A safety violation is local in time: it happens at one instant, so a finite prefix of the run already proves the property broke — answer a read wrongly once and consistency is gone forever. A liveness violation is global in time: no finite prefix can prove it, because "eventually" always has more time to be redeemed — availability fails only in the limit, when the answer truly never comes. An unreliable network can force either break: cut the link and a server that answers risks the safety break, while a server that waits walks into the liveness break. The theorem is the observation that under a partition these two exits are the only two, and they point opposite ways.

This is why the sharper result matters. Fischer, Lynch, and Paterson removed the partition entirely and kept only a single crash — the most benign failure imaginable — and still found an execution in which a consensus protocol never terminates. Consensus asks for strictly more safety than a register does (agreement plus validity, versus one correct value), so its impossibility implies the register's: if you cannot agree under one crash, you certainly cannot stay both consistent and available under a partition. CAP is the gentle face of a hard law, and owning it starts with reading the law's shape — two families, one collision — rather than the storage-flavored slogan.

The property rule — consistency is a safety promise (nothing bad, at every instant); availability is a liveness promise (something good, in the limit); no unreliable system keeps both. Say it and the theorem stops being about databases and becomes about the two families every correctness property belongs to — and the network that is built to break one or the other, never letting you keep both.