Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

handlePublishResponse commits only on a publish quorum of both configurations

Proved
OpenSearchCoordination.handlePublishResponse_spec

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

cluster-coordinationconsensuscoordination-stateelasticsearchformal-verificationleader-electionopensearchpaxosquorumraftzen2

For every coordination state cs, node src, publish response r, state cs' and optional commit o: if cs.handlePublishResponse src r = .ok (cs', o) then

  • cs.electionWon = true, r.term = cs.currentTerm and r.version = cs.lastPublishedVersion;
  • cs' is cs with publish votes (cs.publishVotes.addVote src).1;
  • if o = some c, then c is the commit ⟨cs.localNode, cs.currentTerm, cs.lastPublishedVersion⟩ (sent by this node, for its current term and the version being published), and the new publish votes are a quorum of cs.lastCommittedConfiguration and of cs.lastPublishedConfiguration, the configuration being published.

The statement says when a commit can be emitted; it is one-directional: it does not say that a commit is emitted whenever the new votes are a publish quorum, and it says nothing when o = none.

Preamble
import Definitions.Def_OpenSearchCoordination
Formal statement
theorem OpenSearchCoordination.handlePublishResponse_spec {V : Type} (cs : CoordinationState V) (src : DiscoveryNode) (r : PublishResponse)
    (cs' : CoordinationState V) (o : Option ApplyCommitRequest) (h : cs.handlePublishResponse src r = .ok (cs', o)) :
    cs.electionWon = true ∧ r.term = cs.currentTerm ∧ r.version = cs.lastPublishedVersion ∧
    cs' = { cs with publishVotes := (cs.publishVotes.addVote src).1 } ∧
    (∀ c, o = some c →
      c = ⟨cs.localNode, cs.currentTerm, cs.lastPublishedVersion⟩ ∧
      cs'.publishVotes.isQuorum cs.lastCommittedConfiguration = true ∧
      cs'.publishVotes.isQuorum cs.lastPublishedConfiguration = true) := 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.handlePublishResponse_spec

Notions used

Coordination states. A coordination state cscscs has nine fields:

  • cs.localNodecs.\mathrm{localNode}cs.localNode, a node with an id and an eligibility flag;
  • cs.currentTerm∈Ncs.\mathrm{currentTerm} \in \mathbb{N}cs.currentTerm∈N;
  • cs.lastAcceptedStatecs.\mathrm{lastAcceptedState}cs.lastAcceptedState;
  • 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.

C(cs)\mathrm{C}(cs)C(cs) is the last committed configuration of cs.lastAcceptedStatecs.\mathrm{lastAcceptedState}cs.lastAcceptedState.

Votes and quorums.

  • isQuorum(v,c)\mathrm{isQuorum}(v, c)isQuorum(v,c) holds iff strictly more than half of the ids of configuration ccc occur in v.nodesv.\mathrm{nodes}v.nodes.
  • 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.
  • isPublishQuorum(cs,v)=isQuorum(v,C(cs))∧isQuorum(v,cs.lastPublishedConfiguration)\mathrm{isPublishQuorum}(cs, v) = \mathrm{isQuorum}(v, \mathrm{C}(cs)) \wedge \mathrm{isQuorum}(v, cs.\mathrm{lastPublishedConfiguration})isPublishQuorum(cs,v)=isQuorum(v,C(cs))∧isQuorum(v,cs.lastPublishedConfiguration).

Messages.

  • A publish response rrr has r.term∈Nr.\mathrm{term} \in \mathbb{N}r.term∈N and r.version∈Zr.\mathrm{version} \in \mathbb{Z}r.version∈Z.
  • A commit request is a triple ⟨sourceNode,term∈N,version∈Z⟩\langle \mathrm{sourceNode}, \mathrm{term} \in \mathbb{N}, \mathrm{version} \in \mathbb{Z}\rangle⟨sourceNode,term∈N,version∈Z⟩.

The handler handlePublishResponse(cs,n,r)\mathrm{handlePublishResponse}(cs, n, r)handlePublishResponse(cs,n,r) tests three guards in order. The first one that holds yields error\mathrm{error}error:

  1. ¬cs.electionWon\neg cs.\mathrm{electionWon}¬cs.electionWon;
  2. r.term≠cs.currentTermr.\mathrm{term} \ne cs.\mathrm{currentTerm}r.term=cs.currentTerm;
  3. r.version≠cs.lastPublishedVersionr.\mathrm{version} \ne cs.\mathrm{lastPublishedVersion}r.version=cs.lastPublishedVersion.

Otherwise, let v′=addVote(cs.publishVotes,n).1v' = \mathrm{addVote}(cs.\mathrm{publishVotes}, n).1v′=addVote(cs.publishVotes,n).1 and cs∗=cscs^\ast = cscs∗=cs with publishVotes:=v′\mathrm{publishVotes} := v'publishVotes:=v′. The result is:

  • ok(cs∗,some ⟨cs.localNode,r.term,r.version⟩)\mathrm{ok}(cs^\ast, \mathrm{some}\ \langle cs.\mathrm{localNode}, r.\mathrm{term}, r.\mathrm{version}\rangle)ok(cs∗,some ⟨cs.localNode,r.term,r.version⟩) if isPublishQuorum(cs∗,v′)\mathrm{isPublishQuorum}(cs^\ast, v')isPublishQuorum(cs∗,v′);
  • ok(cs∗,none)\mathrm{ok}(cs^\ast, \mathrm{none})ok(cs∗,none) otherwise.

1. Declaration

Binders.

  • VVV (implicit);
  • cscscs: a coordination state;
  • nnn (src): a node;
  • rrr: a publish response;
  • cs′cs'cs′: a coordination state;
  • ooo: an optional commit request.

Hypothesis. hhh: handlePublishResponse(cs,n,r)=ok(cs′,o)\mathrm{handlePublishResponse}(cs, n, r) = \mathrm{ok}(cs', o)handlePublishResponse(cs,n,r)=ok(cs′,o).

Conclusion. The conjunction of:

  1. cs.electionWon=truecs.\mathrm{electionWon} = \mathrm{true}cs.electionWon=true;
  2. r.term=cs.currentTermr.\mathrm{term} = cs.\mathrm{currentTerm}r.term=cs.currentTerm;
  3. r.version=cs.lastPublishedVersionr.\mathrm{version} = cs.\mathrm{lastPublishedVersion}r.version=cs.lastPublishedVersion;
  4. cs′=cscs' = cscs′=cs with publishVotes:=addVote(cs.publishVotes,n).1\mathrm{publishVotes} := \mathrm{addVote}(cs.\mathrm{publishVotes}, n).1publishVotes:=addVote(cs.publishVotes,n).1;
  5. ∀c, o=some c→\forall c,\ o = \mathrm{some}\ c \to∀c, o=some c→ the following three facts hold:
    • c=⟨cs.localNode, cs.currentTerm, cs.lastPublishedVersion⟩c = \langle cs.\mathrm{localNode},\ cs.\mathrm{currentTerm},\ cs.\mathrm{lastPublishedVersion}\ranglec=⟨cs.localNode, cs.currentTerm, cs.lastPublishedVersion⟩;
    • isQuorum(cs′.publishVotes,C(cs))=true\mathrm{isQuorum}(cs'.\mathrm{publishVotes}, \mathrm{C}(cs)) = \mathrm{true}isQuorum(cs′.publishVotes,C(cs))=true;
    • isQuorum(cs′.publishVotes,cs.lastPublishedConfiguration)=true\mathrm{isQuorum}(cs'.\mathrm{publishVotes}, cs.\mathrm{lastPublishedConfiguration}) = \mathrm{true}isQuorum(cs′.publishVotes,cs.lastPublishedConfiguration)=true.

Conjuncts 1–3 are the negations of the guards. Conjunct 4 determines cs′cs'cs′ completely. Conjunct 5 constrains the returned commit request, if there is one: its term and version equal the node's current term and last published version, and the updated publish votes form a quorum of both the committed and the last published configuration (not the accepted one).

2. What is not constrained

  • When o=noneo = \mathrm{none}o=none, nothing is claimed. The theorem does not say that "none" means the votes fail to be a publish quorum. Equally, it does not say that a commit request is returned whenever a quorum is reached, although by definition the handler is deterministic and does return one.
  • nnn is arbitrary. If nnn is ineligible or already counted, the votes are unchanged. If a quorum already holds, a commit request is returned again; the statement permits this.
  • The commit's source node is the local node. The responding node nnn does not appear in the returned request.
  • No assumption on cscscs beyond success, and no invariant.
  • Not vacuous. The success hypothesis is satisfiable, for example by a node that has won the election and receives a response matching its current term and published version.

3. Plain-language summary

A node processes a publish response only if:

  • it has won the election;
  • the response's term equals its current term;
  • the response's version equals its last published version.

The only state change is adding the responder (if eligible) to the publish votes. If a commit request is returned, it comes from the local node for the current term and the last published version, and the updated publish votes form a quorum of both the last committed and the last published configurations.

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