When a written invariant resists a direct argument, how do you decide between pressing for a contradiction proof and hunting a counterexample?
answer
- one activity, seen from two ends
- the stall describes the witness
- near misses name the missing hypothesis
- stop by what depends on the claim
- keep the assumptions, not the verdict
basics
~10 sRun both and let each steer the other: where the argument stalls names the state worth searching, and a near-miss witness names the missing hypothesis. Spend according to what else rests on the claim.
solid answer
~50 sTreating these as rival activities is the mistake. They are one activity seen from two ends, and the information flows both ways. When the argument stalls, the stall is a **description of the witness you are looking for** — the case the reasoning cannot rule out. When a hunt produces runs that almost violate the claim, the gap between them and a real violation is **the missing hypothesis**. The decision that genuinely belongs to a lead is where to stop. A negative safety claim other components are written against — no block handed out twice, no committed write lost — earns a written argument, because tests sample runs and the claim quantifies over all of them. A claim that only affects one component's internals, or that is cheap to enforce at runtime, does not: state it, guard it, and move on.
go deeper
Recall that an open claim has two fates, established or refuted, and that looking for a counterexample is a legitimate first move rather than an admission that you cannot argue it.
Be able to use one attempt to steer the other: turn the step where reasoning stalls into a description of the run to search for, and turn near misses into the hypothesis the claim is missing.
Show that you audit the outcome rather than the verdict: which assumptions the argument needed, which witnesses failed and why, and whether the final wording is the claim that was originally asserted.
Own the stopping rule. Decide which claims other components may be written against, which are better enforced at runtime than argued, and how much a silent violation would cost before anyone spends a day on either attempt.
## Why the two attempts are one activity An open claim has exactly two possible fates: it is established, or a witness refutes it. An engineer who commits early to one fate spends the afternoon confirming a preference. The productive posture is to hold both open and let each attempt feed the other, because the information each produces is precisely what the other one needs. - **The argument tells the hunt where to look.** Reasoning proceeds by ruling cases out. When it stops, it stops at the case it cannot rule out — and that case is a specification of the witness. *I can close this for every interleaving except one where a release overlaps an allocation* is a search plan, not a failure. - **The hunt tells the argument what to assume.** Witnesses that come close but do not violate the claim mark the boundary. The condition that keeps failing to be violated is usually the hypothesis the document should have stated. ## What the stall point tells you | Pattern | Usual meaning | Next move | |---|---|---| | The argument stalls at one step, hunts find nothing near it | an assumption nobody stated is carrying that step | write it down, then re-argue | | The argument stalls, hunts come close at the same step | the claim is too broad and the witness is real | narrow the claim, or change the mechanism | | The argument closes but only under an added condition | the claim was fine, the document was not | restate with the condition and re-review | | Every shape stalls, no near misses in any hunt | the claim may be stated in unusable terms | rewrite the claim so one end is traceable | The middle two rows are the common ones, and both end with the **sentence** changing rather than the reasoning getting cleverer. That is the judgment worth carrying out of this: most invariants that resist an argument are drafting problems, not mathematical ones. ## When the claim itself is the defect Before spending a day on either attempt, read the claim as an adversary would: 1. **Does it quantify over something real?** *Every schedule*, *every run*, *every pair of callers* — or does it quantify over an implementation detail nobody can enumerate? 2. **Is either end traceable?** If neither the hypothesis nor the negated conclusion names an object with a history, no shape will be comfortable and the claim needs rewriting. 3. **Is it a negative?** *Never*, *no two*, *at most one* usually means contradiction, because the denial is what manufactures the object to trace. 4. **Does the design actually need this claim, or a weaker one?** Arguing a stronger statement than the system requires is a common way to spend effort on nothing. ## Deciding how long to spend The stopping rule is a cost question, and it belongs to whoever owns the design rather than to whoever is writing the argument. - **What depends on it.** A claim that other components are written against must hold in every run, and only an argument covers every run. A claim local to one component, whose violation is caught and handled, can be enforced rather than established. - **What a violation costs.** Silent corruption and lost durability justify days. A degraded but observable behaviour justifies a guard and a metric. - **Whether it can be enforced at runtime.** Some invariants are cheap to check where they matter. An enforced invariant that aborts the operation is often worth more than an argued one, because it also covers the assumptions the argument quietly made. - **Whether the search space is small.** Bounded configurations, small numbers of participants and short interleavings can sometimes be swept. An exhaustive sweep of a genuinely finite space is an argument, not a sample — but be honest about whether the space you swept is the space the claim ranges over. ## What to write down afterwards Whichever way it ends, the review should leave artefacts, because the next person to change this code inherits them: - **The shape used**, named in the first sentence, so a reader knows what the last line proves. - **Every assumption the argument leaned on**, promoted from the writer's head into stated preconditions. This is the highest-value output of the whole exercise, and the one most often lost. - **The witnesses that failed**, with the reason each failed. They are the boundary of the claim, and they save the next hunt from repeating the same ground. - **The claim as finally worded**, noted as new if it was narrowed, so nobody treats the old argument as covering it. A team that keeps only the verdict keeps the least durable part. The assumptions and the near-miss witnesses are what still holds value after the code changes.
- The hunt returns nothing and the argument stalls at the same step every time. What does that pattern usually mean?An assumption nobody wrote down is carrying that step. Make it explicit and choose: if it is genuinely guaranteed by the mechanism, add it as a stated precondition and the argument usually closes; if it is not, you have just described exactly the witness the hunt should have been constructing.
- Which claims deserve a written argument rather than a guard and a test?Claims other components are written against, and negatives whose violation is silent — no block handed out twice, no committed write lost. Tests sample runs while the claim ranges over all of them. A claim local to one component whose violation is detected and handled is better enforced at runtime than argued.
- Can an exhaustive sweep of a bounded space count as the argument?Yes, if the space swept really is the space the claim ranges over — all configurations up to a stated size, all interleavings of a fixed number of participants. Then it is a case analysis rather than a sample. The usual failure is a sweep bounded by what was affordable, reported as though it were bounded by the claim.
saying these in an interview costs you the question
- Commits to proving before checking whether the claim is even true.
- Treats a failed search as a proof and closes the review.
- Spends the same effort on an internal claim as on a safety negative.
- Ignores that a stalled step is a description of the witness to hunt.
- Records only the verdict and discards the assumptions that were needed.
- Rewrites the claim until the known witness misses, then stops.