Specifying Correctness: Safety, Liveness and Invariants
Before anything can be proved, the claim has to be written down. A safety property says nothing bad ever happens and is refuted by a finite trace; a liveness property says something good eventually does and is not. An invariant is the safety property a proof actually uses.
What a learner can do afterwards
- Classify stated properties as safety or liveness and say what a counterexample to each looks like
- Write an invariant for a small algorithm and check that every step preserves it
- Say why a specification that only forbids things can be satisfied by doing nothing
1 · Read
After finding a valid schedule, you need words for what valid means. Safety says nothing bad ever happens, and one finite trace showing the bad thing refutes it. Liveness says something good eventually happens, and no finite snapshot refutes it, since the good thing could still arrive later.
Take a lock. Safety: two holders never hold it at once, refuted by one trace with both holding. Liveness: every requester eventually gets it, refuted only by a whole infinite wait, never by one snapshot of someone queueing.
An invariant is the safety property proofs actually use: true at the start and preserved by every step. Check each step keeps it true and induction covers all runs. If one step breaks it, the proof fails, so fix the step or choose a weaker claim that survives.
A specification that only forbids things is satisfied by doing nothing: never crash and never send holds of a dead program. Always pair safety with the liveness that demands progress, or your proof may bless an idle system.
Safety is refuted by one trace, liveness needs forever, invariants bridge to proof.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.