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 true at the start and preserved by every step. Start at 0 and add 2 each step, so reachable counts are 0, 2, 4, and so on. To prove the count is never 3, try 'the count is never 3' alone: from 1, adding 2 reaches 3, so preservation fails. But 1 cannot be reached. If it failed on a reachable count, fix the step. Strengthen the auxiliary invariant to 'the count is even', which excludes 1. The combined claim is preserved, and the safety claim is unchanged.
A program that sends no messages satisfies a ban on bad messages, even if it does nothing. This does not hold for every safety property. A deadline or a ban on idling while work is pending can be violated by doing nothing. For the message-ban example, add a requirement that requests eventually receive replies. The specification must require the progress the system is meant to make.
A finite trace can refute safety. Refuting liveness requires an infinite trace. Invariants help prove safety properties.
2 · Watch
En anglaisTake it off screen
Where it sits
Learn first
Optional connections
This opens up
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.