invariant() is preserved by handleJoin, handleClientValue and handlePublishResponse
ProvedOpenSearchCoordination.javaInvariant_preservedFor every monotone election strategy es and coordination state cs with cs.javaInvariant es:
- if
cs.handleJoin es j = .ok (cs', b)thencs'.javaInvariant es; - if
cs.handleClientValue s = .ok (cs', p)thencs'.javaInvariant es; - if
cs.handlePublishResponse n r = .ok (cs', o)thencs'.javaInvariant es.
javaInvariant is the conjunction of the five assertions of invariant() (CoordinationState.java:601-611). With init_javaInvariant and handleStartJoin_javaInvariant this accounts for every handler except handlePublishRequest (see javaInvariant_not_local), handleCommit and setInitialState, the three that change the configurations the second assertion reads.
import Definitions.Def_OpenSearchCoordination
theorem OpenSearchCoordination.javaInvariant_preserved {V : Type} (es : ElectionStrategy) (hes : es.Monotone) (cs : CoordinationState V)
(hinv : cs.javaInvariant es) :
(∀ j cs' b, cs.handleJoin es j = .ok (cs', b) → cs'.javaInvariant es) ∧
(∀ s cs' p, cs.handleClientValue s = .ok (cs', p) → cs'.javaInvariant es) ∧
(∀ n r cs' o, cs.handlePublishResponse n r = .ok (cs', o) → cs'.javaInvariant es) := by sorryRead-back
What the Lean code literally says, in plain math · claude-opus-5-5 (independent sub-agent, blind: Lean code + auditor instructions only)
Read-back: OpenSearchCoordination.javaInvariant_preserved
Notions used
Coordination states. For a payload type , a coordination state has nine fields:
- , a node with an id and an eligibility flag;
- ;
- , a cluster state with a term, version, metadata version, last committed and last accepted voting configurations, and other fields;
- and , vote collections (lists of ids);
- and ;
- ;
- .
Abbreviations, all read from the accepted state:
- : its term;
- : its version;
- : its metadata version if the term is , otherwise its version;
- and : its last committed and last accepted configurations.
Quorums, votes, strategies.
- holds iff strictly more than half of 's ids occur in .
- prepends if is eligible and absent. Otherwise it leaves unchanged.
- An election strategy is an arbitrary Boolean function .
- .
- : with the first six arguments fixed, if holds for and every id of is in , then holds for .
The Java invariant. is the conjunction of:
- (i) ;
- (ii) ;
- (iii) if , then ; otherwise ;
- (iv) ;
- (v) is empty .
The three handlers.
- .
- Guards: ; ; 's accepted term and version are not ahead of ; is non-empty.
- Effect: becomes , and becomes . If the election is newly won, becomes . Nothing else changes.
- .
- Guards: the election is won; ; ; ; no reconfiguration while reconfiguring; the join votes form a quorum of 's accepted configuration.
- Effect: , , .
- .
- Guards: the election is won; ; .
- Effect: becomes .
None of the three changes , or . Those are the only fields, besides the votes argument, that reads.
1. Declaration
Binders.
- (implicit);
- : an election strategy;
- : a coordination state.
Hypotheses, in order.
- : ;
- : .
Conclusion. The conjunction of three clauses:
- ;
- ;
- .
In words: from a state satisfying all five Java invariant conjuncts under a monotone strategy, one successful step of any of these three handlers leads to a state satisfying them again, for the same strategy.
2. What is not constrained
-
Scope: three of the seven handlers.
handleStartJoinis covered separately byhandleStartJoin_javaInvariant, under the weaker hypothesis of conjunct (i) only.handlePublishRequestis shown not to preserve the invariant byjavaInvariant_not_local.setInitialStateandhandleCommitare covered by no theorem of the mission.
-
Observation about
handleCommit. This is not a claim of any theorem; I checked it by evaluating the definitions.handleCommitdoes not preservejavaInvarianteven underDEFAULT_INSTANCE. Take node 4 with:- current term , accepted state of term and version ;
- committed configuration and accepted configuration ;
- join votes , , , published version , no publish votes.
This state satisfies all five conjuncts: the votes are not a quorum of . Now apply the commit . It succeeds and sets the committed configuration to . The quorum test becomes true while stays false, which breaks (ii). So this theorem together with
javaInvariant_not_localshould not be read as saying that publish requests are the only steps that break the invariant. -
Monotonicity is assumed for all three clauses. Only the join clause needs it, to rule out a won election becoming not won, since conjuncts (iii) and (v) depend on that. The other two clauses do not change the votes or the flag.
-
The same strategy throughout. is the strategy both in the invariant and in
handleJoin. -
One step at a time. Each clause is a single-step implication from success. The statement says nothing about sequences of steps that interleave other handlers.
-
Not vacuous. The hypotheses are satisfiable: for example,
initof any state with accepted term current term satisfiesjavaInvariant, and the default strategy is monotone.
3. Plain-language summary
Under a monotone election strategy, if a coordination state satisfies the five assertions of Java's invariant(), then any successful join, client-value or publish-response step yields a state that satisfies them again. The theorem says nothing about publish requests, commits or initial-state injection.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.