Checked cooperative finite search¶
solvi.experimental.experience.cooperation implements a finite minimization
problem with host-owned feasibility predicates and integer objective callbacks.
Assignments are immutable portable typed dictionaries indexed by string IDs.
The host supplies a revision identifying the semantics of all callbacks, and
must change it when those semantics change. Callbacks must be deterministic,
terminating and free of external effects; work units do not sandbox arbitrary
Python callbacks or limit their wall time.
FiniteProblem(assignments, constraints, objective, revision=..., budget=budget) defines the
host task. Construction pays to materialize an immutable truth/cost table.
Later mutation of callback closures has no effect on that frozen problem;
construct a new problem to change semantics. Its fingerprint includes the table.
Use the same ledger for construction and all subsequent operations. CooperativeSearch(problem, budget) accepts Evidence
claims containing an ID, source, revision, kind, target IDs, value and optional
active dependencies. Residual exposes remaining IDs, incumbent and bounds.
Source labels are provenance labels, not authenticated identities.
exclusion: each target violates the host constraint named byvalue.incumbent: one feasible target has exactly the claimed integer cost.lower_bound: every feasible original assignment has cost at leastvalue. This deliberately expensive independent finite check does not rely on solver claims or a circular argument about an already pruned residual.
ConstraintSolver checks successive surviving assignments and emits checked
counterexamples to feasibility. ObjectiveSolver sorts the current residual by
cost and proposes a feasible improving incumbent. Both implement the callable
solver(residual, budget) -> Evidence | None protocol. In run, the next solver
receives the updated residual after each acceptance: exclusions directly reduce
its objective evaluations and an incumbent changes its improvement threshold.
Custom solvers must debit their internal work through the supplied ledger.
These are cooperating constraint and objective methods, not external solver
integrations or a claim of a generally faster optimization algorithm.
submit independently rechecks every claim; contradictory certificates,
unknown targets, stale revisions, duplicate IDs, missing and cyclic dependencies
are rejected without changing accepted state. Rejected checking still costs
work. revoke(id) removes that claim and its transitive dependents; IDs cannot
be reused. Constraints are never relaxed by evidence.
run(solvers, rounds=...) is bounded by a finite number of calls and returns
unknown, including when a budget is exhausted. A feasible incumbent does not
imply optimality. certify() pays for finite_reference(problem, budget), an
exhaustive independent search, and returns optimal, infeasible, or unknown
on exhaustion. The reference returns (cost, assignment_id) with deterministic
ID tie breaking.
snapshot() records the evidence journal and complete budget. To restore,
call CooperativeSearch.restore(snapshot, host_problem, existing_host_budget, authority=search.authority). Replay validates the
schema, digest and problem fingerprint, uses the existing host ledger (rejecting refunded or inflated-limit ledgers), charges
replay and verification again, and fails closed on invalid evidence or exhausted
budget. Neither callbacks nor solver objects are deserialized. Callback semantics are frozen in the problem fingerprint; a digest is corruption detection,
not authentication. Solvers can be recreated after restore, with fresh source
names to avoid reusing evidence IDs. No snapshot can establish final optimality
without another paid certify call.
See examples/36_cooperative_solvers.py for a complete local example. The
implementation promises correctness on a finite declared domain, not a speed
advantage over enumeration; measurements must include all checker work.
Finite limits: 4096 assignments, 32 named constraints, 32 attributes per assignment, 4096 journal entries, 4096 targets/dependencies per claim, 256 characters per evidence identifier and 4096 rounds. Non-sequence iterators for task mappings and claim targets/dependencies are rejected before materialization. Residual reads, snapshots, rounds and even empty-domain reference certificates cost work. Exhaustion can make residual access raise BudgetStop; run returns residual=None in its budget result. Replay receives a host ledger rather than constructing a replacement ledger from untrusted snapshot data.
CooperativeAuthority is a trusted host capability holding the current epoch,
exact authorized checkpoint identity and a live reference to the shared budget.
Every accepted claim/retraction invalidates prior snapshots. Successful restore
transfers ownership and makes the old search instance stale; a snapshot by
itself cannot authorize replay. A restore compares the incoming budget against
the live ledger before charging restore, so spending in other users of the
shared ledger cannot be refunded by an old ledger clone. While the authority
is live, restore requires that same budget object.
For a fresh process, the host persists authority.export_trusted_state() in a
trusted monotonic channel, separately from untrusted snapshot data, and reloads
with CooperativeAuthority.from_trusted_state(anchor). Persist the CURRENT
budget as well. The host must prevent rollback/duplication of that trust anchor;
loading a self-reported or old authority anchor is outside this security contract.
No cryptographic signature or external durable storage service is provided.