Skip to content

About

Feasibility toy: epoch-indexed complement proofs make split-brain unrepresentable at compile time. A distributed-systems generalization of warp-types.

Resources

Stars

0 stars

Watchers

0 watching

Forks

Latest commit

 

History

128 Commits

Folders and files

Repository files navigation

quorum-types

CI

Can the compile-time safety of warp-types survive the move from a GPU warp to a distributed system?

Status: feasibility exploration. Every piece here is a deliberately small toy built to answer one question and stop. Nothing is production code, the formal model is bounded, and the tests exercise small domains. What it offers is an arc — a chain of small results, each verified, that together map where structural typing helps in a distributed setting and where it must hand off to a runtime check.

The idea

Verification is becoming the bottleneck of software: generation outpaces review. Of the styles that have historically composed and scaled, structural (type-level) enforcement stands out — you get the guarantee by construction, not by a global proof.

warp-types is a structural type system for GPU warps: a diverged warp cannot call a shuffle because the method does not exist on its type. The observation behind this repo is that a GPU warp is a degenerate best-case distributed system — fixed membership, lockstep, no partitions, no failure. So warp-types is already a session/ownership type system specialized to the friendliest distributed system in existence. What has to change to handle a real one?

The answer, built up step by step below, is: keep the type carrying the relations (epoch, complementarity, majority), push the elements and the temporal facts to runtime certificates at a gradual boundary — and accept that some safety is structural while some is irreducibly temporal.

The arc

# Layer Question Result
1 lib.rs (base) Does epoch-indexing compose with compile-time complement proofs? Yes. Cross-epoch merge is a type error — split-brain unrepresentable at compile time.
2 tla/quorum.tla Is the type-level epoch sufficient for safety? No. Split-brain is temporal; a bounded TLA+ check finds it as soon as the lease guard is dropped. Epoch is necessary but not sufficient.
3 failover.rs How does the missing temporal guard look in Rust? A runtime lease check (reconfigure returns Result) — the gradual boundary the model proved unavoidable.
4 tests/partition_heal.rs Does the real API hold across a failure cycle? A deterministic crash→partition→heal sim keeps NoSplitBrain throughout, delegating the decision to the real reconfigure.
5 membership.rs How does membership go dynamic and unbounded? By flipping the set relation: warp complements are disjoint; distributed quorums must intersect. The type stays relational; the members become a runtime set.
6 reconfig.rs Are the temporal and structural guards redundant? No — they split safety by regime. Within an epoch, intersection. Across an epoch, quorums can be disjoint, so only the lease is safe.
7 consistency.rs Can the data be typed, not just the membership? A value's consensus strength becomes a lattice Local → At<T,E> → Agreed<T>. Moving up requires a &Quorum as evidence; moving down is free — so a committed value is unforgeable, and acting on an uncommitted one is a type error.
8 reconcile.rs Can the merge of divergent committed values be typed? Partly. Diverged → Reconciled is an evidence-gated typestate: the merge demands a Lawful witness minted by property-checking the merge function's semilattice laws at a runtime boundary (sampled evidence, not proof — Propel does this soundly, statically). And the merged result re-enters the lattice at the bottom: in a consensus system a merge is a new proposal, not a decision.
9 byzantine.rs Does the evidence discipline survive nodes that lie? Yes, with a declared axiom. A masking quorum (n ≥ 4f+1, overlap ≥ 2f+1 — Malkhi–Reiter) is a distinct certificate type: crash evidence where Byzantine evidence is required is a compile error. The fault budget f is operator-declared — the types propagate its consequences but cannot check it.
10 tests/wire_sim.rs Does the discipline survive an actual wire? Per process, yes — and the wire is a named boundary. A turmoil-simulated cluster drives the real API over UDP through crash → partition → heal. A const E: u64 cannot be lifted from runtime bytes, so one promote() function and one visible match (runtime data selecting among compiled monomorphizations) are the only crossing — and a twin that bypasses the lease guard split-brains under the same seed.
11 attest.rs Can a value be believed only when nodes corroborate it? Yes, in two tiers. The crash lattice (7) discards its quorum witness (commit's _witness is unused); under Byzantine faults it becomes load-bearing. Attested<T,E> has no value: T parameter and no constructor, so a value can only inhabit it if f+1 distinct members voted for it — value-blindness is unrepresentable. f+1 buys existence, not uniqueness; Committed<T,E> at the masking threshold buys uniqueness, reduced to the rung-9 Overlap at construction time. tests/attest_wire.rs: one equivocating host splits at f+1, is denied at the masking threshold.

Read top to bottom, that is the whole story: a structural guarantee (1), a proof that it is not enough (2), the runtime guard that completes it (3), evidence it works end-to-end (4), the generalization to real membership (5), the composition showing the two guards are complementary (6), the same discipline turned on the values rather than the membership (7), the merge of values that disagree — where the discipline survives but its evidence weakens from counted majorities to sampled laws (8), the adversarial fault model, where the count itself must mask liars and the whole guarantee becomes conditional on a trust declaration (9), the network itself, where the type-level epoch is honestly a per-process property and everything hinges on one deserialization boundary (10), and finally the values that cross that wire, believable only when f+1 distinct nodes corroborate them and uniquely believable only at the masking threshold — the same equivocating host that splits the weak threshold is denied by the strong one (11).

Key findings

  • Split-brain unrepresentable is a type-error claim. Lifting the epoch into the type makes merge(q@epoch3, q@epoch4) fail to unify — the guarantee is discharged by the compiler's unifier, nothing runs.
  • The epoch is necessary but not sufficient. Safety against a stale leader is temporal — no type can say "wait for the old lease to expire." A bounded TLA+ model (guarded: no violation over 36 states; negative control: split-brain at depth 4) pins this down.
  • Dynamic membership is a sign flip, not a scale-up. Divergence partitions lanes into disjoint complements; failure-tolerant consensus needs the opposite relation — any two quorums must intersect. Overlap is necessary for agreement (though not alone sufficient — the shared member must also refuse to double-vote, which this toy does not model).
  • The two guards partition safety by regime. Within a configuration, safety is structural (intersection). Across a configuration change, quorums can be disjoint, so intersection guarantees nothing — safety must come from elsewhere. This is the known cross-configuration hazard, and real systems answer it two ways: force overlapping joint majorities across configs (Raft's C_old,new), or sequence configs with a leader lease (this toy's choice, in the Chubby/Boxwood lineage; Vertical Paxos uses an external reconfiguration authority). Arriving at that fork from "generalize warp-types" is a faithfulness signal, not a novelty claim.
  • The value lattice is asymmetric: up is quorum-gated, down is free. Consensus strength is itself a type — Local (a proposal) below At<T,E>/Agreed<T> (committed). The only move up consumes a Local and demands a &Quorum as evidence, so a committed value is unforgeable; weakening back down needs nothing, because discarding a guarantee is always sound. "Act only on decided values" is then a compile error, not a runtime flag anyone can set.
  • A merge is a proposal, not a decision. Reconciling two divergent committed values is evidence-gated like everything else (Lawful<M>, a witness that the merge's semilattice laws held on samples), but its output re-enters the lattice at the bottom: no quorum has witnessed the merged value as the resolution, so it must be committed again. In a pure CRDT the merge is the truth — that difference is the seam between the two worlds. The witness here is the runtime-cheap cousin of what Propel (PLDI 2023) proves statically, and it gates standing, not computation: nothing stops code from hand-merging readable values off-path, and the samples are caller-chosen — certification is self-attestation, so the Reconciled badge proves a law-check ran, not that gaming one is impossible. Types verify chains; operators choose roots.
  • Byzantine evidence is a different type, not a bigger number. Under crash faults one shared node proves continuity, because nodes do not lie. Under Byzantine faults the reader must out-vote liars, and without signatures that takes a masking quorum: n ≥ 4f+1, quorums of ⌈(n+2f+1)/2⌉, any two overlapping in ≥ 2f+1 nodes so the ≥ f+1 correct ones outnumber all f possible liars (Malkhi–Reiter, STOC '97 — the famous 3f+1 is the dissemination regime and assumes self-verifying data). ByzQuorum is therefore deliberately not interchangeable with Quorum; the intersection lemma checks the masking bound at the boundary and mints an Overlap witness whose None arm is unreachable for same-configuration quorums — what None actually detects is epoch-label reuse, two configs minted under one E (a cold review compiled that case; an infallible draft panicked on it). And the witness's meaning is conditional throughout: every promise is relative to the operator's declared fault budget f, an axiom no type can check. The third instance of "types verify chains; operators choose roots" — and at f = 0 the masking threshold degenerates exactly to the crash majority.
  • The wire is where const generics die — what survives is a boundary. Every certificate here is indexed by const E: u64, and no runtime u64 parsed off a socket can become one: there is no match over 2^64 monomorphizations. The deterministic network sim (tests/wire_sim.rs, three turmoil hosts exchanging raw datagrams) shows what survives: within each process the discipline is intact — election, certification, and failover all run through the typed API, monomorphic in the epoch — and the runtime epoch does exactly one thing, select which compiled epoch space to enter, at one visible match. All trust concentrates in the single promote() that turns bytes into typed values (a lying peer can announce a shorter lease; the types verify counting after promotion, never that the bytes told the truth) — the fourth root in the arc's refrain, after membership, samples, and f. The sim has teeth: an unguarded twin that mints authority through the genesis escape hatch split-brains at the exact tick the TLA+ counterexample predicts, with the partition delivered as a network event rather than a bookkeeping flag, and the whole trace is seed-reproducible byte for byte.
  • A witness changes weight with the fault model. The value lattice commits with commit(self, _witness: &Quorum<E>) — the witness is discarded, because under crash faults an honest majority's mere existence is enough. Under Byzantine faults that is forgeable, so attest has no value: T parameter (the value is extracted from f+1 votes) and Attested<T,E> has no constructor: value-blindness is unrepresentable, not a check to remember. f+1 buys existence (≥1 correct voucher) but not uniqueness — two conflicting values can each clear it. Committed<T,E> at the masking threshold buys uniqueness, and the reduction is ordinary typechecking at construction time, not a proof obligation: two masking quorums meet in ≥ f+1 correct members (the rung-9 Overlap), who each vote once. tests/attest_wire.rs runs it as a sign-flip — one equivocating host splits two Attested at f+1 and is denied two Committed at the masking threshold, same trace, two constructors.
  • gradual boundaries are where structure ends. Config::certify and reconfigure are runtime-checked edges that mint typed tokens trusted structurally inside. N > E across a reconfiguration and true linear must-consume are not expressible on stable Rust — documented as boundary invariants rather than faked.
  • The ladder tops out at a structural ceiling, not a Rust limitation. Conflicting Committed as a compile error — the value-level twin of rung 1's cross-epoch merge — is impossible, and the impossibility is the capstone result. Two reasons: Rust is not dependently typed, so a runtime vote value cannot be lifted into a const generic (a compile_fail witnesses the E0435); and, deeper, the disagreement that constitutes split-brain lives in two different processes, while a type system is per-process — no single typechecker sees both certificates. So value-uniqueness is commit_masking's construction-time None, the maximal enforcement a per-process type system can offer against a cross-process threat. (Cross-participant agreement can be typed statically — refined multiparty session types — but only via a prover over an intact session a partition destroys; not by ordinary typechecking.)

Layout

src/lib.rs               base: Quorum<const E, S> — compile-time epoch + complement
src/failover.rs          gap #1: Lease, reconfigure — runtime temporal guard
src/membership.rs        gap #2: Config/Quorum<const E> — dynamic intersecting quorums
src/reconfig.rs          unified: LeasedQuorum — both guards composed
src/consistency.rs       value lattice: Local/At/Agreed — consensus strength as a type
src/reconcile.rs         divergence: Diverged/Lawful/Reconciled — evidence-gated merge
src/byzantine.rs         lying nodes: BftConfig/ByzQuorum/Overlap — masking quorums
src/attest.rs            attested values: Vote/Attested/Committed — corroboration as a type
tests/partition_heal.rs  deterministic crash/partition/heal simulation
tests/wire_sim.rs        the same cycle over a simulated network (turmoil)
tests/attest_wire.rs     an equivocating host: existence splits, masking denies it
tla/quorum.tla           bounded TLA+ model of the failover discipline
    quorum_guarded.cfg   lease guard on  — invariants hold
    quorum_noguard.cfg   lease guard off — split-brain counterexample

Running it

cargo test                 # 80 tests: unit + integration + sim + doctest + compile-fail
cargo clippy --all-targets -- -D warnings

# The formal model (needs Java + tla2tools.jar):
java -cp tla2tools.jar tlc2.TLC -deadlock -config tla/quorum_guarded.cfg tla/quorum.tla   # holds
java -cp tla2tools.jar tlc2.TLC -deadlock -config tla/quorum_noguard.cfg tla/quorum.tla   # finds split-brain

Scope and non-goals

This is a research feasibility study, not a consensus library. It does not provide: a network/transport layer, a message protocol, real-time leases, more than two-way static splits, or Byzantine tolerance. The TLA+ model is bounded (MaxEpoch = 2, two halves) and the property tests cover small domains. Treat every result as "holds in the checked domain," not "proven in general."

Relationship to warp-types

warp-types is a published, independent crate and is treated here as a read-only reference — it is not a dependency. The ActiveSet / ComplementOf traits in the base module are a minimal model of its concept, kept self-contained so this experiment varies only the distributed dimensions.

License

MIT. Copyright (c) ModelMiser. The full text is in LICENSE.

About

Feasibility toy: epoch-indexed complement proofs make split-brain unrepresentable at compile time. A distributed-systems generalization of warp-types.

Resources

Stars

0 stars

Watchers

0 watching

Forks

Releases

Packages

Used by

Contributors

Languages