# Checkpoint Resolution Algorithm (authoritative) This is the single, authoritative spec for **receiving a checkpoint** and reconciling a finalized divergence. It replaces the old `_resolveAssertCanon` → watermark → `resolveByCompleteness` chain with ONE algorithm. There is no completeness metric and no separate canon-vs-completeness fall-through. The per-peer agreement watermark (`agreeUntil`) mechanics + the sparse send/ack live in `SPARSE_CHECKPOINT_PROTOCOL.md`; this doc is the resolution logic that runs on top. Status: this is the corrected design (supersedes the scratch `memoized-hugging-sunset.md`). Open item: once implemented, re-evaluate whether the dirty-bit ledger is still needed (working assumption: `agreeUntil` subsumes it, so it can be removed). **Scope: this is the COMPARE variant only.** Checkpoint resolution has a `compare | union` setting; this algorithm replaces the COMPARE path. Once it is implemented and solid, a follow-up upgrades it to also support the UNION option (which needs its own tweaks — TBD). --- ## 1. Definitions - **Checkpoint** — a message from a peer carrying, over a finalized tick window, the peer's per-tick **state hashes** plus the **corroborated inputs and liveness** that produced them. (Corroborated = confirmed held by a second party, i.e. real, not a local-only reconstruction.) - **Corroborated vs uncorroborated** — an input/liveness datum is *corroborated* once a second holder is known (forwarded, or the author proved a witness). *Uncorroborated* = local-only. In a FINALIZED window a still-uncorroborated datum is suspect (the network never confirmed it): "the network beats the straggler." - **`lastAgreedTick`** — the NEWEST shared checkpoint tick where your state hash equals the peer's. Found by walking the shared ticks newest→oldest, first match wins. `null` if none match anywhere. - **Adoption range** — `[lastAgreedTick, newestCheckpointTick]`. The window we may reconcile over. - **Winner / loser** — decided over a range by a LEXICOGRAPHIC score: (corroborated-input count, corroborated- liveness coverage), higher wins; ties break by seniority (older `simulationAge`, then lower `peerId`). The winner holds at least as much corroborated evidence. **Phantom inputs do NOT count toward the score.** - **Phantom input** — the value held ENTERING the adoption range, clamped to `lastAgreedTick + 1`, used so the re-sim has a correct baseline at the range start. Inserted only if your own entering value differs from the adopted one. Never counts as a corroborated input. - **Adopt = REPLACE.** Adopting the winner's corroborated set over the range REPLACES your inputs/liveness in that range (your non-adopted, e.g. uncorroborated, entries in the range are dropped). This is what converges both peers to the corroborated-only state when both held different uncorroborated data. - **`agreeUntil[P]`** — per-peer watermark: the most recent finalized tick at which you have CONFIRMED your hash == P's hash. Rises on a confirmed match, may fall on a fresh top-mismatch / self-reconcile (see §5). This algorithm only acts on FINALIZED divergences (a mismatch at a tick older than `present - graceTicks`). Non-finalized mismatches are still in flight and are ignored here. --- ## 2. Receive-a-checkpoint algorithm ``` RECEIVE CHECKPOINT cp FROM P: lastAgreedTick = newest shared tick where my hash == cp hash (walk newest→oldest) ── NO AGREEMENT ANYWHERE ── IF lastAgreedTick is null: decide winner/loser over the ENTIRE checkpoint range IF I am the loser: request state transfer from P return // winner does nothing adoptionRange = [lastAgreedTick, newestCheckpointTick] decide winner/loser over adoptionRange // corroborated inputs + liveness coverage ── WINNER PATH ── IF the loser's corroborated inputs & liveness over adoptionRange EQUAL mine (i.e. we fully agree on corroborated data — the only difference is my uncorroborated stuff): IF I hold any uncorroborated input or liveness WITHIN adoptionRange: drop those uncorroborated inputs/liveness (adoption range ONLY — never my recent not-yet-corroborated own inputs outside it) rollback to lastAgreedTick WITH predicate recheck // else (I have strictly MORE corroborated): do nothing — the loser pulls from me. ── LOSER PATH ── divergingHashes = any tick > lastAgreedTick in the range whose hashes (both present) differ // efficient invariant: adoptionRange spans > 1 tick, or the single tick's hashes differ baseline_is_equal = false IF NOT divergingHashes: // adoptionRange is effectively one tick, no proven hash divergence baseline_is_equal = (P's corroborated inputs & liveness at that tick == mine exactly) adopt P's corroborated inputs & liveness over adoptionRange (REPLACE; insert phantoms as in §4) IF divergingHashes: rollback to lastAgreedTick WITHOUT predicate recheck // proven divergence → forced full re-sim ELSE IF NOT baseline_is_equal: rollback to lastAgreedTick WITH predicate recheck // only roll back if a query result flips IF after re-sim the newest checkpoint tick STILL mismatches AND the winner had NO uncorroborated inputs in its range: // its state is fully corroborated/authoritative request state transfer from P return // (if the winner HAD uncorroborated inputs, the residual mismatch is transient — it will drop them — so // do NOT request a transfer.) ── BOTH PATHS ── update agreeUntil[P] // see §5 ``` **Why "WITHOUT recheck" for `divergingHashes` (loser).** The hashes already PROVE a real divergence, and you are force-adopting different inputs, so a predicate recheck is wasted work — and under an indeterministic game loop it can actively hinder repair. A full re-sim from `lastAgreedTick` is the safe path. When there is no proven hash divergence (a corroborated-input difference that may or may not matter), recheck WITH predicates so you only roll back if a query result actually flips — potentially saving the rollback (or part of it). **Why the winner self-cleans only on EQUAL corroborated sets.** If the loser has FEWER corroborated than you, you are authoritative and do nothing — the loser adopts from you. The self-clean case is the pure-uncorroborated divergence: corroborated sets are equal, you "win" only by tiebreak, and your extra UNCORROBORATED inputs are what make your state differ. Dropping them (network beats the straggler) converges you to corroborated-only, which is exactly where the loser lands after its adopt-replace. --- ## 3. The send gate (global, not per-peer) **Never send checkpoints while you are requesting a state transfer** (`_xferReqPending`). Waiting for a transfer means you believe your own state is wrong and unrecoverable, so any checkpoint you'd send carries misleading hashes. This is GLOBAL (suppress all outbound checkpoints), not per-peer. --- ## 4. Adopting inputs / liveness - Adopt only the winner's corroborated inputs/liveness that fall WITHIN the adoption range. Adoption REPLACES (drops your non-adopted entries in the range). - For the value held ENTERING the range: take the winner's most-recent input at or before `lastAgreedTick` and insert it as a **phantom** at `lastAgreedTick + 1` — ONLY IF your own entering value differs from it (else no phantom needed). Same for liveness. - Phantoms exist so the re-sim has the correct baseline at the range start. They NEVER count toward the corroborated-input score (they are reconstructions, not authored inputs). --- ## 5. Updating `agreeUntil[P]` (the subtle part) After processing the checkpoint (including any local re-sim), advance the watermark: - Candidate = the most recent tick in the received window where YOUR (post-re-sim) hash equals P's checkpoint hash. - **CAP for the sender's pending re-sim:** if P holds uncorroborated inputs/liveness in the window that P will itself drop and re-simulate, then P's checkpoint hashes at and above P's earliest such tick are STALE — you cannot confirm agreement there from this checkpoint (you can't see P's post-re-sim result). Ignore any match at or above that tick. - Net effect: when BOTH sides drop uncorroborated + re-sim, the watermark cannot advance past `lastAgreedTick` from this checkpoint alone — a fresh post-re-sim checkpoint from P is required to confirm newer agreement. When only YOU re-sim (P had no uncorroborated, so P's hashes are final/authoritative), you CAN advance to your newest post-re-sim match. Both winner and loser perform this update. - The watermark RISES on a confirmed match; it may FALL on a fresh top-mismatch or a self-reconcile, per `SPARSE_CHECKPOINT_PROTOCOL.md` §3. Then send the watermark ack. --- ## 6. What is removed - `resolveByCompleteness()`, `_completenessSummary()`, `completenessScore()`, the `_completenessDrivenRequest` flag, and the canon→watermark→completeness fall-through. One algorithm, transfers only when repair fails. - **Dirty-bit ledger:** working assumption it is subsumed by `agreeUntil` (you send the sparse delta above `agreeUntil[P]`, so a per-checkpoint ack ledger is redundant). To be confirmed after implementation. ## 7. What is reused - `canonWinner()` — winner/loser decision over a range. - `canonResolve()` — merged canon set. - `_reconcileToCanon()` / `_reconcileLivenessToCanon()` — the adopt-replace + phantom mechanics. - `_recheckInputs()` / `_queryLog.recheck()` — the predicate-recheck rollback anchor (the "WITH recheck" paths). - The transfer request/serve path. ## 8. Determinism Winner/loser must be computed identically on both peers (A decides winner ⟺ B decides loser). This holds because the checkpoint carries the other side's corroborated set, so each peer scores the SAME `(A, B)` pair with the SAME lexicographic + seniority tiebreak. The grace/finalization gate ensures both reconcile only over agreed-finalized data. See `SPARSE_CHECKPOINT_PROTOCOL.md` (watermark + sparse send/ack), `LIVENESS_CORROBORATION.md`, `DESIGN_PARTICIPATION.md` §13.6.