Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Only handleStartJoin changes the current term, and every handler keeps the accepted term at most the current term

Proved
OpenSearchCoordination.lastAcceptedTerm_le_currentTerm

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

cluster-coordinationconsensuscoordination-stateelasticsearchformal-verificationleader-electionopensearchpaxosquorumraftzen2

For every election strategy es and coordination state cs with cs.lastAcceptedTerm ≤ cs.currentTerm, every successful handler call on cs — for setInitialState s, one with s.term = 0, one of the method's asserted preconditions (a conjunct of initialStateContract, the only one assumed) — yields a state cs' with cs'.lastAcceptedTerm ≤ cs'.currentTerm, and moreover:

  • cs.setInitialState s = .ok cs' with s.term = 0 leaves the current term unchanged;
  • cs.handleStartJoin r = .ok (cs', j) strictly increases it: cs.currentTerm < cs'.currentTerm;
  • cs.handleJoin es j, cs.handleClientValue s, cs.handlePublishRequest p, cs.handlePublishResponse n r and cs.handleCommit c, when they succeed, leave it unchanged.

So the first assertion of invariant(), getLastAcceptedTerm() <= getCurrentTerm(), is preserved by one successful call of any handler, and along successful calls on one node that start from a state satisfying it (with term-0 states for setInitialState) the current term changes only at handleStartJoin, upwards. The statement is about single steps; it does not mention init, whose result satisfies the inequality exactly when s.term ≤ t (the hypothesis of init_javaInvariant).

Preamble
import Definitions.Def_OpenSearchCoordination
Formal statement
theorem OpenSearchCoordination.lastAcceptedTerm_le_currentTerm {V : Type} (es : ElectionStrategy) (cs : CoordinationState V)
    (hcs : cs.lastAcceptedTerm ≤ cs.currentTerm) :
    (∀ s cs', cs.setInitialState s = .ok cs' → s.term = 0 → cs'.lastAcceptedTerm ≤ cs'.currentTerm ∧
        cs'.currentTerm = cs.currentTerm) ∧
    (∀ r cs' j, cs.handleStartJoin r = .ok (cs', j) → cs'.lastAcceptedTerm ≤ cs'.currentTerm ∧
        cs.currentTerm < cs'.currentTerm) ∧
    (∀ j cs' b, cs.handleJoin es j = .ok (cs', b) → cs'.lastAcceptedTerm ≤ cs'.currentTerm ∧
        cs'.currentTerm = cs.currentTerm) ∧
    (∀ s cs' p, cs.handleClientValue s = .ok (cs', p) → cs'.lastAcceptedTerm ≤ cs'.currentTerm ∧
        cs'.currentTerm = cs.currentTerm) ∧
    (∀ p cs' r, cs.handlePublishRequest p = .ok (cs', r) → cs'.lastAcceptedTerm ≤ cs'.currentTerm ∧
        cs'.currentTerm = cs.currentTerm) ∧
    (∀ n r cs' o, cs.handlePublishResponse n r = .ok (cs', o) → cs'.lastAcceptedTerm ≤ cs'.currentTerm ∧
        cs'.currentTerm = cs.currentTerm) ∧
    (∀ c cs', cs.handleCommit c = .ok cs' → cs'.lastAcceptedTerm ≤ cs'.currentTerm ∧
        cs'.currentTerm = cs.currentTerm) := 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.lastAcceptedTerm_le_currentTerm

Notions used

Coordination states. A coordination state cscscs over a payload type VVV has nine fields:

  • localNode;
  • currentTerm∈N\mathrm{currentTerm} \in \mathbb{N}currentTerm∈N;
  • lastAcceptedState, a cluster state with a term ∈N\in \mathbb{N}∈N, a version ∈Z\in \mathbb{Z}∈Z, two voting configurations, and further fields;
  • joinVotes;
  • startedJoinSinceLastReboot;
  • electionWon;
  • lastPublishedVersion;
  • lastPublishedConfiguration;
  • publishVotes.

Abbreviations:

  • lat(cs)=cs.lastAcceptedState.term\mathrm{lat}(cs) = cs.\mathrm{lastAcceptedState}.\mathrm{term}lat(cs)=cs.lastAcceptedState.term;
  • lav(cs)=cs.lastAcceptedState.version\mathrm{lav}(cs) = cs.\mathrm{lastAcceptedState}.\mathrm{version}lav(cs)=cs.lastAcceptedState.version;
  • A(cs)\mathrm{A}(cs)A(cs) = the accepted state's last accepted configuration.

The seven handlers. Here is what each one does to currentTerm\mathrm{currentTerm}currentTerm and lastAcceptedState\mathrm{lastAcceptedState}lastAcceptedState when it returns ok\mathrm{ok}ok; their other effects do not matter for this statement.

  • setInitialState(cs,S)\mathrm{setInitialState}(cs, S)setInitialState(cs,S) succeeds iff A(cs)\mathrm{A}(cs)A(cs) is empty. The result is cscscs with lastAcceptedState:=S\mathrm{lastAcceptedState} := SlastAcceptedState:=S. Nothing about SSS is checked, in particular not S.termS.\mathrm{term}S.term.
  • handleStartJoin(cs,r)\mathrm{handleStartJoin}(cs, r)handleStartJoin(cs,r) succeeds iff r.term>cs.currentTermr.\mathrm{term} > cs.\mathrm{currentTerm}r.term>cs.currentTerm. The result's currentTerm\mathrm{currentTerm}currentTerm is r.termr.\mathrm{term}r.term, and lastAcceptedState\mathrm{lastAcceptedState}lastAcceptedState is unchanged. A join is also returned.
  • handleJoin(es,cs,j)\mathrm{handleJoin}(es, cs, j)handleJoin(es,cs,j) leaves both fields unchanged. It changes only votes, the won flag and the published version. A Boolean is also returned.
  • handleClientValue(cs,S)\mathrm{handleClientValue}(cs, S)handleClientValue(cs,S) leaves both fields unchanged. It changes the published version and configuration and the publish votes. A publish request is also returned.
  • handlePublishRequest(cs,R)\mathrm{handlePublishRequest}(cs, R)handlePublishRequest(cs,R) succeeds only if R.acceptedState.term=cs.currentTermR.\mathrm{acceptedState}.\mathrm{term} = cs.\mathrm{currentTerm}R.acceptedState.term=cs.currentTerm. The result is cscscs with lastAcceptedState:=R.acceptedState\mathrm{lastAcceptedState} := R.\mathrm{acceptedState}lastAcceptedState:=R.acceptedState. A publish response is also returned.
  • handlePublishResponse(cs,n,r)\mathrm{handlePublishResponse}(cs, n, r)handlePublishResponse(cs,n,r) leaves both fields unchanged. It changes only the publish votes. An optional commit request is also returned.
  • handleCommit(cs,c)\mathrm{handleCommit}(cs, c)handleCommit(cs,c) replaces lastAcceptedState\mathrm{lastAcceptedState}lastAcceptedState by markCommitted\mathrm{markCommitted}markCommitted of it. That operation changes only the committed configuration and a UUID flag; the term is unchanged. currentTerm\mathrm{currentTerm}currentTerm is also unchanged.

1. Declaration

Binders.

  • VVV (implicit);
  • eseses: an election strategy, an arbitrary Boolean function used inside handleJoin;
  • cscscs: a coordination state.

Hypothesis. hcs\mathit{hcs}hcs: lat(cs)≤cs.currentTerm\mathrm{lat}(cs) \le cs.\mathrm{currentTerm}lat(cs)≤cs.currentTerm.

Conclusion. A conjunction of seven clauses, one per handler:

  1. ∀S cs′, setInitialState(cs,S)=ok(cs′)→S.term=0→lat(cs′)≤cs′.currentTerm∧cs′.currentTerm=cs.currentTerm\forall S\ cs',\ \mathrm{setInitialState}(cs, S) = \mathrm{ok}(cs') \to S.\mathrm{term} = 0 \to \mathrm{lat}(cs') \le cs'.\mathrm{currentTerm} \wedge cs'.\mathrm{currentTerm} = cs.\mathrm{currentTerm}∀S cs′, setInitialState(cs,S)=ok(cs′)→S.term=0→lat(cs′)≤cs′.currentTerm∧cs′.currentTerm=cs.currentTerm.
  2. ∀r cs′ j, handleStartJoin(cs,r)=ok(cs′,j)→lat(cs′)≤cs′.currentTerm∧cs.currentTerm<cs′.currentTerm\forall r\ cs'\ j,\ \mathrm{handleStartJoin}(cs, r) = \mathrm{ok}(cs', j) \to \mathrm{lat}(cs') \le cs'.\mathrm{currentTerm} \wedge cs.\mathrm{currentTerm} < cs'.\mathrm{currentTerm}∀r cs′ j, handleStartJoin(cs,r)=ok(cs′,j)→lat(cs′)≤cs′.currentTerm∧cs.currentTerm<cs′.currentTerm.
  3. ∀j cs′ b, handleJoin(es,cs,j)=ok(cs′,b)→lat(cs′)≤cs′.currentTerm∧cs′.currentTerm=cs.currentTerm\forall j\ cs'\ b,\ \mathrm{handleJoin}(es, cs, j) = \mathrm{ok}(cs', b) \to \mathrm{lat}(cs') \le cs'.\mathrm{currentTerm} \wedge cs'.\mathrm{currentTerm} = cs.\mathrm{currentTerm}∀j cs′ b, handleJoin(es,cs,j)=ok(cs′,b)→lat(cs′)≤cs′.currentTerm∧cs′.currentTerm=cs.currentTerm.
  4. ∀S cs′ p, handleClientValue(cs,S)=ok(cs′,p)→\forall S\ cs'\ p,\ \mathrm{handleClientValue}(cs, S) = \mathrm{ok}(cs', p) \to∀S cs′ p, handleClientValue(cs,S)=ok(cs′,p)→ (the same two facts as in 3).
  5. ∀R cs′ r, handlePublishRequest(cs,R)=ok(cs′,r)→\forall R\ cs'\ r,\ \mathrm{handlePublishRequest}(cs, R) = \mathrm{ok}(cs', r) \to∀R cs′ r, handlePublishRequest(cs,R)=ok(cs′,r)→ (the same).
  6. ∀n r cs′ o, handlePublishResponse(cs,n,r)=ok(cs′,o)→\forall n\ r\ cs'\ o,\ \mathrm{handlePublishResponse}(cs, n, r) = \mathrm{ok}(cs', o) \to∀n r cs′ o, handlePublishResponse(cs,n,r)=ok(cs′,o)→ (the same).
  7. ∀c cs′, handleCommit(cs,c)=ok(cs′)→\forall c\ cs',\ \mathrm{handleCommit}(cs, c) = \mathrm{ok}(cs') \to∀c cs′, handleCommit(cs,c)=ok(cs′)→ (the same).

Each clause says two things:

  • One successful step of that handler from cscscs yields a state cs′cs'cs′ whose last-accepted term is at most its current term.
  • The current term strictly increases (clause 2) or is unchanged (all other clauses).

2. What is not constrained

  • Clause 1 has its own extra hypothesis, S.term=0S.\mathrm{term} = 0S.term=0. This is the only part of Java's setInitialState assertions (initialStateContract) that is used. setInitialState does not check it, so without it the clause could fail: S.term>cs.currentTermS.\mathrm{term} > cs.\mathrm{currentTerm}S.term>cs.currentTerm would be accepted. Clause 1 does not need hcs\mathit{hcs}hcs.
  • This is one-step preservation, not an invariant. The name suggests an invariant, but the content is preservation by a single step from any state satisfying hcs\mathit{hcs}hcs.
    • The statement does not mention init. Separately, init(n, t, S) satisfies the inequality only when S.term≤tS.\mathrm{term} \le tS.term≤t.
    • It says nothing about sequences of steps or reachability.
  • eseses matters only for clause 3.
  • Clause 5 claims less than holds. It states only ≤\le≤, but in fact lat(cs′)=cs.currentTerm\mathrm{lat}(cs') = cs.\mathrm{currentTerm}lat(cs′)=cs.currentTerm.
  • No other fields are mentioned.
  • Each clause's antecedent is satisfiable, so the statement is not vacuous. If a handler fails on some input, that clause is vacuous for that input.

3. Plain-language summary

Starting from any coordination state whose last-accepted term is at most its current term, each of the seven handlers, when it succeeds, produces a state with the same property. handleStartJoin strictly increases the current term, and every other handler leaves it unchanged. For setInitialState this is claimed only for initial states of term 000.

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