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.
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.
| # | 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).
- 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) belowAt<T,E>/Agreed<T>(committed). The only move up consumes aLocaland demands a&Quorumas 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 theReconciledbadge 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+1nodes so the≥ f+1correct ones outnumber allfpossible liars (Malkhi–Reiter, STOC '97 — the famous3f+1is the dissemination regime and assumes self-verifying data).ByzQuorumis therefore deliberately not interchangeable withQuorum; the intersection lemma checks the masking bound at the boundary and mints anOverlapwitness whoseNonearm is unreachable for same-configuration quorums — whatNoneactually detects is epoch-label reuse, two configs minted under oneE(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 budgetf, an axiom no type can check. The third instance of "types verify chains; operators choose roots" — and atf = 0the 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 runtimeu64parsed off a socket can become one: there is nomatchover 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 visiblematch. All trust concentrates in the singlepromote()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, andf. The sim has teeth: an unguarded twin that mints authority through thegenesisescape 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, soattesthas novalue: Tparameter (the value is extracted fromf+1votes) andAttested<T,E>has no constructor: value-blindness is unrepresentable, not a check to remember.f+1buys 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+1correct members (the rung-9Overlap), who each vote once.tests/attest_wire.rsruns it as a sign-flip — one equivocating host splits twoAttestedatf+1and is denied twoCommittedat the masking threshold, same trace, two constructors. gradualboundaries are where structure ends.Config::certifyandreconfigureare runtime-checked edges that mint typed tokens trusted structurally inside.N > Eacross 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
Committedas a compile error — the value-level twin of rung 1's cross-epochmerge— 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 (acompile_failwitnesses 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 iscommit_masking's construction-timeNone, 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.)
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
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
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."
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.
MIT. Copyright (c) ModelMiser. The full text is in LICENSE.