Cairn
guides · cross-cutting lens, not tied to one category

↩ back to Guides

Safety vs. Liveness

Five of this site's eleven Concurrency entries — Peterson's algorithm, Dekker's algorithm, Lamport's bakery algorithm, the Dining Philosophers Problem, and the Readers-Writers Problem — each already prove a mix of two completely different kinds of claim about themselves, in their own Pitfalls and Complexity sections, without ever naming the distinction out loud. This page names it, and shows what falls out of lining all five up side by side: the two kinds of claim fail from unrelated causes and neither implies the other, and the stronger of the two kinds gets proven for free as long as there's exactly one shared resource and a process count fixed at two — a guarantee that stops being free the moment either of those two conditions is dropped.

Two kinds of claim

A safety property says a bad thing never happens: two processes are never both inside the same critical section at once. It's the kind of claim a single counterexample refutes — one reachable state where both flags are up disproves it outright, which is exactly what every exhaustive interleaving search on this site's three mutual-exclusion pages checks for, state by state. A liveness property says a good thing eventually happens: a process that wants in eventually gets in. No single state refutes a liveness claim — the violation is an entire infinite run that keeps dodging the good thing forever, which is why this site's own exhaustive searches check liveness a different way: by looking for a stuck state (nothing can move — a direct liveness failure) or by measuring how long a specific process can be made to wait before hitting a search's own bound, and arguing from there.

Both kinds of claim appear, unlabeled, in language this site's own pages already use. "Mutual exclusion holds" (Peterson's, Dekker's, Lamport's bakery) and "no violation of anything proven here" (Dining Philosophers) are safety claims. "Bounded waiting" (all three mutual-exclusion pages), "never deadlocks" (Dining Philosophers), and "every reader and writer eventually gets served" (the fair policy on Readers-Writers) are liveness claims. They read like two flavors of the same kind of promise. They are not — the next section is the site's own evidence for that.

The site's own proof they fail independently

Three separate pages on this site each weaken their own correct algorithm by removing one piece, then run the identical exhaustive search over the broken result. Lined up together, the pattern is exact: removing a turn-taking variable costs only liveness, and removing a self-trust variable (whether a process's own flag can be relied on) costs only safety — and the two never overlap, across three independently-written pages:

pagevariantwhat's removedsafety violationsstuck (liveness failure)
Peterson'sflag-onlyturn01 / 9 (by attempt count)
Peterson'sturn-onlyflag00 (1,1) → 1 (lopsided attempts)
Dekker'sno backoffturn-driven retry01 / 9 (by attempt count)
Dekker'sno re-raiseflag self-trust0 (1,1) → 1 / 10 (2,1 / 3,3)0
Lamport's bakeryno tie-breakdeterministic tie order1 / 9 (by attempt count)0
Lamport's bakeryno choosing flagflag self-trust1 / 35 (by attempt count)0

Every single broken variant across all three pages lands in exactly one column, never both. Peterson's own page draws the reason precisely: both of its broken variants "still give each process at least one real condition to check before entering" — the safety argument survives on whatever's left — but "what the removed variable was actually buying... was a way to guarantee the check eventually clears," which is a liveness guarantee, not a safety one. Dekker's own page draws the mirror version: its no-re-raise bug breaks "a single process's own flag no longer mean[ing] what the rest of the algorithm assumes it means" — a safety-only failure — while its no-backoff bug "only ever costs liveness... never a safety violation." Six independent broken variants, two independent authors' worth of design (Dekker's 1965, generalized by Peterson's 1981 and by Lamport's bakery 1974), zero exceptions.

Liveness splits in two once the resource shape changes

All three mutual-exclusion pages above solve the same shape of problem: a fixed number of processes (two, or n for the bakery algorithm) compete for one shared critical section. That shape has a convenient property: proving mutual exclusion and proving liveness turn out to be the same proof. Peterson's own Complexity section states it directly — bounded waiting "is a direct consequence of the same proof structure as mutual exclusion above, not a separate empirical claim" — and Dekker's and the bakery algorithm's own Complexity sections make the identical claim about themselves. Bounded waiting here is actually the stronger form of liveness: not just "the system as a whole keeps moving" (deadlock-freedom) but "this specific process never waits more than one bounded pass of its rivals" (starvation-freedom) — and it comes free, for all three, from a single resource shape simple enough that there's nowhere for a starvation case to hide.

Both of this site's other two Concurrency entries break that convenient shape on purpose, and the free corollary disappears in both directions at once — each page's own fix buys back only one of the two liveness properties, never both:

Put the two fixes next to each other and the asymmetry is the whole point: Dijkstra's resource-hierarchy rule is a structural argument about which pairs of resources a process can simultaneously want, and it has nothing to say about fairness. The fair ticket-order policy is entirely a fairness mechanism — bolted on top of an admission rule that was already deadlock-free without it — and it has nothing to do with resource ordering. Two different liveness diseases, two unrelated cures, on two pages that otherwise look like they're both just "fancier mutual exclusion."

Try it: the guarantee matrix

Every cell below is a claim some page on this site already proves about itself — nothing new is asserted here. Filter to see only the rows that have (or lack) a given guarantee.

Pitfalls

"Deadlock-free" does not mean "starvation-free," and the Readers-Writers Problem is this site's own clean counterexample. Readers-preference never once locks up — 0 stuck states in every configuration checked — while still letting a writer wait arbitrarily long. It is tempting to read "the system never gets completely stuck" as "every process is treated fairly eventually"; Readers-Writers' own measured tables are the direct refutation, not just a hypothetical one.

Bounded waiting (the mutual-exclusion pages' term) and starvation-freedom (the Readers-Writers page's term) are the same property under two names, but only once the processes being compared are interchangeable. Peterson's bounded wait is one competitor against one rival; Readers-Writers' starvation-freedom has to hold between two different classes of process (readers and writers) that don't play symmetric roles — which is exactly why a policy can be "fair" to one class and not the other (readers-preference, writers-preference) in a way that has no equivalent failure mode on a two-interchangeable-process page.

An exhaustive search proves a safety violation outright but can only extrapolate an unbounded liveness bound. A single reachable bad state disproves safety with certainty, at whatever size was searched. "Readers-preference's writer-starvation has no ceiling" is not proven that way — it rests on the measured bound scaling exactly with readers × attempts-each across every finite configuration tried, and reasoning from that pattern to "an unbounded supply of fresh requests gives an unbounded wait," the same honest extrapolation Readers-Writers' own Pitfalls section makes rather than a closed-form proof for every n at once. Worth remembering before citing either site's search result as settled with the same confidence: one kind of claim is airtight at the sizes checked, the other is a strongly-supported inference beyond them.