--- title: "Specifying Correctness: Safety, Liveness and Invariants" description: "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 do" canonical: https://lightmysky.com/learn/computing/specifying-correctness-safety-liveness-and-invariants-mt_4_KaoDSHZF source: https://lightmysky.com/learn/computing/specifying-correctness-safety-liveness-and-invariants-mt_4_KaoDSHZF.md retrieved: 2026-11-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # 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. Subject: Computing · Area: Software Engineering · Ages 22 to 24 Page: https://lightmysky.com/learn/computing/specifying-correctness-safety-liveness-and-invariants-mt_4_KaoDSHZF ## Ready when they can - 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 ## Lesson: Forbid the bad, demand the good 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. **Example.** 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. **Recap.** A finite trace can refute safety. Refuting liveness requires an infinite trace. Invariants help prove safety properties. ## Practice 8 questions on this page, each with its working shown. ## Needs first - [SAT Solvers and What Makes Search Practical](https://lightmysky.com/learn/computing/sat-solvers-and-what-makes-search-practical-mt_d46m2LD443) ## Optional connections - [Property-Based Testing](https://lightmysky.com/learn/computing/property-based-testing-mt_QqCNKT06IY) ## Opens up - [Model Checking and the State-Space Explosion](https://lightmysky.com/learn/computing/model-checking-and-the-state-space-explosion-mt__pgZ0PzEZo)