A won election stays won (CoordinationState.java:323-324)
ProvedOpenSearchCoordination.handleJoin_stays_wonLet es be a monotone election strategy (es.Monotone) and cs a coordination state whose electionWon agrees with the election-quorum status of its join votes, cs.electionWon = cs.isElectionQuorum es cs.joinVotes (the second assertion of invariant()). If cs.electionWon = true and cs.handleJoin es j = .ok (cs', b), then cs'.electionWon = true.
This is the assertion assert !prevElectionWon || electionWon ("we cannot go from won to not won") in handleJoin: a join only adds a vote, a superset of a quorum is a quorum, and a monotone strategy's constraint survives added votes. Java does not require plugin strategies to be monotone; the theorem does.
import Definitions.Def_OpenSearchCoordination
theorem OpenSearchCoordination.handleJoin_stays_won {V : Type} (es : ElectionStrategy) (hes : es.Monotone) (cs : CoordinationState V) (j : Join)
(cs' : CoordinationState V) (b : Bool) (hinv : cs.electionWon = cs.isElectionQuorum es cs.joinVotes)
(h : cs.handleJoin es j = .ok (cs', b)) (hw : cs.electionWon = true) : cs'.electionWon = true := 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.handleJoin_stays_won
Notions used
Coordination states. A coordination state has nine fields: localNode (a node), currentTerm, lastAcceptedState, joinVotes (a vote collection, i.e. a list of ids), startedJoinSinceLastReboot, electionWon (a Boolean), lastPublishedVersion, lastPublishedConfiguration and publishVotes. Abbreviations, all read from the last accepted state:
- : its term;
- : its version;
- : its metadata version if the term is , otherwise its version;
- , : its last committed and last accepted voting configurations.
Quorums and votes.
- holds iff strictly more than half of the ids of configuration occur in .
- prepends when is eligible and not yet present. Otherwise it leaves unchanged. In either case it also returns whether it added.
Election strategy, election quorum, monotonicity. A strategy is an arbitrary Boolean function of a node, two naturals, an integer, two configurations and a vote collection.
means: for all fixed values of the first six arguments, if every id of is in and , then .
The handler has two cases.
- Guards. It fails unless all of the following hold:
- ;
- holds;
- 's last-accepted term and version are not ahead of ;
- is non-empty.
- Success. Otherwise, with , the result has:
- ;
- ;
- if the election is newly won.
1. Declaration
Binders.
- (implicit);
- : an election strategy;
- : a coordination state;
- : a join;
- : a coordination state;
- : a Boolean.
Hypotheses, in order.
- : ;
- : . This is conjunct (ii) of the Java invariant, an equality of Booleans.
- : ;
- : .
Conclusion. .
Combined, and say that the node's current join votes form an election quorum. The conclusion says that after any successful join, the recomputed flag is still .
2. What is not constrained
- The strategy must be monotone. For a non-monotone strategy nothing is claimed. Such a strategy could make a successful join lower the flag; this is the Java assertion at CoordinationState.java:323.
- Only one invariant conjunct is assumed. is conjunct (ii) of
javaInvariantalone. The others (term bound, published-version condition, startedJoin, publish votes) are not assumed. Nothing in the statement needs them. - is arbitrary apart from . That includes a join from an ineligible or already-counted node, which leaves the votes unchanged.
- Only the flag is claimed. Nothing is said about , the votes or the published version.
- The hypotheses are jointly satisfiable, so the statement is not vacuous. For example, take the default strategy, a node with id whose committed and accepted configurations are both , joinVotes , , , and a join in the current term whose last-accepted term is lower.
3. Plain-language summary
Under a monotone election strategy, a node that has won its election, with the stored won flag agreeing with the quorum test on its current votes, still has its election won after any successful join. In words, "won cannot become not-won".
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.