Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

handleJoin: which votes are counted, and electionWon recomputed

Proved
OpenSearchCoordination.handleJoin_spec

by pitimespi · Nov 1, 2026 · Mathlib 0df444a (Lean v4.33.1)

cluster-coordinationconsensuscoordination-stateelasticsearchformal-verificationleader-electionopensearchpaxosquorumraftzen2

For 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 and j.lastAcceptedVersion ≤ cs.lastAcceptedVersionOrMetadataVersion;
  • the new join votes are (cs.joinVotes.addVote j.sourceNode).1, and b is (cs.joinVotes.addVote j.sourceNode).2, whether the vote was new;
  • cs'.electionWon = cs.isElectionQuorum es cs'.joinVotes: electionWon is recomputed as whether the new votes are a quorum of the last committed and of the last accepted configuration of cs and satisfy the strategy's additional constraint (nothing is assumed of cs or es, so a successful join may also turn electionWon from true to false, for instance where cs.electionWon disagrees with its votes, or for a strategy that is not monotone; handleJoin_stays_won rules this out under its hypotheses);
  • the current term, last accepted state, local node, startedJoinSinceLastReboot, publish votes and lastPublishedConfiguration of cs' are those of cs;
  • cs'.lastPublishedVersion is cs.lastAcceptedVersion if this join won the election (cs'.electionWon = true and cs.electionWon = false), and cs.lastPublishedVersion otherwise.

The Java assertion that the join targets this node (CoordinationState.java:265) is not checked by the transcription and does not appear here.

Preamble
import Definitions.Def_OpenSearchCoordination
Formal statement
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 sorry
Source
OpenSearch b2a54ba5c0defba3d1d20423e911d4bf920bab19: CoordinationState (constructor lines 84-106, isElectionQuorum 144-154, isPublishQuorum 156-158, setInitialState 180-204, handleStartJoin 213-255, handleJoin 264-339, handleClientValue 348-407, handlePublishRequest 416-460, handlePublishResponse 471-515, handleCommit 523-573, invariant 601-611, PersistedState.markLastAcceptedStateAsCommitted 703-728, commitVotingConfiguration 730-740, VoteCollection 750-814), server/src/main/java/org/opensearch/cluster/coordination/CoordinationState.java: https://github.com/opensearch-project/OpenSearch/blob/b2a54ba5c0defba3d1d20423e911d4bf920bab19/server/src/main/java/org/opensearch/cluster/coordination/CoordinationState.java#L64-L815; CoordinationMetadata.VotingConfiguration (lines 383-449, hasQuorum 405-409): https://github.com/opensearch-project/OpenSearch/blob/b2a54ba5c0defba3d1d20423e911d4bf920bab19/server/src/main/java/org/opensearch/cluster/coordination/CoordinationMetadata.java#L383-L449; ElectionStrategy (DEFAULT_INSTANCE lines 46-59, isElectionQuorum 68-88): https://github.com/opensearch-project/OpenSearch/blob/b2a54ba5c0defba3d1d20423e911d4bf920bab19/server/src/main/java/org/opensearch/cluster/coordination/ElectionStrategy.java#L44-L110; ClusterState.getVersionOrMetadataVersion (lines 239-244): https://github.com/opensearch-project/OpenSearch/blob/b2a54ba5c0defba3d1d20423e911d4bf920bab19/server/src/main/java/org/opensearch/cluster/ClusterState.java#L239-L244; Coordinator.ZEN1_BWC_TERM (line 134): https://github.com/opensearch-project/OpenSearch/blob/b2a54ba5c0defba3d1d20423e911d4bf920bab19/server/src/main/java/org/opensearch/cluster/coordination/Coordinator.java#L134; the messages StartJoinRequest.java, Join.java, PublishRequest.java, PublishResponse.java, ApplyCommitRequest.java in the same directory; test vectors from server/src/test/java/org/opensearch/cluster/coordination/CoordinationStateTests.java (https://github.com/opensearch-project/OpenSearch/blob/b2a54ba5c0defba3d1d20423e911d4bf920bab19/server/src/test/java/org/opensearch/cluster/coordination/CoordinationStateTests.java) and CoordinationMetadataTests.java (testVotingConfiguration)
Read-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 VVV, a coordination state cscscs has nine fields:

  • cs.localNodecs.\mathrm{localNode}cs.localNode: a node, made of an id in N\mathbb{N}N and a Boolean "eligible" flag;
  • cs.currentTerm∈Ncs.\mathrm{currentTerm} \in \mathbb{N}cs.currentTerm∈N;
  • cs.lastAcceptedStatecs.\mathrm{lastAcceptedState}cs.lastAcceptedState: a cluster state with a term ∈N\in \mathbb{N}∈N, a version ∈Z\in \mathbb{Z}∈Z, a metadata version ∈Z\in \mathbb{Z}∈Z, last committed and last accepted voting configurations, and further fields;
  • cs.joinVotescs.\mathrm{joinVotes}cs.joinVotes and cs.publishVotescs.\mathrm{publishVotes}cs.publishVotes: vote collections, which are lists of ids;
  • cs.startedJoinSinceLastRebootcs.\mathrm{startedJoinSinceLastReboot}cs.startedJoinSinceLastReboot and cs.electionWoncs.\mathrm{electionWon}cs.electionWon: Booleans;
  • cs.lastPublishedVersion∈Zcs.\mathrm{lastPublishedVersion} \in \mathbb{Z}cs.lastPublishedVersion∈Z;
  • cs.lastPublishedConfigurationcs.\mathrm{lastPublishedConfiguration}cs.lastPublishedConfiguration.

Abbreviations, all read from cs.lastAcceptedStatecs.\mathrm{lastAcceptedState}cs.lastAcceptedState:

  • lat(cs)\mathrm{lat}(cs)lat(cs) = its term;
  • lav(cs)\mathrm{lav}(cs)lav(cs) = its version;
  • lavm(cs)\mathrm{lavm}(cs)lavm(cs) = its metadata version if its term is 000, and its version otherwise;
  • C(cs)\mathrm{C}(cs)C(cs) = its last committed configuration;
  • A(cs)\mathrm{A}(cs)A(cs) = its last accepted configuration.

Configurations and votes.

  • A voting configuration is a strictly increasing list of ids. isEmpty\mathrm{isEmpty}isEmpty means the list is [ ][\,][].
  • isQuorum(v,c)\mathrm{isQuorum}(v, c)isQuorum(v,c) holds iff 2 ∣{x∈c.nodeIds:x∈v.nodes}∣>∣c.nodeIds∣2\,|\{x \in c.\mathrm{nodeIds} : x \in v.\mathrm{nodes}\}| > |c.\mathrm{nodeIds}|2∣{x∈c.nodeIds:x∈v.nodes}∣>∣c.nodeIds∣.
  • addVote(v,n)\mathrm{addVote}(v, n)addVote(v,n) returns (⟨n.id::v.nodes⟩,true)(\langle n.\mathrm{id} :: v.\mathrm{nodes}\rangle, \mathrm{true})(⟨n.id::v.nodes⟩,true) if nnn is eligible and n.id∉v.nodesn.\mathrm{id} \notin v.\mathrm{nodes}n.id∈/v.nodes, and (v,false)(v, \mathrm{false})(v,false) otherwise.

Election quorum. An election strategy eseses is an arbitrary Boolean function fesf_{es}fes​ of seven arguments.

isElectionQuorum(es,cs,v)=isQuorum(v,C(cs))∧isQuorum(v,A(cs))∧fes(cs.localNode,cs.currentTerm,lat(cs),lav(cs),C(cs),A(cs),v).\mathrm{isElectionQuorum}(es, cs, v) = \mathrm{isQuorum}(v, \mathrm{C}(cs)) \wedge \mathrm{isQuorum}(v, \mathrm{A}(cs)) \wedge f_{es}(cs.\mathrm{localNode}, cs.\mathrm{currentTerm}, \mathrm{lat}(cs), \mathrm{lav}(cs), \mathrm{C}(cs), \mathrm{A}(cs), v).isElectionQuorum(es,cs,v)=isQuorum(v,C(cs))∧isQuorum(v,A(cs))∧fes​(cs.localNode,cs.currentTerm,lat(cs),lav(cs),C(cs),A(cs),v).

Joins. A join jjj has two nodes, j.sourceNodej.\mathrm{sourceNode}j.sourceNode and j.targetNodej.\mathrm{targetNode}j.targetNode, a term j.term∈Nj.\mathrm{term} \in \mathbb{N}j.term∈N, j.lastAcceptedTerm∈Nj.\mathrm{lastAcceptedTerm} \in \mathbb{N}j.lastAcceptedTerm∈N and j.lastAcceptedVersion∈Zj.\mathrm{lastAcceptedVersion} \in \mathbb{Z}j.lastAcceptedVersion∈Z.

The handler handleJoin(es,cs,j)\mathrm{handleJoin}(es, cs, j)handleJoin(es,cs,j) tests five guards in order. The first one that holds gives error\mathrm{error}error:

  1. j.term≠cs.currentTermj.\mathrm{term} \ne cs.\mathrm{currentTerm}j.term=cs.currentTerm;
  2. ¬cs.startedJoinSinceLastReboot\neg cs.\mathrm{startedJoinSinceLastReboot}¬cs.startedJoinSinceLastReboot;
  3. j.lastAcceptedTerm>lat(cs)j.\mathrm{lastAcceptedTerm} > \mathrm{lat}(cs)j.lastAcceptedTerm>lat(cs);
  4. j.lastAcceptedTerm=lat(cs)∧j.lastAcceptedVersion>lavm(cs)j.\mathrm{lastAcceptedTerm} = \mathrm{lat}(cs) \wedge j.\mathrm{lastAcceptedVersion} > \mathrm{lavm}(cs)j.lastAcceptedTerm=lat(cs)∧j.lastAcceptedVersion>lavm(cs);
  5. isEmpty(A(cs))\mathrm{isEmpty}(\mathrm{A}(cs))isEmpty(A(cs)).

If no guard holds, the handler computes:

  • (v′,added):=addVote(cs.joinVotes,j.sourceNode)(v', \mathit{added}) := \mathrm{addVote}(cs.\mathrm{joinVotes}, j.\mathrm{sourceNode})(v′,added):=addVote(cs.joinVotes,j.sourceNode);
  • won:=isElectionQuorum(es,cs,v′)\mathit{won} := \mathrm{isElectionQuorum}(es, cs, v')won:=isElectionQuorum(es,cs,v′).

It returns ok(cs2,added)\mathrm{ok}(cs_2, \mathit{added})ok(cs2​,added). Here cs2cs_2cs2​ is cscscs with joinVotes:=v′\mathrm{joinVotes} := v'joinVotes:=v′ and electionWon:=won\mathrm{electionWon} := \mathit{won}electionWon:=won. In addition, lastPublishedVersion:=lav(cs)\mathrm{lastPublishedVersion} := \mathrm{lav}(cs)lastPublishedVersion:=lav(cs) if won\mathit{won}won holds and cs.electionWoncs.\mathrm{electionWon}cs.electionWon was false.

1. Declaration

Binders.

  • VVV (implicit);
  • eseses: an election strategy, arbitrary;
  • cscscs: a coordination state;
  • jjj: a join;
  • cs′cs'cs′: a coordination state;
  • bbb: a Boolean.

Hypothesis. hhh: handleJoin(es,cs,j)=ok(cs′,b)\mathrm{handleJoin}(es, cs, j) = \mathrm{ok}(cs', b)handleJoin(es,cs,j)=ok(cs′,b).

Conclusion. The conjunction of:

  1. j.term=cs.currentTermj.\mathrm{term} = cs.\mathrm{currentTerm}j.term=cs.currentTerm;
  2. cs.startedJoinSinceLastReboot=truecs.\mathrm{startedJoinSinceLastReboot} = \mathrm{true}cs.startedJoinSinceLastReboot=true;
  3. isEmpty(A(cs))=false\mathrm{isEmpty}(\mathrm{A}(cs)) = \mathrm{false}isEmpty(A(cs))=false;
  4. j.lastAcceptedTerm<lat(cs) ∨ (j.lastAcceptedTerm=lat(cs)∧j.lastAcceptedVersion≤lavm(cs))j.\mathrm{lastAcceptedTerm} < \mathrm{lat}(cs)\ \vee\ \big(j.\mathrm{lastAcceptedTerm} = \mathrm{lat}(cs) \wedge j.\mathrm{lastAcceptedVersion} \le \mathrm{lavm}(cs)\big)j.lastAcceptedTerm<lat(cs) ∨ (j.lastAcceptedTerm=lat(cs)∧j.lastAcceptedVersion≤lavm(cs));
  5. cs′.joinVotes=addVote(cs.joinVotes,j.sourceNode).1cs'.\mathrm{joinVotes} = \mathrm{addVote}(cs.\mathrm{joinVotes}, j.\mathrm{sourceNode}).1cs′.joinVotes=addVote(cs.joinVotes,j.sourceNode).1;
  6. b=addVote(cs.joinVotes,j.sourceNode).2b = \mathrm{addVote}(cs.\mathrm{joinVotes}, j.\mathrm{sourceNode}).2b=addVote(cs.joinVotes,j.sourceNode).2;
  7. cs′.electionWon=isElectionQuorum(es,cs,cs′.joinVotes)cs'.\mathrm{electionWon} = \mathrm{isElectionQuorum}(es, cs, cs'.\mathrm{joinVotes})cs′.electionWon=isElectionQuorum(es,cs,cs′.joinVotes), evaluated against the old state's configurations, terms and version;
  8. cs′.currentTerm=cs.currentTermcs'.\mathrm{currentTerm} = cs.\mathrm{currentTerm}cs′.currentTerm=cs.currentTerm;
  9. cs′.lastAcceptedState=cs.lastAcceptedStatecs'.\mathrm{lastAcceptedState} = cs.\mathrm{lastAcceptedState}cs′.lastAcceptedState=cs.lastAcceptedState;
  10. cs′.localNode=cs.localNodecs'.\mathrm{localNode} = cs.\mathrm{localNode}cs′.localNode=cs.localNode;
  11. cs′.startedJoinSinceLastReboot=cs.startedJoinSinceLastRebootcs'.\mathrm{startedJoinSinceLastReboot} = cs.\mathrm{startedJoinSinceLastReboot}cs′.startedJoinSinceLastReboot=cs.startedJoinSinceLastReboot;
  12. cs′.publishVotes=cs.publishVotescs'.\mathrm{publishVotes} = cs.\mathrm{publishVotes}cs′.publishVotes=cs.publishVotes;
  13. cs′.lastPublishedConfiguration=cs.lastPublishedConfigurationcs'.\mathrm{lastPublishedConfiguration} = cs.\mathrm{lastPublishedConfiguration}cs′.lastPublishedConfiguration=cs.lastPublishedConfiguration;
  14. cs′.lastPublishedVersion=lav(cs)cs'.\mathrm{lastPublishedVersion} = \mathrm{lav}(cs)cs′.lastPublishedVersion=lav(cs) if cs′.electionWon=true∧cs.electionWon=falsecs'.\mathrm{electionWon} = \mathrm{true} \wedge cs.\mathrm{electionWon} = \mathrm{false}cs′.electionWon=true∧cs.electionWon=false, and cs′.lastPublishedVersion=cs.lastPublishedVersioncs'.\mathrm{lastPublishedVersion} = cs.\mathrm{lastPublishedVersion}cs′.lastPublishedVersion=cs.lastPublishedVersion 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 cs′cs'cs′, and conjunct 6 fixes bbb. Since conjuncts 8–10 keep every input of the election test unchanged, conjunct 7 could equally be evaluated on cs′cs'cs′.

2. What is not constrained

  • j.targetNodej.\mathrm{targetNode}j.targetNode is never mentioned. The handler does not check that the join is addressed to this node; Java only asserts it.
  • j.sourceNodej.\mathrm{sourceNode}j.sourceNode is arbitrary. If it is ineligible, or its id is already present, then cs′.joinVotes=cs.joinVotescs'.\mathrm{joinVotes} = cs.\mathrm{joinVotes}cs′.joinVotes=cs.joinVotes and b=falseb = \mathrm{false}b=false. Even so, the election flag is recomputed.
  • There is no invariant hypothesis. So the statement covers states whose electionWon\mathrm{electionWon}electionWon disagrees with the quorum test. For such a state, a successful join can turn electionWon\mathrm{electionWon}electionWon from true\mathrm{true}true to false\mathrm{false}false. Conjunct 7 then forces that, and conjunct 14 leaves lastPublishedVersion\mathrm{lastPublishedVersion}lastPublishedVersion 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 lavm(cs)\mathrm{lavm}(cs)lavm(cs), the metadata version for term-0 states.
    • The strategy argument inside isElectionQuorum\mathrm{isElectionQuorum}isElectionQuorum and the new lastPublishedVersion\mathrm{lastPublishedVersion}lastPublishedVersion in conjunct 14 use the plain lav(cs)\mathrm{lav}(cs)lav(cs).
  • eseses 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.
Human review
  • Endorsed by Shuze Chen · Nov 1, 2026

    Confirmed by the moderator at approval.

  • Endorsed by pitimespi · Nov 1, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me