Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

handleStartJoin succeeds exactly when the term increases; it moves to that term and votes for the requester

Proved
OpenSearchCoordination.handleStartJoin_spec

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

cluster-coordinationconsensuscoordination-stateelasticsearchformal-verificationleader-electionopensearchpaxosquorumraftzen2

For every coordination state cs, start-join request req, state cs' and join j: cs.handleStartJoin req = .ok (cs', j) holds iff all of the following hold:

  • cs.currentTerm < req.term, and cs'.currentTerm = req.term;
  • cs' has the last accepted state and the local node of cs;
  • cs'.startedJoinSinceLastReboot = true and cs'.electionWon = false;
  • the join votes and the publish votes of cs' are VoteCollection.empty;
  • cs'.lastPublishedVersion = 0 and cs'.lastPublishedConfiguration = cs.lastAcceptedConfiguration;
  • j is the join from cs.localNode to req.sourceNode in term req.term, carrying cs.lastAcceptedTerm and cs.lastAcceptedVersionOrMetadataVersion (the last accepted state's version, or its metadata version if its term is 0).

The conditions on cs' fix all nine of its fields, so the result of a successful call is determined; a request whose term is not above the current term is rejected.

Preamble
import Definitions.Def_OpenSearchCoordination
Formal statement
theorem OpenSearchCoordination.handleStartJoin_spec {V : Type} (cs : CoordinationState V) (req : StartJoinRequest) (cs' : CoordinationState V)
    (j : Join) :
    cs.handleStartJoin req = .ok (cs', j) ↔
      cs.currentTerm < req.term ∧ cs'.currentTerm = req.term ∧ cs'.lastAcceptedState = cs.lastAcceptedState ∧
      cs'.localNode = cs.localNode ∧ cs'.startedJoinSinceLastReboot = true ∧ cs'.electionWon = false ∧
      cs'.joinVotes = VoteCollection.empty ∧ cs'.publishVotes = VoteCollection.empty ∧
      cs'.lastPublishedVersion = 0 ∧ cs'.lastPublishedConfiguration = cs.lastAcceptedConfiguration ∧
      j = ⟨cs.localNode, req.sourceNode, req.term, cs.lastAcceptedTerm, cs.lastAcceptedVersionOrMetadataVersion⟩ := 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.handleStartJoin_spec

Notions used

Coordination states and cluster 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 isClusterManagerNode;
  • cs.currentTerm∈Ncs.\mathrm{currentTerm} \in \mathbb{N}cs.currentTerm∈N;
  • cs.lastAcceptedStatecs.\mathrm{lastAcceptedState}cs.lastAcceptedState: a cluster state;
  • 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: a voting configuration.

A cluster state SSS has:

  • S.term∈NS.\mathrm{term} \in \mathbb{N}S.term∈N;
  • S.version,S.metadataVersion∈ZS.\mathrm{version}, S.\mathrm{metadataVersion} \in \mathbb{Z}S.version,S.metadataVersion∈Z;
  • two voting configurations, S.lastCommittedConfigurationS.\mathrm{lastCommittedConfiguration}S.lastCommittedConfiguration and S.lastAcceptedConfigurationS.\mathrm{lastAcceptedConfiguration}S.lastAcceptedConfiguration;
  • an optional natural S.clusterManagerNodeS.\mathrm{clusterManagerNode}S.clusterManagerNode;
  • two Booleans about the cluster UUID;
  • a payload S.value∈VS.\mathrm{value} \in VS.value∈V.

The file's accessors give these abbreviations:

  • lat(cs)=cs.lastAcceptedState.term\mathrm{lat}(cs) = cs.\mathrm{lastAcceptedState}.\mathrm{term}lat(cs)=cs.lastAcceptedState.term;
  • A(cs)=cs.lastAcceptedState.lastAcceptedConfiguration\mathrm{A}(cs) = cs.\mathrm{lastAcceptedState}.\mathrm{lastAcceptedConfiguration}A(cs)=cs.lastAcceptedState.lastAcceptedConfiguration;
  • lavm(cs)\mathrm{lavm}(cs)lavm(cs) is the accepted state's metadataVersion\mathrm{metadataVersion}metadataVersion if its term is 000, and its version\mathrm{version}version otherwise (lastAcceptedVersionOrMetadataVersion).

VoteCollection.empty\mathrm{VoteCollection.empty}VoteCollection.empty is the empty list.

Messages. A start-join request rrr has a node r.sourceNoder.\mathrm{sourceNode}r.sourceNode and a term r.term∈Nr.\mathrm{term} \in \mathbb{N}r.term∈N. A join is a 5-tuple ⟨sourceNode,targetNode,term,lastAcceptedTerm,lastAcceptedVersion⟩\langle \mathrm{sourceNode}, \mathrm{targetNode}, \mathrm{term}, \mathrm{lastAcceptedTerm}, \mathrm{lastAcceptedVersion}\rangle⟨sourceNode,targetNode,term,lastAcceptedTerm,lastAcceptedVersion⟩ of two nodes, two naturals and an integer.

The handler handleStartJoin(cs,r)\mathrm{handleStartJoin}(cs, r)handleStartJoin(cs,r):

  • If r.term≤cs.currentTermr.\mathrm{term} \le cs.\mathrm{currentTerm}r.term≤cs.currentTerm, it returns error\mathrm{error}error.
  • Otherwise it returns ok(cs∗,J)\mathrm{ok}(cs^\ast, J)ok(cs∗,J), where:
    • cs∗cs^\astcs∗ is cscscs with currentTerm:=r.term\mathrm{currentTerm} := r.\mathrm{term}currentTerm:=r.term, lastPublishedVersion:=0\mathrm{lastPublishedVersion} := 0lastPublishedVersion:=0, lastPublishedConfiguration:=A(cs)\mathrm{lastPublishedConfiguration} := \mathrm{A}(cs)lastPublishedConfiguration:=A(cs), startedJoinSinceLastReboot:=true\mathrm{startedJoinSinceLastReboot} := \mathrm{true}startedJoinSinceLastReboot:=true, electionWon:=false\mathrm{electionWon} := \mathrm{false}electionWon:=false, joinVotes:=empty\mathrm{joinVotes} := \mathrm{empty}joinVotes:=empty and publishVotes:=empty\mathrm{publishVotes} := \mathrm{empty}publishVotes:=empty;
    • J=⟨cs.localNode, r.sourceNode, r.term, lat(cs), lavm(cs)⟩J = \langle cs.\mathrm{localNode},\ r.\mathrm{sourceNode},\ r.\mathrm{term},\ \mathrm{lat}(cs),\ \mathrm{lavm}(cs)\rangleJ=⟨cs.localNode, r.sourceNode, r.term, lat(cs), lavm(cs)⟩.

1. Declaration

Binders.

  • VVV: a type (implicit);
  • cscscs: a coordination state over VVV;
  • rrr (req): a start-join request;
  • cs′cs'cs′: a coordination state over VVV;
  • jjj: a join.

Hypotheses. None.

Conclusion. The statement is a biconditional:

handleStartJoin(cs,r)=ok(cs′,j)  ⟺  (1)∧⋯∧(11),\mathrm{handleStartJoin}(cs, r) = \mathrm{ok}(cs', j) \iff (1) \wedge \dots \wedge (11),handleStartJoin(cs,r)=ok(cs′,j)⟺(1)∧⋯∧(11),

where:

  1. cs.currentTerm<r.termcs.\mathrm{currentTerm} < r.\mathrm{term}cs.currentTerm<r.term;
  2. cs′.currentTerm=r.termcs'.\mathrm{currentTerm} = r.\mathrm{term}cs′.currentTerm=r.term;
  3. cs′.lastAcceptedState=cs.lastAcceptedStatecs'.\mathrm{lastAcceptedState} = cs.\mathrm{lastAcceptedState}cs′.lastAcceptedState=cs.lastAcceptedState;
  4. cs′.localNode=cs.localNodecs'.\mathrm{localNode} = cs.\mathrm{localNode}cs′.localNode=cs.localNode;
  5. cs′.startedJoinSinceLastReboot=truecs'.\mathrm{startedJoinSinceLastReboot} = \mathrm{true}cs′.startedJoinSinceLastReboot=true;
  6. cs′.electionWon=falsecs'.\mathrm{electionWon} = \mathrm{false}cs′.electionWon=false;
  7. cs′.joinVotes=VoteCollection.emptycs'.\mathrm{joinVotes} = \mathrm{VoteCollection.empty}cs′.joinVotes=VoteCollection.empty;
  8. cs′.publishVotes=VoteCollection.emptycs'.\mathrm{publishVotes} = \mathrm{VoteCollection.empty}cs′.publishVotes=VoteCollection.empty;
  9. cs′.lastPublishedVersion=0cs'.\mathrm{lastPublishedVersion} = 0cs′.lastPublishedVersion=0;
  10. cs′.lastPublishedConfiguration=A(cs)cs'.\mathrm{lastPublishedConfiguration} = \mathrm{A}(cs)cs′.lastPublishedConfiguration=A(cs);
  11. j=⟨cs.localNode, r.sourceNode, r.term, lat(cs), lavm(cs)⟩j = \langle cs.\mathrm{localNode},\ r.\mathrm{sourceNode},\ r.\mathrm{term},\ \mathrm{lat}(cs),\ \mathrm{lavm}(cs)\ranglej=⟨cs.localNode, r.sourceNode, r.term, lat(cs), lavm(cs)⟩.

Conjuncts 2–10 fix all nine fields of cs′cs'cs′, and conjunct 11 fixes jjj. So the right-hand side says exactly that the guard holds and that (cs′,j)(cs', j)(cs′,j) is the handler's output.

The biconditional therefore characterizes the handler completely:

  • It succeeds iff r.term>cs.currentTermr.\mathrm{term} > cs.\mathrm{currentTerm}r.term>cs.currentTerm, and its output is then the one listed.
  • When r.term≤cs.currentTermr.\mathrm{term} \le cs.\mathrm{currentTerm}r.term≤cs.currentTerm the result is not ok\mathrm{ok}ok of anything, so it is an error\mathrm{error}error.

2. What is not constrained

  • cscscs is arbitrary. No invariant is assumed. In particular, lat(cs)≤cs.currentTerm\mathrm{lat}(cs) \le cs.\mathrm{currentTerm}lat(cs)≤cs.currentTerm is not required.
  • r.sourceNoder.\mathrm{sourceNode}r.sourceNode is arbitrary. It may be the local node itself, and it may be ineligible. It appears only as the target of the returned join.
  • The old joinVotes\mathrm{joinVotes}joinVotes, publishVotes\mathrm{publishVotes}publishVotes, electionWon\mathrm{electionWon}electionWon and lastPublishedVersion\mathrm{lastPublishedVersion}lastPublishedVersion are discarded whatever their values.
  • The join's version field is lavm(cs)\mathrm{lavm}(cs)lavm(cs): the metadata version when the accepted state's term is 000, otherwise the cluster-state version.
  • There are no hypotheses, so nothing can make the statement vacuous. Both sides of the biconditional are satisfiable.

3. Plain-language summary

A start-join request succeeds exactly when its term is larger than the node's current term. The node then:

  • adopts that term;
  • keeps its accepted state and identity;
  • resets its election and publication bookkeeping: votes emptied, election not won, published version 000, published configuration set to the accepted configuration;
  • records that it has started a join since restart.

It returns a join vote from itself to the requester, carrying the new term and its last accepted term and version (the metadata version for term-0 states).

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