Specifying Correctness: Safety, Liveness and Invariants · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

Forbid the bad, demand the good

Computing · Software Engineering · ages 22-24
Name ______________________   Date ____________

  1. "Two holders never hold the lock at once" is which kind?

    • A performance goal
    • A liveness property
    • A safety property

  2. Which kind of property is refuted by a single finite trace?

    • Safety
    • Liveness
    • Neither kind

  3. An invariant must hold at the start and survive every step.

    Circle one:   True   False

  4. Your proof step breaks the invariant. What must happen?

    • Ship the proof anyway
    • Fix step or weaken claim
    • Drop the base case instead

  5. "Every request is eventually answered" is which kind?

    • An invariant
    • Safety
    • Liveness

  6. A dead program never sends a bad message. What is missing from that spec?

    • Liveness for progress
    • A stronger safety ban
    • A longer finite trace

  7. A counter starts at 0 and each step adds 2. Is "the count is even" preserved?

    • No, 0 is not even
    • Yes, +2 stays even
    • Only on steps that add 4

  8. Jo shows one snapshot of a waiting requester and claims liveness refuted. What is wrong?

    • Snapshots can only prove liveness
    • The waiter might still be served later
    • Waiting requesters prove safety instead
LightMySky · lightmysky.comW1-mt_4_KaoDSHZF-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

Forbid the bad, demand the good W1-mt_4_KaoDSHZF-s1

  1. A safety property · It forbids a bad state outright.
  2. Safety · The trace exhibits the bad thing happening.
  3. True · Both checks together power the induction.
  4. Fix step or weaken claim · A broken link voids the induction.
  5. Liveness · It demands a good event in the fullness of time.
  6. Liveness for progress · Pure prohibition blesses idleness.
  7. Yes, +2 stays even · The start is even and each step keeps it even.
  8. The waiter might still be served later · Refuting eventually needs forever, not a moment.
Worksheet · LightMySky