@@ -222,17 +222,46 @@ may do wasted indexing before its 412), not correctness. ∎
222222A3 is the only axiom not guaranteed by the protocol itself; for AWS S3 it is
223223documented, for any other backend (MinIO, Ceph RGW, ...) it is an empirical
224224claim. It is discharged by a ** conformance probe** run at startup against the
225- target backend:
226-
227- > Spawn N concurrent ` PUT M_R If-Match: e ` (and ` If-None-Match: * ` ) predicated on
228- > the same ETag, with distinct payloads. ** Pass** iff exactly one PUT returns
229- > success and the remaining N−1 return precondition-failed, and a subsequent read
230- > observes the single winner's value. Repeat under sustained contention.
231-
232- If the probe passes, A3 holds for that backend and Theorems 1–3 transfer
233- unchanged. If it fails, the design is invalid against that backend — exactly as
234- non-atomic ` rename() ` would invalidate reftable. The probe is therefore a
235- ** gate** , not a benchmark, and must pass before the backend is trusted.
225+ target backend. The probe is a ** deployment admission gate** : a backend is
226+ trusted only if it passes. Passing does * not* prove the universal axiom — a
227+ finite probe yields operational confidence for * this backend, build, and
228+ config* ; failure invalidates the design against that backend, exactly as
229+ non-atomic ` rename() ` would invalidate reftable.
230+
231+ The probe has both a sequential half (semantic correctness) and a concurrent
232+ half (linearizability under contention). The concurrent half is the load-bearing
233+ part — A3 is a claim about * races* , so a probe that only checks sequential
234+ conditional writes does not discharge it.
235+
236+ 1 . ** Sequential semantics.** create-if-absent succeeds; duplicate
237+ ` If-None-Match: * ` fails; ` If-Match: E ` with current ETag succeeds; stale
238+ ` If-Match ` fails; ` If-Match ` on a missing key does not create; read-after-write
239+ returns the written value.
240+ 2 . ** N-way ` If-Match ` race (required).** Write key with body ` base ` ; read its
241+ ETag ` E ` via the * same code path production uses for the pointer* . Spawn N
242+ (e.g. 32–64) concurrent ` PUT key If-Match: E ` with unique bodies. ** Pass** iff
243+ exactly one succeeds, the other N−1 classify as precondition-failed, a
244+ subsequent read returns the winner's body and a new ETag, and the final body is
245+ never one of the * failed* payloads. Repeat for R rounds (configurable; default
246+ trades boot time against confidence).
247+ 3 . ** N-way ` If-None-Match: * ` race (required).** Same shape on a missing key:
248+ exactly one create wins, N−1 precondition failures, final body is the winner.
249+ 4 . ** ETag-token consistency.** Verify HEAD-path and GET-path ETag extraction
250+ agree byte-for-byte (quoting included). ` If-Match ` compares tokens literally;
251+ a quote mismatch between the read path and the write path silently tests the
252+ wrong thing. The probe must use the exact token format the pointer write uses.
253+
254+ ** Proof surface (explicit non-goals of the probe and the design).** The protocol
255+ depends only on conditional writes of * small single objects* (the manifest
256+ pointer). It does ** not** depend on, and the probe does ** not** test:
257+ conditional * multipart* uploads (packs are content-addressed plain PUTs, staged
258+ without conditionals) or conditional * delete* (GC uses retention/sweep over a
259+ republished manifest, not ` If-Match ` delete). Keeping the proof surface to
260+ single-object conditional PUT is what makes A3 both sufficient and cheaply
261+ checkable.
262+
263+ If the probe passes, A3 is admitted for that backend and Theorems 1–3 transfer
264+ unchanged.
236265
237266## Prior Art
238267
@@ -264,37 +293,75 @@ knowledge, new.
264293
265294## Implementation Correspondence
266295
267- The fence (Theorem 1) is enforced by the type system, not convention: the only
268- function that constructs a success ` Response ` from a push consumes a value that
269- exists only after the CAS succeeds. Snapshot reads of ref state are * fallible* ;
270- a failure to read either the before- or after-state is treated as "assume
271- changed" so the CAS path runs rather than silently skipping publish — closing
272- the double-failure hole where two failed ref scans compare equal and bypass the
273- fence. Two ordering tests pin the behavior: a ref-changing push waits for CAS; a
274- no-op push does not.
296+ The fence (Theorem 1) maps to a single structural obligation on the
297+ implementation, stated here as a requirement the code must meet for the proof to
298+ transfer:
299+
300+ - ** Unique constructor seam.** There must be exactly one path that builds a
301+ success ` Response ` from push output (the ` PackOutput → Response ` conversion),
302+ and it must live inside ` finalize_push ` after the CAS returns success. If any
303+ other path can construct that ` Response ` , the fence is convention, not
304+ structure, and Theorem 1 does not hold for the implementation. This is a
305+ checkable property of the code (one conversion site), not a claim provable
306+ here; it is the spec↔code obligation, verified by reviewers against the actual
307+ ` finalize_push ` .
308+ - ** Fallible snapshot.** Ref-state snapshots are ` Result ` , and the skip predicate
309+ is ` Ok(after) == Ok(before) ` , never ` after == before ` over values that default
310+ to equal on error. Any ` Err ` on either snapshot falls through to publish
311+ ("assume changed"). This closes the double-failure hole — two failed scans
312+ comparing equal and bypassing the fence — and is exactly the `MustPublish ==
313+ changes \/ snapErr` rule the model checks.
314+ - ** Conditional fence.** The fence engages only when refs changed; a no-op push
315+ returns success without awaiting publish (the ` SkipPublish ` path). The
316+ obligation is "publish-before-success * for ref-changing pushes* ," not
317+ unconditional publish.
318+
319+ Two ordering tests pin the behavior: a ref-changing push waits for CAS; a no-op
320+ push does not (and a both-snapshots-fail push waits, per the fallible rule).
275321
276322## Mechanized Verification
277323
278- The three safety theorems are model-checked, not only argued in prose. The
279- companion TLA+ module ` docs/spec/GitOnObjectStore.tla ` models concurrent pushers
280- racing to advance the manifest pointer, with the CAS action (` If-Match ` ) as the
281- sole pointer writer — directly encoding axiom A3. TLC checks four invariants
282- corresponding to T1–T3 plus pointer well-formedness.
324+ The safety theorems are model-checked, not only argued in prose. The companion
325+ TLA+ module ` docs/spec/GitOnObjectStore.tla ` models concurrent pushers racing to
326+ advance the manifest pointer, with the CAS action (` If-Match ` ) as the sole
327+ pointer writer — directly encoding axiom A3. Each push independently models
328+ ** (a)** whether it actually changes refs (` changes ` ) and ** (b)** whether its ref
329+ snapshot reads succeed (` snapErr ` ), so the publish-or-skip fence is exercised on
330+ all four combinations, including the both-snapshots-fail case. The skip predicate
331+ is ` MustPublish(p) == changes[p] \/ snapErr[p] ` — "publish unless we * observed*
332+ no change," never "publish unless ` b == a ` " with failed reads compared equal.
333+
334+ TLC checks five invariants: durability-ordering for obligated pushes (T1), a
335+ ref-changing push is always published (the fallible-snapshot bite),
336+ no-lost-update among installed pushes (T3), pack-set coverage (T2), and pointer
337+ well-formedness.
283338
284339```
285340$ tlc GitOnObjectStore.tla -config GitOnObjectStore.cfg
286341Model checking completed. No error has been found.
287- 1747 states generated, 398 distinct states found, 0 states left on queue.
342+ 107128 states generated, 14833 distinct states found, 0 states left on queue.
288343```
289344
290- The check is ** non-vacuous** : removing the ` If-Match ` guard from the CAS action
291- (a deliberate mutation that violates A3) makes TLC report
292- ` Invariant Safety is violated ` within a few hundred states — confirming the
293- invariants actually couple ref-safety to the CAS axiom rather than holding
294- trivially. The model is parametric in the number of pushers and bounded manifest
295- count (` Pushers = {p1,p2,p3} ` , ` MaxManifests = 5 ` in the supplied config); larger
296- bounds check identically and are limited only by state-space, as expected for a
297- property whose proof is bounded-independent (Theorems 1–3).
345+ The check is ** non-vacuous** , confirmed by two deliberate mutations:
346+
347+ - Removing the ` If-Match ` guard from CAS (violating A3) → `Invariant Safety is
348+ violated` (no-lost-update breaks): the invariants bind ref-safety to the CAS
349+ axiom.
350+ - Changing the skip predicate to ` changes[p] /\ ~snapErr[p] ` — i.e. a real ref
351+ change whose snapshots * both failed* compares "equal" and is silently skipped,
352+ exactly the double-failure hole — → ` Invariant Safety is violated ` in 181
353+ states (` Inv_ChangedPublished ` breaks). The model catches the silent-corruption
354+ bug that motivated the fallible-snapshot fix.
355+
356+ (A weaker mutation, ` MustPublish == changes[p] ` alone, does * not* break safety —
357+ it over-publishes, which is safe-but-wasteful, not unsafe. Noting this so the
358+ mutation set is honest: only the skip-on-error mutation is a true safety
359+ regression, and the model distinguishes the two.)
360+
361+ The model is parametric in pusher count and bounded manifest count
362+ (` Pushers = {p1,p2,p3} ` , ` MaxManifests = 5 ` ); larger bounds check identically,
363+ limited only by state space, as expected for a bounded-independent safety
364+ property.
298365
299366## Summary
300367
0 commit comments