Skip to content

Bind family, semaphore, and prefix decisions to coherent reads #45

Description

@flyingrobots

Collection decisions can commit against the current generation while using incomplete membership. The #38 investigation has exposed independent family, semaphore and prefix invariant violations with controlled mixed observations.

The fixture serves one synthetic for-each-ref result assembled from individually valid before/after refs of a completed operation. Every referenced object comes from the real isolated store; ordinary cat-file and real update-ref transactions run unchanged. Retries read the actual store. This establishes that the planners do not reject these mixed observations. A live Git schedule producing them has not been reproduced. Git's update-ref contract allows concurrent readers to observe only a subset of transaction modifications; the exact backend schedules remain unverified.

Reproductions against 01e39c306362d7de26cec08f149d7f286e3733ce, fixed clock 1000000, first study seed 38:

  • Family: Observe the new parent job record and parent path record, but omit the newly admitted child job. release --job p6899 exits 0 and its real transaction deletes the parent refs without deleting the child. An independent raw-ref/object check finds child c6899 referencing missing parent p6899. Representative case: family-38-14.
  • Semaphore: Observe the new refs/locks/sem/gpu/gen but omit the committed slots/c6899. sem acquire gpu --job z6899 --holder bob exits 0. Two live slots remain under capacity 1. Representative case: semaphore-38-01.
  • Prefix: Observe the new directory token but omit the committed descendant job. A claim on d6899/ exits 0 while another job still holds d6899/child.md. An independent path comparison finds overlapping live reservations. Representative case: prefix-38-01.

The first exhaustive small matrix exposed 7 violating cases among 28 per-ref mixes: 4/16 family, 1/4 semaphore, 2/8 prefix. Coherent before/after controls remain healthy; an old generation with incomplete old membership triggers a retry. Injecting only the initial dispatcher read is insufficient for release and semaphore acquisition, which take a fresh planner read. The study retains that negative instrumentation control. The completed matrix contains 84 cases across seeds 38, 1701 and 20260922, with 21 invariant violations. Study PR #47 retains the complete ledger and exact object/ref/transaction receipts; it does not implement this corrective work.

Acceptance criteria

  • Define and justify how the membership used for admission is bound to the generation or other witness checked at commit, including concurrent observation itself.
  • Family release, sweep and parent replacement cannot commit from an observation that omits a child belonging to the parent acquisition; preserved parent/child invariants are checked independently after the operation.
  • Semaphore admission cannot exceed capacity when observation omits a committed live slot while retaining the current generation.
  • Prefix admission cannot overlap a live descendant when observation omits its job while retaining the current directory token.
  • Turn retained observation-phase counterexamples into actual safety regressions. They must pass by preserving invariants or refusing/retrying safely, rather than classifying the unsafe result as expected success.
  • Preserve coherent-read golden paths, old-generation retry controls, and known-bad oracle calibration. Record the exact planner observation and real transaction result.
  • Distinguish synthetic fixtures from any reproduced live Git schedules, state supported backend/read-order assumptions, and retain unresolved limitations.
  • Update the documented guarantee and pass relevant tests/lint without adding an unreviewed broad redesign.

An immutable semaphore state object in #20 is one design to compare, not an adopted solution. This is an unresolved correctness gate for the hardening release tracked by #41. Completing the #38 investigation does not complete this fix.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't working

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions