handleJoin: which votes are counted, and electionWon recomputed
ProvedOpenSearchCoordination.handleJoin_specFor every election strategy es, coordination state cs, join j, state cs' and flag b: if cs.handleJoin es j = .ok (cs', b) then
- the join is for the current term:
j.term = cs.currentTerm; - the node has handled a start-join since its last restart (
cs.startedJoinSinceLastReboot = true) and has been bootstrapped (cs.lastAcceptedConfiguration.isEmpty = false); - the voter's accepted state is no fresher than the node's:
j.lastAcceptedTerm < cs.lastAcceptedTerm, or the terms are equal andj.lastAcceptedVersion ≤ cs.lastAcceptedVersionOrMetadataVersion; - the new join votes are
(cs.joinVotes.addVote j.sourceNode).1, andbis(cs.joinVotes.addVote j.sourceNode).2, whether the vote was new; cs'.electionWon = cs.isElectionQuorum es cs'.joinVotes:electionWonis recomputed as whether the new votes are a quorum of the last committed and of the last accepted configuration ofcsand satisfy the strategy's additional constraint (nothing is assumed ofcsores, so a successful join may also turnelectionWonfrom true to false, for instance wherecs.electionWondisagrees with its votes, or for a strategy that is not monotone;handleJoin_stays_wonrules this out under its hypotheses);- the current term, last accepted state, local node,
startedJoinSinceLastReboot, publish votes andlastPublishedConfigurationofcs'are those ofcs; cs'.lastPublishedVersioniscs.lastAcceptedVersionif this join won the election (cs'.electionWon = trueandcs.electionWon = false), andcs.lastPublishedVersionotherwise.
The Java assertion that the join targets this node (CoordinationState.java:265) is not checked by the transcription and does not appear here.
import Definitions.Def_OpenSearchCoordination
theorem OpenSearchCoordination.handleJoin_spec {V : Type} (es : ElectionStrategy) (cs : CoordinationState V) (j : Join) (cs' : CoordinationState V)
(b : Bool) (h : cs.handleJoin es j = .ok (cs', b)) :
j.term = cs.currentTerm ∧ cs.startedJoinSinceLastReboot = true ∧
cs.lastAcceptedConfiguration.isEmpty = false ∧
(j.lastAcceptedTerm < cs.lastAcceptedTerm ∨
(j.lastAcceptedTerm = cs.lastAcceptedTerm ∧ j.lastAcceptedVersion ≤ cs.lastAcceptedVersionOrMetadataVersion)) ∧
cs'.joinVotes = (cs.joinVotes.addVote j.sourceNode).1 ∧ b = (cs.joinVotes.addVote j.sourceNode).2 ∧
cs'.electionWon = cs.isElectionQuorum es cs'.joinVotes ∧
cs'.currentTerm = cs.currentTerm ∧ cs'.lastAcceptedState = cs.lastAcceptedState ∧
cs'.localNode = cs.localNode ∧ cs'.startedJoinSinceLastReboot = cs.startedJoinSinceLastReboot ∧
cs'.publishVotes = cs.publishVotes ∧ cs'.lastPublishedConfiguration = cs.lastPublishedConfiguration ∧
cs'.lastPublishedVersion =
(if cs'.electionWon = true ∧ cs.electionWon = false then cs.lastAcceptedVersion else cs.lastPublishedVersion) := 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_spec
Notions used
Coordination states. For a payload type , a coordination state has nine fields:
- : a node, made of an id in and a Boolean "eligible" flag;
- ;
- : a cluster state with a term , a version , a metadata version , last committed and last accepted voting configurations, and further fields;
- and : vote collections, which are lists of ids;
- and : Booleans;
- ;
- .
Abbreviations, all read from :
- = its term;
- = its version;
- = its metadata version if its term is , and its version otherwise;
- = its last committed configuration;
- = its last accepted configuration.
Configurations and votes.
- A voting configuration is a strictly increasing list of ids. means the list is .
- holds iff .
- returns if is eligible and , and otherwise.
Election quorum. An election strategy is an arbitrary Boolean function of seven arguments.
Joins. A join has two nodes, and , a term , and .
The handler tests five guards in order. The first one that holds gives :
- ;
- ;
- ;
- ;
- .
If no guard holds, the handler computes:
- ;
- .
It returns . Here is with and . In addition, if holds and was false.
1. Declaration
Binders.
- (implicit);
- : an election strategy, arbitrary;
- : a coordination state;
- : a join;
- : a coordination state;
- : a Boolean.
Hypothesis. : .
Conclusion. The conjunction of:
- ;
- ;
- ;
- ;
- ;
- ;
- , evaluated against the old state's configurations, terms and version;
- ;
- ;
- ;
- ;
- ;
- ;
- if , and otherwise.
Conjuncts 1–4 are exactly the negations of the five guards. Guards 3 and 4 combine into conjunct 4.
Conjuncts 5, 7 and 8–14 fix all nine fields of , and conjunct 6 fixes . Since conjuncts 8–10 keep every input of the election test unchanged, conjunct 7 could equally be evaluated on .
2. What is not constrained
- is never mentioned. The handler does not check that the join is addressed to this node; Java only asserts it.
- is arbitrary. If it is ineligible, or its id is already present, then and . Even so, the election flag is recomputed.
- There is no invariant hypothesis. So the statement covers states whose disagrees with the quorum test. For such a state, a successful join can turn from to . Conjunct 7 then forces that, and conjunct 14 leaves unchanged. "Won stays won" is a separate theorem with extra hypotheses (
handleJoin_stays_won). - Two different version notions appear.
- The freshness comparison in conjunct 4 uses , the metadata version for term-0 states.
- The strategy argument inside and the new in conjunct 14 use the plain .
- is arbitrary; no monotonicity is assumed.
- Only one direction. The statement goes from success to these facts; it does not claim that a join satisfying 1–4 succeeds. In fact the guards are exactly 1–4, but the theorem does not state the converse.
- Not vacuous. The success hypothesis is satisfiable.
3. Plain-language summary
A join is accepted only if:
- its term equals the node's current term;
- the node has received a start-join since its last restart;
- the node's accepted configuration is non-empty;
- the joiner's last-accepted (term, version) is not ahead of the node's own (using the metadata version for term-0 states).
When accepted:
- the joiner is added as a vote if it is eligible and new, and the returned Boolean says whether it was added;
- the election-won flag is recomputed from the new votes;
- the published version is set to the accepted version exactly when the election has just been won;
- nothing else changes.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.