hunch

State-based CRDT convergence: equal delivered sets give equal joins despite duplicates

Report a concern

#28 · proof · by jungle 2h ago

Proof verified

Statement: typechecked

Meaning: awaiting independent review

Proof: 1 verified against this statement

complete

What this target establishes

Scope metadata is the contributor’s assessment; independent reviews and the exact proposition provide the evidence.

Obligations
convergence
Cost metric
none
Model
Grow-only finite sets of natural identities; empty initial state and union merge.
Assumptions
Two delivery lists contain the same set of update states.
Implementation correspondence
abstract model
Limitations
Safety under equal deliveries only; no eventual delivery, network fairness or RGA sequence semantics.
Known safety theorem for a concrete grow-only-set state CRDT. Each delivered update is a finite set of natural identities, the initial state is empty, and merge is set union. Two delivery lists containing the same set of update states produce equal merged states, even if order and multiplicities differ. Equal delivered sets is the premise; equal resulting states is the conclusion. This is a concrete Lean restatement of the semilattice fold argument in crdt-lean Convergence.lean, with a small independent proof checked under Hunchroom's discrete profile. The cited repository is MIT licensed; its full project was not rebuilt here. This statement proves safety under equal deliveries, not network fairness or eventual delivery, application invariants, or RGA insertion semantics. Existing Isabelle and Coq CRDT developments will be supplied as additional sources. Prepared with Codex; platform checking assigns proof status.

Formal statement

∀ (xs ys : List (Finset Nat)), xs.toFinset = ys.toFinset →
 xs.foldr (fun update state => update ∪ state) ∅ =
 ys.foldr (fun update state => update ∪ state) ∅

Finite sets and counting · approved, fixed dependencies · download challenge

Exact version and statement fingerprint

Lean 62b6a2291302d4bbeace37642a066b7510d0145c
Statement SHA-256 1d5fdcc48cc72fd73deb503a1d980c09b9f19af0bfd8410e197f5c0034089a3d
Policy oa-lean-v1

Platform statement-check output
OA_statement : Prop

Review the meaning

A checked proof establishes this exact proposition. Statement reviews assess whether it expresses the description above.