Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

handleClientValue publishes only as an elected node, in its term, above the last version, reconfiguring only safely

Proved
OpenSearchCoordination.handleClientValue_spec

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

cluster-coordinationconsensuscoordination-stateelasticsearchformal-verificationleader-electionopensearchpaxosquorumraftzen2

For every coordination state cs, cluster state s, state cs' and publish request p: if cs.handleClientValue s = .ok (cs', p) then

  • cs.electionWon = true;
  • cs.lastPublishedVersion = cs.lastAcceptedVersion: the node has accepted its own last publication;
  • s.term = cs.currentTerm and cs.lastAcceptedVersion < s.version (so the new version is above the last published one);
  • s keeps the node's last accepted configuration (s.lastAcceptedConfiguration = cs.lastAcceptedConfiguration), or no reconfiguration is pending (cs.lastCommittedConfiguration = cs.lastAcceptedConfiguration);
  • the node's join votes are a quorum of the new accepted configuration: cs.joinVotes.isQuorum s.lastAcceptedConfiguration = true;
  • p is the publish request of s, and cs' is cs with lastPublishedVersion := s.version, lastPublishedConfiguration := s.lastAcceptedConfiguration and empty publish votes.

The asserted precondition that s keeps the node's last committed configuration (clientValueContract, CoordinationState.java:397-398) is a caller contract and is not part of the statement.

Preamble
import Definitions.Def_OpenSearchCoordination
Formal statement
theorem OpenSearchCoordination.handleClientValue_spec {V : Type} (cs : CoordinationState V) (s : ClusterState V) (cs' : CoordinationState V)
    (p : PublishRequest V) (h : cs.handleClientValue s = .ok (cs', p)) :
    cs.electionWon = true ∧ cs.lastPublishedVersion = cs.lastAcceptedVersion ∧ s.term = cs.currentTerm ∧
    cs.lastAcceptedVersion < s.version ∧
    (s.lastAcceptedConfiguration = cs.lastAcceptedConfiguration ∨
      cs.lastCommittedConfiguration = cs.lastAcceptedConfiguration) ∧
    cs.joinVotes.isQuorum s.lastAcceptedConfiguration = true ∧
    p = ⟨s⟩ ∧ cs' = { cs with lastPublishedVersion := s.version,
                               lastPublishedConfiguration := s.lastAcceptedConfiguration,
                               publishVotes := VoteCollection.empty } := 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.handleClientValue_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;
  • 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 (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 cluster state SSS has nine independent fields:

  • 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 cluster-manager id;
  • two Booleans about the cluster UUID;
  • a payload.

Abbreviations, all read from the accepted state:

  • lav(cs)=cs.lastAcceptedState.version\mathrm{lav}(cs) = cs.\mathrm{lastAcceptedState}.\mathrm{version}lav(cs)=cs.lastAcceptedState.version;
  • C(cs)\mathrm{C}(cs)C(cs) is the last committed configuration;
  • A(cs)\mathrm{A}(cs)A(cs) is the last accepted configuration.

Configurations and votes.

  • Voting configurations are strictly increasing lists of ids. Two configurations are equal iff they denote the same set.
  • 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∣.
  • VoteCollection.empty\mathrm{VoteCollection.empty}VoteCollection.empty is the empty list.

A publish request is a wrapper ⟨S⟩\langle S\rangle⟨S⟩ around one cluster state.

The handler handleClientValue(cs,S)\mathrm{handleClientValue}(cs, S)handleClientValue(cs,S) tests six guards in order. The first one that holds yields error\mathrm{error}error:

  1. ¬cs.electionWon\neg cs.\mathrm{electionWon}¬cs.electionWon;
  2. cs.lastPublishedVersion≠lav(cs)cs.\mathrm{lastPublishedVersion} \ne \mathrm{lav}(cs)cs.lastPublishedVersion=lav(cs);
  3. S.term≠cs.currentTermS.\mathrm{term} \ne cs.\mathrm{currentTerm}S.term=cs.currentTerm;
  4. S.version≤cs.lastPublishedVersionS.\mathrm{version} \le cs.\mathrm{lastPublishedVersion}S.version≤cs.lastPublishedVersion;
  5. S.lastAcceptedConfiguration≠A(cs)∧C(cs)≠A(cs)S.\mathrm{lastAcceptedConfiguration} \ne \mathrm{A}(cs) \wedge \mathrm{C}(cs) \ne \mathrm{A}(cs)S.lastAcceptedConfiguration=A(cs)∧C(cs)=A(cs);
  6. ¬isQuorum(cs.joinVotes,S.lastAcceptedConfiguration)\neg\mathrm{isQuorum}(cs.\mathrm{joinVotes}, S.\mathrm{lastAcceptedConfiguration})¬isQuorum(cs.joinVotes,S.lastAcceptedConfiguration).

If no guard holds, the result is

ok(cs with lastPublishedVersion:=S.version, lastPublishedConfiguration:=S.lastAcceptedConfiguration, publishVotes:=empty; ⟨S⟩).\mathrm{ok}\big(cs \text{ with } \mathrm{lastPublishedVersion} := S.\mathrm{version},\ \mathrm{lastPublishedConfiguration} := S.\mathrm{lastAcceptedConfiguration},\ \mathrm{publishVotes} := \mathrm{empty};\ \langle S\rangle\big).ok(cs with lastPublishedVersion:=S.version, lastPublishedConfiguration:=S.lastAcceptedConfiguration, publishVotes:=empty; ⟨S⟩).

1. Declaration

Binders.

  • VVV (implicit);
  • cscscs: a coordination state;
  • SSS (s): a cluster state;
  • cs′cs'cs′: a coordination state;
  • ppp: a publish request.

Hypothesis. hhh: handleClientValue(cs,S)=ok(cs′,p)\mathrm{handleClientValue}(cs, S) = \mathrm{ok}(cs', p)handleClientValue(cs,S)=ok(cs′,p).

Conclusion. The conjunction of:

  1. cs.electionWon=truecs.\mathrm{electionWon} = \mathrm{true}cs.electionWon=true;
  2. cs.lastPublishedVersion=lav(cs)cs.\mathrm{lastPublishedVersion} = \mathrm{lav}(cs)cs.lastPublishedVersion=lav(cs);
  3. S.term=cs.currentTermS.\mathrm{term} = cs.\mathrm{currentTerm}S.term=cs.currentTerm;
  4. lav(cs)<S.version\mathrm{lav}(cs) < S.\mathrm{version}lav(cs)<S.version;
  5. S.lastAcceptedConfiguration=A(cs) ∨ C(cs)=A(cs)S.\mathrm{lastAcceptedConfiguration} = \mathrm{A}(cs)\ \vee\ \mathrm{C}(cs) = \mathrm{A}(cs)S.lastAcceptedConfiguration=A(cs) ∨ C(cs)=A(cs);
  6. isQuorum(cs.joinVotes,S.lastAcceptedConfiguration)=true\mathrm{isQuorum}(cs.\mathrm{joinVotes}, S.\mathrm{lastAcceptedConfiguration}) = \mathrm{true}isQuorum(cs.joinVotes,S.lastAcceptedConfiguration)=true;
  7. p=⟨S⟩p = \langle S\ranglep=⟨S⟩;
  8. cs′=cscs' = cscs′=cs with lastPublishedVersion:=S.version\mathrm{lastPublishedVersion} := S.\mathrm{version}lastPublishedVersion:=S.version, lastPublishedConfiguration:=S.lastAcceptedConfiguration\mathrm{lastPublishedConfiguration} := S.\mathrm{lastAcceptedConfiguration}lastPublishedConfiguration:=S.lastAcceptedConfiguration and publishVotes:=VoteCollection.empty\mathrm{publishVotes} := \mathrm{VoteCollection.empty}publishVotes:=VoteCollection.empty.

Conjuncts 1–6 are the negations of the six guards. Conjunct 4 is stated against lav(cs)\mathrm{lav}(cs)lav(cs) rather than cs.lastPublishedVersioncs.\mathrm{lastPublishedVersion}cs.lastPublishedVersion; given conjunct 2 the two are equivalent. Conjunct 5 means: either the value keeps the accepted configuration, or no reconfiguration is pending. Conjuncts 7 and 8 determine the output completely.

2. What is not constrained

  • The committed configuration of SSS is free. S.lastCommittedConfigurationS.\mathrm{lastCommittedConfiguration}S.lastCommittedConfiguration appears in neither the hypotheses nor the conclusion. The handler does not check it. Java's assertion that it equals C(cs)\mathrm{C}(cs)C(cs) is the separate predicate clientValueContract, which is not used here. So the statement allows publishing a value whose committed configuration differs from the node's.
  • Other fields of SSS are free: S.metadataVersionS.\mathrm{metadataVersion}S.metadataVersion, the cluster-manager id, the UUID flags and the payload.
  • The configuration test is set equality. "Equal" in conjunct 5 compares sets, because configurations are stored sorted.
  • No hypothesis on cscscs beyond success, and no invariant.
  • Only one direction. The statement goes from success to the conjuncts. It does not claim that a value meeting 1–6 is accepted, although by definition it is.
  • Not vacuous. For example, a winner with matching versions, given a value of the current term with a higher version and the same accepted configuration, satisfies the hypothesis whenever its join votes are a quorum of that configuration.

3. Plain-language summary

A node accepts a new cluster state for publication only if all of the following hold:

  • it has won the election;
  • its previous publication has been accepted locally (published version equals accepted version);
  • the new state is in the current term with a strictly higher version;
  • it does not start a reconfiguration while one is pending;
  • its join votes form a quorum of the new state's accepted configuration.

The result is a publish request carrying the state unchanged. The node records the new published version and configuration and clears its publish votes.

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