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 fails, but only on states that cannot be reached. What should you do?

    • Recheck the base case and keep the same preservation argument
    • Strengthen the auxiliary invariant to exclude those states
    • Check more reachable steps and keep the same preservation argument

  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 ban on another kind of bad message
    • A longer finite trace

  7. A counter starts at 0 and each step adds 3. Which invariant fits this counter?

    • The count is even
    • The count is a multiple of 3
    • The count is less than 10

  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. Strengthen the auxiliary invariant to exclude those states · The base case already holds. More examples do not repair preservation. Add the even-count invariant to exclude 1, then prove the combined claim is preserved.
  5. Liveness · It demands a good event eventually.
  6. Liveness for progress · A program can satisfy this ban by doing nothing. Requiring eventual progress rules out that behavior.
  7. The count is a multiple of 3 · The initial count, 0, is a multiple of 3. Adding 3 to a multiple of 3 gives another multiple of 3.
  8. The waiter might still be served later · The requester could still be served later. One snapshot does not show an infinite wait.
Worksheet · LightMySky