Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

OpenSearch pre-voting: pre-vote requests and responses, pre-voting rounds, the election they trigger, and the election scheduler's delays

Definition
OpenSearchPreVote

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

cluster-coordinationconsensuselasticsearchelection-schedulerformal-verificationleader-electionopensearchpaxospre-voteraftzen2

A transcription of PreVoteCollector, the parts of Coordinator it calls, and the delay computation of ElectionSchedulerFactory, at OpenSearch revision b2a54ba5c0defba3d1d20423e911d4bf920bab19, over the per-node CoordinationState of the OpenSearchCoordination mission (whose DiscoveryNode, ClusterState, VoteCollection, ElectionStrategy, Join, CoordinationState, handleStartJoin and handleJoin are used as they are).

Messages. PreVoteRequest — the requesting node and its current term. PreVoteResponse — the responder's current term, and the term and the version (the metadata version, for a term-0 state) of its last accepted state. preVoteResponseOf cs — the response a node with coordination state cs gives: cs.currentTerm, cs.lastAcceptedTerm, cs.lastAcceptedVersionOrMetadataVersion (Coordinator.getPreVoteResponse).

Answering. CollectorState — the known leader (none when no leader is known) and the node's own response, as last set by the Coordinator (itself when it becomes leader, the leader it follows, none when it becomes a candidate). handlePreVoteRequest healthy st req — rejects if the node is not healthy; otherwise answers with st.response if the node knows no leader or knows req.sourceNode as its leader, and rejects if it knows another leader.

Rounds. PreVotingRound V — the requester's last accepted cluster state when the round started, the requester (localNode), the recorded pre-votes as a list of (sender, response) pairs, most recent first, and the flags electionStarted and isClosed. PreVotingRound.start s n — an open round over s for requester n, with no pre-votes and no election started. votes r — the vote collection built by adding the vote of each recorded sender to the empty collection (only cluster-manager-eligible senders count). isElectionQuorumFor es n t at av committed accepted votes — ElectionStrategy.isElectionQuorum with explicit arguments: votes is a quorum of committed and of accepted, and the strategy's additional constraint holds for the local node n, current term t, accepted term at and version av, the two configurations and votes.

r.handlePreVoteResponse es lr resp sender (PVC:225-279) returns the new round, whether startElection is called, and the term passed to updateMaxTermSeen (none if none is passed); lr is the requester's own current response, read when the response arrives. If the round is closed: unchanged, false, none. Otherwise, if resp is fresher than the round's accepted state s — resp.lastAcceptedTerm > s.term, or equal terms and resp.lastAcceptedVersion > s.versionOrMetadataVersion — the round is unchanged, with false and some resp.currentTerm. Otherwise the pair (sender, resp) replaces any earlier entry of sender; if the new votes are not an election quorum (isElectionQuorumFor es r.localNode lr.currentTerm lr.lastAcceptedTerm lr.lastAcceptedVersion over the last committed and last accepted configurations of s), or the round has already started an election, the result is that round with false; otherwise the round with electionStarted set, and true. In every case but the closed one, the term passed is some resp.currentTerm. close r — the round with isClosed set.

NoFresher resp s — resp.lastAcceptedTerm < s.term, or resp.lastAcceptedTerm = s.term and resp.lastAcceptedVersion ≤ s.versionOrMetadataVersion: the responses a round records. RoundReachable es Delivered — the rounds obtained from start s n (any s, n) by handling, any number of times and in any order, responses resp from senders n with Delivered n resp (each step with an arbitrary requester response lr), and by close.

The election. handleJoins es cs js — the joins of js handled in order by CoordinationState.handleJoin; a rejected join leaves the state unchanged. For joins whose term is not above the node's current term this is Coordinator.handleJoin (CO:1267-1299); a join of a higher term is rejected here (term mismatch), whereas the Coordinator first moves the node to that term (CO:1269). The joins' target is not checked (Java asserts it). startElectionTerm currentTerm maxTermSeen — max currentTerm maxTermSeen + 1, the term of the StartJoinRequest that startElection sends (CO:593). nodeMayWinElection s excluded n — n is in the last committed or the last accepted configuration of s, or is not among the excluded ids (CO:628-633); it is not used by the theorems.

The scheduler (times in milliseconds). SchedulerSettings — initialTimeout, backoffTime, maxTimeout, duration. Valid — the setting ranges (1 ≤ initialTimeout ≤ 10000, 1 ≤ backoffTime ≤ 60000, 200 ≤ maxTimeout ≤ 300000, 1 ≤ duration ≤ 300000) and the constructor's check initialTimeout ≤ maxTimeout. default — 100, 100, 10000, 500 (not used by the theorems). maxDelay s k — min(maxTimeout, initialTimeout + k · backoffTime), the bound for attempt k (counted from 0). nonNegative n — 0 for n = -2^63 (Long.MIN_VALUE), |n| otherwise. toPositiveLongAtMost r b — nonNegative r mod b + 1. attemptDelay s k r g — toPositiveLongAtMost r (maxDelay s k) + g, the delay of attempt k for the drawn random long r and the grace period g, a free parameter (Java passes 0 for the first attempt, CO:1574, and duration for the later ones, ESF:218; the field duration occurs only in Valid).

Formalization Note. The Coordinator's side effects are not modelled. The argument of updateMaxTermSeen is returned by handlePreVoteResponse, and not at all by handlePreVoteRequest (where it is always the request's term); the call's effect is outside these functions: in particular a leader whose current term is below the largest term it has seen moves to that term and starts an election, at once or, while a publication is in progress, when that publication ends (CO:560-581, CO:1784). Nodes are compared by id and role, while Java's DiscoveryNode.equals compares ephemeral ids, which change at each restart: the two can differ only between two incarnations of one node with the same role. The election strategy sees voter ids only (the per-node mission's abstraction). Health is a Boolean parameter, the network is the delivery predicate of RoundReachable, and the random long is any integer: the theorems hold for every value. Only the per-node mission's definitions are imported.

Definition code
import Definitions.Def_OpenSearchCoordination

/-!
# OpenSearch cluster coordination: pre-voting and election scheduling

Before a node starts an election it runs a **pre-voting round** (`PreVoteCollector`, OpenSearch
`b2a54ba5c0defba3d1d20423e911d4bf920bab19`,
`server/src/main/java/org/opensearch/cluster/coordination/PreVoteCollector.java`, cited `PVC:<line>`): it asks the nodes
it has discovered, including itself, for a pre-vote. A node answers with its current term and the term and version of
its last accepted state, unless it is unhealthy or already follows a leader other than the requester. The round counts
the answers that are no fresher than the requester's own accepted state, and when they form an election quorum the
requester starts an election (`Coordinator.startElection`, Coordinator.java, cited `CO:<line>`): it sends a
`StartJoinRequest` in a term above every term it has seen. Pre-voting rounds are started by an **election scheduler**
(`ElectionSchedulerFactory`, cited `ESF:<line>`) at randomized, backed-off intervals.

The pre-vote messages and handlers are transcribed below as functions. Both handlers raise the Coordinator's
`maxTermSeen` (`updateMaxTermSeen`, CO:560-581): `handlePreVoteRequest` first of all, with the request's term (PVC:134);
`handlePreVoteResponse` once it has found the round open, with the response's current term, before the freshness test
(PVC:226-231). `handlePreVoteResponse` returns the term it passes (`none` when the round is closed);
`handlePreVoteRequest` returns nothing, its argument being always the request's term. When `maxTermSeen` exceeds the
current term of a leader, the leader moves to that term and starts an election itself, at once or, while a publication
is in progress, when that publication ends (CO:564-578, CO:1784); that effect is outside these functions.

Node equality: Java's `DiscoveryNode.equals` compares ephemeral ids, which change when a node restarts; here nodes are
compared by id and role. The two can differ only between two incarnations of the same node with the same role, which
Java treats as different nodes (so a follower of a node's previous incarnation with the same role refuses that node's
pre-vote request in Java, and accepts it here).
-/

namespace OpenSearchPreVote

open OpenSearchCoordination

variable {V : Type}

/-- `PreVoteRequest` (PreVoteRequest.java): the requesting node and its current term. -/
structure PreVoteRequest where
  sourceNode : DiscoveryNode
  currentTerm : Nat
  deriving DecidableEq, Repr

/-- `PreVoteResponse` (PreVoteResponse.java): the responder's current term and the term and version (or metadata
version, for a term-0 state) of its last accepted state. -/
structure PreVoteResponse where
  currentTerm : Nat
  lastAcceptedTerm : Nat
  lastAcceptedVersion : Int
  deriving DecidableEq, Repr

/-- `Coordinator.getPreVoteResponse()` (CO:873-879): the response a node gives, computed from its coordination state. -/
def preVoteResponseOf (cs : CoordinationState V) : PreVoteResponse :=
  ⟨cs.currentTerm, cs.lastAcceptedTerm, cs.lastAcceptedVersionOrMetadataVersion⟩

/-- The pre-vote collector's state (PVC:79): the known leader (`none` is Java `null`, no known leader) and the node's
own response, both as last set by `update` (PVC:128-131) — `Coordinator` sets the leader to itself when it becomes
leader, to the leader it follows when it becomes a follower, and to `null` when it becomes a candidate (CO:516, 653, 777,
801, 839, 1157). Java's state is `null` before the first `update`; a node answers pre-votes only after it. -/
structure CollectorState where
  leader : Option DiscoveryNode
  response : PreVoteResponse
  deriving DecidableEq, Repr

/-- `PreVoteCollector.handlePreVoteRequest(request)` (PVC:133-163). `healthy` is the node health status
(`nodeHealthService.getHealth()`). A node that knows a leader other than the requester refuses. (Before answering, the
handler calls `updateMaxTermSeen(request.getCurrentTerm())`, PVC:134; see the module documentation.) -/
def handlePreVoteRequest (healthy : Bool) (st : CollectorState) (req : PreVoteRequest) :
    Except String PreVoteResponse :=
  if !healthy then .error "rejecting on unhealthy node"
  else match st.leader with
    | none => .ok st.response
    | some l => if l = req.sourceNode then .ok st.response else .error "rejecting as there is already a leader"

/-- A pre-voting round (`PreVoteCollector.PreVotingRound`, PVC:175-300): the last accepted cluster state of the
requester when the round started, the requester, the pre-votes received so far (Java: a map keyed by sender; here a
list, most recent first, which in every reachable round has at most one entry per sender, a sender being a node value,
id and role, as `round_entries` proves; the type itself allows repeats), whether it has started an election, and
whether it was closed.
Java takes the requester from the round's cluster state (`clusterState.nodes().getLocalNode()`, PVC:244); the request's
term (PVC:112) is not needed here. -/
structure PreVotingRound (V : Type) where
  clusterState : ClusterState V
  localNode : DiscoveryNode
  preVotesReceived : List (DiscoveryNode × PreVoteResponse)
  electionStarted : Bool
  isClosed : Bool

/-- `PreVoteCollector.start` (PVC:111-115): a new, open round over the requester's last accepted state. -/
def PreVotingRound.start (s : ClusterState V) (localNode : DiscoveryNode) : PreVotingRound V :=
  ⟨s, localNode, [], false, false⟩

/-- The `VoteCollection` the round builds from its pre-votes (PVC:242-257): `addJoinVote` of a join from each sender,
which counts the cluster-manager-eligible senders. -/
def PreVotingRound.votes (r : PreVotingRound V) : VoteCollection :=
  r.preVotesReceived.foldr (fun p v => (v.addVote p.1).1) VoteCollection.empty

/-- `ElectionStrategy.isElectionQuorum` (ElectionStrategy.java:68-88), as called with explicit arguments. -/
def isElectionQuorumFor (es : ElectionStrategy) (localNode : DiscoveryNode) (currentTerm acceptedTerm : Nat)
    (acceptedVersion : Int) (committed accepted : VotingConfiguration) (votes : VoteCollection) : Bool :=
  votes.isQuorum committed && votes.isQuorum accepted &&
    es.satisfiesAdditionalQuorumConstraints localNode currentTerm acceptedTerm acceptedVersion committed accepted votes

/-- `PreVotingRound.handlePreVoteResponse(response, sender)` (PVC:225-279). `localResponse` is the requester's own
current response (`getPreVoteResponse()`, read when the response arrives). Returns the new round, whether
`startElection` is called, and the argument of the `updateMaxTermSeen` call (`none` when the round is closed and the
response is ignored before it). A response fresher than the round's accepted state is ignored. -/
def PreVotingRound.handlePreVoteResponse (es : ElectionStrategy) (localResponse : PreVoteResponse)
    (r : PreVotingRound V) (resp : PreVoteResponse) (sender : DiscoveryNode) :
    PreVotingRound V × Bool × Option Nat :=
  if r.isClosed then (r, false, none)
  else if resp.lastAcceptedTerm > r.clusterState.term ∨
      (resp.lastAcceptedTerm = r.clusterState.term ∧
        resp.lastAcceptedVersion > r.clusterState.versionOrMetadataVersion) then
    (r, false, some resp.currentTerm)
  else
    let r₁ : PreVotingRound V :=
      { r with preVotesReceived := (sender, resp) :: r.preVotesReceived.filter (fun p => p.1 ≠ sender) }
    if !isElectionQuorumFor es r.localNode localResponse.currentTerm localResponse.lastAcceptedTerm
        localResponse.lastAcceptedVersion r.clusterState.lastCommittedConfiguration
        r.clusterState.lastAcceptedConfiguration r₁.votes then
      (r₁, false, some resp.currentTerm)
    else if r₁.electionStarted then
      (r₁, false, some resp.currentTerm)
    else
      ({ r₁ with electionStarted := true }, true, some resp.currentTerm)

/-- `PreVotingRound.close()` (PVC:296-299). -/
def PreVotingRound.close (r : PreVotingRound V) : PreVotingRound V := { r with isClosed := true }

/-- A pre-vote response is no fresher than the accepted state `s`: its accepted (term, version) is lexicographically at
most `s`'s (term, version-or-metadata-version) — the responses a round counts (PVC:233-238). -/
def NoFresher (resp : PreVoteResponse) (s : ClusterState V) : Prop :=
  resp.lastAcceptedTerm < s.term ∨
    (resp.lastAcceptedTerm = s.term ∧ resp.lastAcceptedVersion ≤ s.versionOrMetadataVersion)

/-- The rounds a node can be in: started over any cluster state for any requester (in Java, over the requester's last
accepted state; the theorems that need this link assume it), then any sequence of responses handled — each response
from a sender and with a content allowed by `Delivered` — and possibly closed. `localResponse` (the requester's own
current response) is arbitrary at each step. -/
inductive RoundReachable (es : ElectionStrategy) (Delivered : DiscoveryNode → PreVoteResponse → Prop) :
    PreVotingRound V → Prop where
  | start (s : ClusterState V) (n : DiscoveryNode) : RoundReachable es Delivered (PreVotingRound.start s n)
  | handle (r : PreVotingRound V) (localResponse resp : PreVoteResponse) (sender : DiscoveryNode) :
      RoundReachable es Delivered r → Delivered sender resp →
      RoundReachable es Delivered (r.handlePreVoteResponse es localResponse resp sender).1
  | close (r : PreVotingRound V) : RoundReachable es Delivered r → RoundReachable es Delivered r.close

/-- The joins a node handles, in the order given, as `Coordinator.handleJoin` (CO:1267-1287, with
`handleJoinIgnoringExceptions`, CO:1289-1299) does for joins whose term is not above the node's current term. A join
of a higher term is rejected here (term mismatch), whereas the `Coordinator` first moves the node to that term
(CO:1269). A rejected join leaves the state unchanged: `handleJoin` throws before changing anything, and
`Coordinator.handleJoin` either propagates the exception to the joining node or ignores it. The joins' target node is
not checked (Java asserts it, CoordinationState.java:265). -/
def handleJoins (es : ElectionStrategy) (cs : CoordinationState V) (js : List Join) : CoordinationState V :=
  js.foldl (fun cs j => match cs.handleJoin es j with
    | .ok (cs', _) => cs'
    | .error _ => cs) cs

/-- The term of the election `Coordinator.startElection` starts (CO:583-602): one above the larger of the current term
and the largest term seen. -/
def startElectionTerm (currentTerm maxTermSeen : Nat) : Nat := max currentTerm maxTermSeen + 1

/-- `Coordinator.nodeMayWinElection` (CO:628-633): the node is in the last committed or last accepted configuration,
or it is not excluded from voting. `excluded` lists the node ids of the voting-configuration exclusions. -/
def nodeMayWinElection (s : ClusterState V) (excluded : List NodeId) (n : NodeId) : Bool :=
  s.lastCommittedConfiguration.nodeIds.contains n || s.lastAcceptedConfiguration.nodeIds.contains n ||
    !(excluded.contains n)

/-! ## Election scheduling (`ElectionSchedulerFactory`) -/

/-- The scheduler settings, in milliseconds (ESF:85-115): `cluster.election.initial_timeout` (default 100, range
1..10000), `cluster.election.back_off_time` (default 100, range 1..60000), `cluster.election.max_timeout` (default 10000,
range 200..300000, at least the initial timeout), `cluster.election.duration` (default 500, range 1..300000). -/
structure SchedulerSettings where
  initialTimeout : Nat
  backoffTime : Nat
  maxTimeout : Nat
  duration : Nat

/-- The settings' validity (setting bounds, ESF:85-115, and the constructor check, ESF:133-143). -/
def SchedulerSettings.Valid (s : SchedulerSettings) : Prop :=
  1 ≤ s.initialTimeout ∧ s.initialTimeout ≤ 10000 ∧ 1 ≤ s.backoffTime ∧ s.backoffTime ≤ 60000 ∧
  200 ≤ s.maxTimeout ∧ s.maxTimeout ≤ 300000 ∧ s.initialTimeout ≤ s.maxTimeout ∧ 1 ≤ s.duration ∧ s.duration ≤ 300000

/-- The defaults. -/
def SchedulerSettings.default : SchedulerSettings := ⟨100, 100, 10000, 500⟩

/-- The bound on the delay of attempt `k` (ESF:203): `min(maxTimeout, initialTimeout + k * backoffTime)`. -/
def maxDelay (s : SchedulerSettings) (k : Nat) : Nat := min s.maxTimeout (s.initialTimeout + k * s.backoffTime)

/-- `nonNegative(n)` (ESF:159-161), defined on every integer: `-2^63` (`Long.MIN_VALUE`) maps to 0, every other `n` to
`|n|`. On a Java `long`, `n ∈ [-2^63, 2^63)`, this is Java's value. -/
def nonNegative (n : Int) : Nat := if n = -2 ^ 63 then 0 else n.natAbs

/-- `toPositiveLongAtMost(randomNumber, upperBound)` (ESF:169-172): `nonNegative(randomNumber) % upperBound + 1`, with
the natural-number remainder (for `upperBound = 0`, which Java's assertion `0 < upperBound` excludes, this is
`nonNegative(randomNumber) + 1`). -/
def toPositiveLongAtMost (randomNumber : Int) (upperBound : Nat) : Nat := nonNegative randomNumber % upperBound + 1

/-- The delay before attempt `k` fires, given the random long drawn for it and the grace period (ESF:195-204). The grace
period is a parameter: Java passes 0 for the first attempt (`Coordinator.startElectionScheduler`, CO:1574) and
`duration` for every later one (ESF:218); `SchedulerSettings.duration` is read only by `Valid`. -/
def attemptDelay (s : SchedulerSettings) (k : Nat) (randomNumber : Int) (gracePeriod : Nat) : Nat :=
  toPositiveLongAtMost randomNumber (maxDelay s k) + gracePeriod

end OpenSearchPreVote
Source
OpenSearch b2a54ba5c0defba3d1d20423e911d4bf920bab19: PreVoteCollector (state line 79, start 111-115, update 128-131, handlePreVoteRequest 133-163, PreVotingRound 175-300, handlePreVoteResponse 225-279, close 296-299): https://github.com/opensearch-project/OpenSearch/blob/b2a54ba5c0defba3d1d20423e911d4bf920bab19/server/src/main/java/org/opensearch/cluster/coordination/PreVoteCollector.java#L66-L301; Coordinator (updateMaxTermSeen lines 560-581, startElection 583-602, nodeMayWinElection 628-633, getPreVoteResponse 873-879, handleJoin 1267-1299, startElectionScheduler 1567-1618, the preVoteCollector.update calls 516, 653, 777, 801, 839, 1157): https://github.com/opensearch-project/OpenSearch/blob/b2a54ba5c0defba3d1d20423e911d4bf920bab19/server/src/main/java/org/opensearch/cluster/coordination/Coordinator.java#L560-L633; ElectionSchedulerFactory (settings lines 85-115, constructor check 133-143, nonNegative 159-161, toPositiveLongAtMost 169-172, scheduleNextElection 195-241): https://github.com/opensearch-project/OpenSearch/blob/b2a54ba5c0defba3d1d20423e911d4bf920bab19/server/src/main/java/org/opensearch/cluster/coordination/ElectionSchedulerFactory.java#L62-L254; ElectionStrategy.isElectionQuorum (lines 68-88): https://github.com/opensearch-project/OpenSearch/blob/b2a54ba5c0defba3d1d20423e911d4bf920bab19/server/src/main/java/org/opensearch/cluster/coordination/ElectionStrategy.java#L68-L88; the messages PreVoteRequest.java and PreVoteResponse.java in the same directory; CoordinationState (handleStartJoin, handleJoin) as transcribed by the OpenSearchCoordination mission
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: Def_OpenSearchPreVote.lean

This file imports Definitions.Def_OpenSearchCoordination, opens that namespace (OpenSearchCoordination), and introduces 23 declarations in the namespace OpenSearchPreVote. Throughout, VVV is an arbitrary type (the opaque payload of a cluster state); it is implicit wherever it is not written. The imported notions these declarations use are expanded first. The declarations follow in file order.

Every declaration that cites Java was compared with the OpenSearch checkout at /home/user/opensearch-project/OpenSearch. git rev-parse HEAD there gives b2a54ba5c0defba3d1d20423e911d4bf920bab19, the revision the file cites. Each comparison is reported in a Source check line. PVC is PreVoteCollector.java, CO is Coordinator.java, ESF is ElectionSchedulerFactory.java, and all three are under server/src/main/java/org/opensearch/cluster/coordination/.

Imported notions, expanded

Node ids and discovery nodes. A node id is a natural number. A discovery node nnn is a pair: a node id n.idn.\mathrm{id}n.id and a Boolean n.cmn.\mathrm{cm}n.cm (isClusterManagerNode, "is cluster-manager-eligible"). Equality of discovery nodes is structural: n=n′n = n'n=n′ iff n.id=n′.idn.\mathrm{id} = n'.\mathrm{id}n.id=n′.id and n.cm=n′.cmn.\mathrm{cm} = n'.\mathrm{cm}n.cm=n′.cm. So ⟨5,true⟩≠⟨5,false⟩\langle 5, \mathrm{true}\rangle \neq \langle 5, \mathrm{false}\rangle⟨5,true⟩=⟨5,false⟩. Two discovery nodes with the same id but different flags are different nodes.

Voting configurations. A voting configuration CCC is a strictly increasing list of node ids C.idsC.\mathrm{ids}C.ids, so it has no duplicates, bundled with a proof of that fact. isEmpty(C)\mathrm{isEmpty}(C)isEmpty(C) holds iff the list is empty. For any list XXX of node ids,

hasQuorum(C,X)  =  (2⋅∣{x∈C.ids:x∈X}∣  >  ∣C.ids∣),\mathrm{hasQuorum}(C, X) \;=\; \Big(2\cdot\big|\{x \in C.\mathrm{ids} : x \in X\}\big| \;>\; |C.\mathrm{ids}|\Big),hasQuorum(C,X)=(2⋅​{x∈C.ids:x∈X}​>∣C.ids∣),

a Boolean: strictly more than half of the configuration's ids occur in XXX. Duplicates in XXX and elements of XXX outside CCC make no difference. The empty configuration never has a quorum, because 0>00 > 00>0 is false.

Vote collections. A vote collection vvv is a list v.nodesv.\mathrm{nodes}v.nodes of node ids. empty\mathrm{empty}empty is the empty list. addVote(v,n)\mathrm{addVote}(v, n)addVote(v,n) returns a pair:

  • (⟨n.id::v.nodes⟩, true)(\langle n.\mathrm{id} :: v.\mathrm{nodes}\rangle,\ \mathrm{true})(⟨n.id::v.nodes⟩, true) if n.cm=truen.\mathrm{cm} = \mathrm{true}n.cm=true and n.id∉v.nodesn.\mathrm{id} \notin v.\mathrm{nodes}n.id∈/v.nodes;
  • (v,false)(v, \mathrm{false})(v,false) otherwise.

isQuorum(v,C)=hasQuorum(C,v.nodes)\mathrm{isQuorum}(v, C) = \mathrm{hasQuorum}(C, v.\mathrm{nodes})isQuorum(v,C)=hasQuorum(C,v.nodes).

Cluster states. A cluster state sss has these fields:

  • a term s.term∈Ns.\mathrm{term} \in \mathbb{N}s.term∈N;
  • a version s.version∈Zs.\mathrm{version} \in \mathbb{Z}s.version∈Z and a metadata version s.metadataVersion∈Zs.\mathrm{metadataVersion} \in \mathbb{Z}s.metadataVersion∈Z;
  • a last committed configuration s.committeds.\mathrm{committed}s.committed and a last accepted configuration s.accepteds.\mathrm{accepted}s.accepted;
  • an optional natural number (the cluster-manager node) and two Booleans (cluster UUID known, cluster UUID committed);
  • a payload of type VVV.

Its version-or-metadata-version is

vomv(s)={s.metadataVersionif s.term=0 (ZEN1_BWC_TERM),s.versionotherwise.\mathrm{vomv}(s) = \begin{cases} s.\mathrm{metadataVersion} & \text{if } s.\mathrm{term} = 0 \ (\texttt{ZEN1\_BWC\_TERM}),\\ s.\mathrm{version} & \text{otherwise.}\end{cases}vomv(s)={s.metadataVersions.version​if s.term=0 (ZEN1_BWC_TERM),otherwise.​

Election strategies. An election strategy eseses is just one arbitrary Boolean function extraes(n,t,a,w,Cc,Ca,v)\mathrm{extra}_{es}(n, t, a, w, C_c, C_a, v)extraes​(n,t,a,w,Cc​,Ca​,v) (satisfiesAdditionalQuorumConstraints). Its arguments are a discovery node, two naturals, an integer, two voting configurations and a vote collection. The default strategy DEFAULT_INSTANCE has extra≡true\mathrm{extra} \equiv \mathrm{true}extra≡true.

Start-join requests and joins. A start-join request is a pair (source node, term ∈N\in \mathbb{N}∈N). A join is a 5-tuple ⟨\langle⟨source node, target node, term ∈N\in \mathbb{N}∈N, last accepted term ∈N\in \mathbb{N}∈N, last accepted version ∈Z⟩\in \mathbb{Z}\rangle∈Z⟩.

Coordination states. A coordination state cscscs has these fields:

  • a local node cs.localNodecs.\mathrm{localNode}cs.localNode and a current term cs.currentTerm∈Ncs.\mathrm{currentTerm} \in \mathbb{N}cs.currentTerm∈N;
  • a last accepted state cs.lascs.\mathrm{las}cs.las (a cluster state);
  • a vote collection cs.joinVotescs.\mathrm{joinVotes}cs.joinVotes;
  • Booleans cs.startedJoinSinceLastRebootcs.\mathrm{startedJoinSinceLastReboot}cs.startedJoinSinceLastReboot and cs.electionWoncs.\mathrm{electionWon}cs.electionWon;
  • an integer cs.lastPublishedVersioncs.\mathrm{lastPublishedVersion}cs.lastPublishedVersion, a configuration cs.lastPublishedConfigurationcs.\mathrm{lastPublishedConfiguration}cs.lastPublishedConfiguration and a vote collection cs.publishVotescs.\mathrm{publishVotes}cs.publishVotes.

The accessors used below are:

  • lastAcceptedTerm(cs)=cs.las.term\mathrm{lastAcceptedTerm}(cs) = cs.\mathrm{las}.\mathrm{term}lastAcceptedTerm(cs)=cs.las.term;
  • lastAcceptedVersion(cs)=cs.las.version\mathrm{lastAcceptedVersion}(cs) = cs.\mathrm{las}.\mathrm{version}lastAcceptedVersion(cs)=cs.las.version;
  • lastAcceptedVersionOrMetadataVersion(cs)=vomv(cs.las)\mathrm{lastAcceptedVersionOrMetadataVersion}(cs) = \mathrm{vomv}(cs.\mathrm{las})lastAcceptedVersionOrMetadataVersion(cs)=vomv(cs.las);
  • the two configurations cs.las.committedcs.\mathrm{las}.\mathrm{committed}cs.las.committed and cs.las.acceptedcs.\mathrm{las}.\mathrm{accepted}cs.las.accepted.

The three coordination-state functions used here:

  • isElectionQuorum(es,cs,v)\mathrm{isElectionQuorum}(es, cs, v)isElectionQuorum(es,cs,v) is the conjunction of:

    • isQuorum(v,cs.las.committed)\mathrm{isQuorum}(v, cs.\mathrm{las}.\mathrm{committed})isQuorum(v,cs.las.committed);
    • isQuorum(v,cs.las.accepted)\mathrm{isQuorum}(v, cs.\mathrm{las}.\mathrm{accepted})isQuorum(v,cs.las.accepted);
    • extraes(cs.localNode,cs.currentTerm,cs.las.term,cs.las.version,cs.las.committed,cs.las.accepted,v)\mathrm{extra}_{es}(cs.\mathrm{localNode}, cs.\mathrm{currentTerm}, cs.\mathrm{las}.\mathrm{term}, cs.\mathrm{las}.\mathrm{version}, cs.\mathrm{las}.\mathrm{committed}, cs.\mathrm{las}.\mathrm{accepted}, v)extraes​(cs.localNode,cs.currentTerm,cs.las.term,cs.las.version,cs.las.committed,cs.las.accepted,v). The plain version is passed here, not vomv\mathrm{vomv}vomv.

    Under the default strategy it is just the two quorum tests.

  • handleStartJoin(cs,⟨src,T⟩)\mathrm{handleStartJoin}(cs, \langle src, T\rangle)handleStartJoin(cs,⟨src,T⟩). If T≤cs.currentTermT \le cs.\mathrm{currentTerm}T≤cs.currentTerm it returns an error. Otherwise it succeeds with a pair (cs′,j)(cs', j)(cs′,j):

    • cs′cs'cs′ is cscscs with: current term TTT, last published version 000, last published configuration cs.las.acceptedcs.\mathrm{las}.\mathrm{accepted}cs.las.accepted, startedJoinSinceLastReboot === true, electionWon === false, and both vote collections empty. The local node and the last accepted state are unchanged.
    • j=⟨cs.localNode, src, T, cs.las.term, vomv(cs.las)⟩j = \langle cs.\mathrm{localNode},\ src,\ T,\ cs.\mathrm{las}.\mathrm{term},\ \mathrm{vomv}(cs.\mathrm{las})\ranglej=⟨cs.localNode, src, T, cs.las.term, vomv(cs.las)⟩.
  • handleJoin(es,cs,j)\mathrm{handleJoin}(es, cs, j)handleJoin(es,cs,j). The guards are tested in this order, and the first that applies gives an error:

    1. j.term≠cs.currentTermj.\mathrm{term} \neq cs.\mathrm{currentTerm}j.term=cs.currentTerm;
    2. cs.startedJoinSinceLastReboot=falsecs.\mathrm{startedJoinSinceLastReboot} = \mathrm{false}cs.startedJoinSinceLastReboot=false;
    3. j.lastAcceptedTerm>cs.las.termj.\mathrm{lastAcceptedTerm} > cs.\mathrm{las}.\mathrm{term}j.lastAcceptedTerm>cs.las.term;
    4. j.lastAcceptedTerm=cs.las.termj.\mathrm{lastAcceptedTerm} = cs.\mathrm{las}.\mathrm{term}j.lastAcceptedTerm=cs.las.term and j.lastAcceptedVersion>vomv(cs.las)j.\mathrm{lastAcceptedVersion} > \mathrm{vomv}(cs.\mathrm{las})j.lastAcceptedVersion>vomv(cs.las);
    5. cs.las.acceptedcs.\mathrm{las}.\mathrm{accepted}cs.las.accepted is empty.

    If none applies, let (v′,added)=addVote(cs.joinVotes,j.source)(v', \mathit{added}) = \mathrm{addVote}(cs.\mathrm{joinVotes}, j.\mathrm{source})(v′,added)=addVote(cs.joinVotes,j.source) and won=isElectionQuorum(es,cs,v′)\mathit{won} = \mathrm{isElectionQuorum}(es, cs, v')won=isElectionQuorum(es,cs,v′). Let cs1cs_1cs1​ be cscscs with joinVotes v′v'v′ and electionWon won\mathit{won}won. Let cs2cs_2cs2​ be cs1cs_1cs1​ with lastPublishedVersion set to cs.las.versioncs.\mathrm{las}.\mathrm{version}cs.las.version when won\mathit{won}won is true and cs.electionWoncs.\mathrm{electionWon}cs.electionWon was false, and cs2=cs1cs_2 = cs_1cs2​=cs1​ otherwise. The result is success with (cs2,added)(cs_2, \mathit{added})(cs2​,added).

    The join's target node is never examined. Neither the current term, nor the local node, nor the last accepted state changes.


Declaration 1: PreVoteRequest

This is a structure with two fields: sourceNode\mathrm{sourceNode}sourceNode, a discovery node, and currentTerm∈N\mathrm{currentTerm} \in \mathbb{N}currentTerm∈N. Decidable equality and Repr are derived.

Source check: PreVoteRequest.java has exactly the fields DiscoveryNode sourceNode and long currentTerm (lines 50–51). The term is a natural number here instead of a Java long.

Declaration 2: PreVoteResponse

This is a structure with three fields: currentTerm∈N\mathrm{currentTerm} \in \mathbb{N}currentTerm∈N, lastAcceptedTerm∈N\mathrm{lastAcceptedTerm} \in \mathbb{N}lastAcceptedTerm∈N and lastAcceptedVersion∈Z\mathrm{lastAcceptedVersion} \in \mathbb{Z}lastAcceptedVersion∈Z. Decidable equality and Repr are derived. Nothing relates the fields to each other; for example, lastAcceptedTerm≤currentTerm\mathrm{lastAcceptedTerm} \le \mathrm{currentTerm}lastAcceptedTerm≤currentTerm is not required.

Source check: PreVoteResponse.java has the three long fields currentTerm, lastAcceptedTerm and lastAcceptedVersion (lines 48–50).

Declaration 3: preVoteResponseOf

For a coordination state cscscs:

preVoteResponseOf(cs)=⟨cs.currentTerm, cs.las.term, vomv(cs.las)⟩.\mathrm{preVoteResponseOf}(cs) = \langle cs.\mathrm{currentTerm},\ cs.\mathrm{las}.\mathrm{term},\ \mathrm{vomv}(cs.\mathrm{las})\rangle.preVoteResponseOf(cs)=⟨cs.currentTerm, cs.las.term, vomv(cs.las)⟩.

The version component is the version-or-metadata-version. It is the metadata version when the last accepted state has term 000.

Source check: CO:873–879 builds new PreVoteResponse(getCurrentTerm(), getLastAcceptedTerm(), getLastAcceptedState().getVersionOrMetadataVersion()), and getCurrentTerm() (CO:882–886) reads the coordination state's current term. Matches.

Declaration 4: CollectorState

This is a structure with two fields:

  • leader\mathrm{leader}leader: either "none" or "some lll" for a discovery node lll;
  • response\mathrm{response}response: a PreVoteResponse.

Decidable equality and Repr are derived. The type does not tie the response to any coordination state, or the leader to anything. Java's null state, before the first update, cannot be represented here: every value of this type is an initialized state.

Source check: PVC:79 declares Tuple<DiscoveryNode, PreVoteResponse> state, whose node is null when no leader is known. PVC:128–131, update, replaces both components. The docstring lists six update calls in Coordinator, and I checked each:

LineLeader passed to update
CO:516the local node (it publishes to itself)
CO:653null (joinLeaderInTerm while already a candidate)
CO:777null (becomeCandidate)
CO:801the local node (becomeLeader)
CO:839the leader node (becomeFollower)
CO:1157null (setInitialConfiguration)

All six match the docstring.

Declaration 5: handlePreVoteRequest

It takes healthy∈Bool\mathit{healthy} \in \mathrm{Bool}healthy∈Bool, a collector state ststst and a request reqreqreq, and returns either an error string or a PreVoteResponse. The cases, in order:

  1. If healthy=false\mathit{healthy} = \mathrm{false}healthy=false: error "rejecting on unhealthy node".
  2. Otherwise, if st.leader=nonest.\mathrm{leader} = \text{none}st.leader=none: success with st.responsest.\mathrm{response}st.response.
  3. Otherwise st.leader=some lst.\mathrm{leader} = \text{some } lst.leader=some l:
    • if l=req.sourceNodel = req.\mathrm{sourceNode}l=req.sourceNode (same id and same flag): success with st.responsest.\mathrm{response}st.response;
    • else: error "rejecting as there is already a leader".

Health is checked before the leader. On success the result is always the stored st.responsest.\mathrm{response}st.response, whatever the request. req.currentTermreq.\mathrm{currentTerm}req.currentTerm is never read.

Source check: PVC:133–163 does the following in order:

  • calls updateMaxTermSeen.accept(request.getCurrentTerm());
  • asserts the state is non-null;
  • throws NodeHealthCheckFailureException if the status is UNHEALTHY;
  • returns response if leader == null;
  • returns response if leader.equals(request.getSourceNode());
  • throws "there is already a leader" otherwise.

The order of the guards matches. Three differences:

  • The updateMaxTermSeen side effect is omitted, as the docstrings say.
  • Leader equality is by (id, role) instead of Java's ephemeral-id equals, as the module docstring says.
  • Health is a Boolean, read as "status is not UNHEALTHY". StatusInfo.java is not in the local checkout, so I could not confirm that the Java status has only two values.

Declaration 6: PreVotingRound V

This is a structure with five fields:

  • clusterState\mathrm{clusterState}clusterState: a cluster state;
  • localNode\mathrm{localNode}localNode: a discovery node;
  • preVotesReceived\mathrm{preVotesReceived}preVotesReceived: a list of pairs (sender, response);
  • electionStarted\mathrm{electionStarted}electionStarted: a Boolean;
  • isClosed\mathrm{isClosed}isClosed: a Boolean.

No equality instance is derived. The type itself imposes nothing:

  • The list may contain several entries for the same sender. The docstring's "at most one entry per sender" is not a property of the type. It is a property of the rounds the transition functions produce, and it is the second conjunct of round_entries.
  • localNode\mathrm{localNode}localNode is unrelated to clusterState\mathrm{clusterState}clusterState.
  • electionStarted\mathrm{electionStarted}electionStarted may be true with no quorum at all.

Source check: PVC:175–300, the inner class PreVotingRound, has these fields: a concurrent map preVotesReceived keyed by DiscoveryNode, an AtomicBoolean electionStarted, a PreVoteRequest preVoteRequest, a ClusterState clusterState and an AtomicBoolean isClosed. The local node is not a field. It is read as clusterState.nodes().getLocalNode() (PVC:244 and 260). The request (with its term, PVC:112 and 184) is not represented. Java's request source is transportService.getLocalNode() (PVC:184), a different expression from the quorum's local node. This model has no request inside the round at all.

Declaration 7: PreVotingRound.start

start(s,n)=⟨s, n, [ ], false, false⟩.\mathrm{start}(s, n) = \langle s,\ n,\ [\,],\ \mathrm{false},\ \mathrm{false}\rangle.start(s,n)=⟨s, n, [], false, false⟩.

The round has cluster state sss, local node nnn, no pre-votes, no election started, and is not closed. No relation between sss and nnn is required.

Source check: PreVoteCollector.start (PVC:111–115) builds a PreVotingRound(clusterState, state.v2().getCurrentTerm()) and broadcasts requests. The broadcast is not modelled. The Coordinator passes the last accepted state (CO:1608) and the discovered nodes, which include the local node (CO:1312–1317). This confirms the module docstring's "including itself".

Declaration 8: PreVotingRound.votes

votes(r)=foldr((p,v)↦addVote(v,p.1).1, empty, r.preVotesReceived).\mathrm{votes}(r) = \mathrm{foldr}\big((p, v) \mapsto \mathrm{addVote}(v, p.1).1,\ \mathrm{empty},\ r.\mathrm{preVotesReceived}\big).votes(r)=foldr((p,v)↦addVote(v,p.1).1, empty, r.preVotesReceived).

The entries are processed from the end of the list (the oldest) to the front (the most recent). Each sender's id is added if the sender is cluster-manager-eligible and the id is not yet present. The result is a duplicate-free list: the ids of the eligible senders. The responses in the entries are ignored completely.

Examples:

  • Entries from ⟨5,true⟩\langle 5,\mathrm{true}\rangle⟨5,true⟩ and ⟨5,false⟩\langle 5,\mathrm{false}\rangle⟨5,false⟩ give the single vote 555.
  • An entry from ⟨5,false⟩\langle 5,\mathrm{false}\rangle⟨5,false⟩ alone gives no vote.

I checked both by evaluation.

Source check: PVC:242–257 builds a fresh VoteCollection and calls addJoinVote(new Join(node, localNode, …)) for every map entry. addJoinVote (CoordinationState.java:759–765) calls addVote(join.getSourceNode()). addVote (CoordinationState.java:755–757) is isClusterManagerNode() && nodes.put(id, node) == null, keyed by node id. Matches in which ids are counted. Java also records the joins, with the response's term, accepted term and version, which a plugin strategy could read. Here they are dropped.

Declaration 9: isElectionQuorumFor

For a strategy eseses, a node nnn, naturals ttt and aaa, an integer www, configurations CcC_cCc​ and CaC_aCa​, and a vote collection vvv:

isElectionQuorumFor(es,n,t,a,w,Cc,Ca,v)=isQuorum(v,Cc)∧isQuorum(v,Ca)∧extraes(n,t,a,w,Cc,Ca,v).\mathrm{isElectionQuorumFor}(es, n, t, a, w, C_c, C_a, v) = \mathrm{isQuorum}(v, C_c) \wedge \mathrm{isQuorum}(v, C_a) \wedge \mathrm{extra}_{es}(n, t, a, w, C_c, C_a, v).isElectionQuorumFor(es,n,t,a,w,Cc​,Ca​,v)=isQuorum(v,Cc​)∧isQuorum(v,Ca​)∧extraes​(n,t,a,w,Cc​,Ca​,v).

Source check: ElectionStrategy.java:68–88 has the final method isElectionQuorum, which is exactly joinVotes.isQuorum(lastCommitted) && joinVotes.isQuorum(lastAccepted) && satisfiesAdditionalQuorumConstraints(…all seven arguments…). Matches.

Declaration 10: PreVotingRound.handlePreVoteResponse

It takes eseses, a "local response" lrlrlr, a round rrr, a response resprespresp and a sender. It returns a triple: (new round, start flag, max-term argument), where the last component is "none" or "some ttt". Write s=r.clusterStates = r.\mathrm{clusterState}s=r.clusterState. The cases, in order:

  1. Closed. If r.isClosedr.\mathrm{isClosed}r.isClosed: the result is (r,false,none)(r, \mathrm{false}, \text{none})(r,false,none).
  2. Fresher. If resp.lastAcceptedTerm>s.termresp.\mathrm{lastAcceptedTerm} > s.\mathrm{term}resp.lastAcceptedTerm>s.term, or resp.lastAcceptedTerm=s.termresp.\mathrm{lastAcceptedTerm} = s.\mathrm{term}resp.lastAcceptedTerm=s.term and resp.lastAcceptedVersion>vomv(s)resp.\mathrm{lastAcceptedVersion} > \mathrm{vomv}(s)resp.lastAcceptedVersion>vomv(s): the result is (r,false,some resp.currentTerm)(r, \mathrm{false}, \text{some } resp.\mathrm{currentTerm})(r,false,some resp.currentTerm). The response is dropped.
  3. Otherwise. Let r1r_1r1​ be rrr with
preVotesReceived:=(sender,resp)::[ p∈r.preVotesReceived∣p.1≠sender ].\mathrm{preVotesReceived} := (\mathit{sender}, resp) :: [\,p \in r.\mathrm{preVotesReceived} \mid p.1 \neq \mathit{sender}\,].preVotesReceived:=(sender,resp)::[p∈r.preVotesReceived∣p.1=sender].

Any earlier entry from a sender equal to this one (same id and same flag) is removed, and the new entry is put in front. Let

Q=isElectionQuorumFor(es, r.localNode, lr.currentTerm, lr.lastAcceptedTerm, lr.lastAcceptedVersion, s.committed, s.accepted, votes(r1)).Q = \mathrm{isElectionQuorumFor}(es,\ r.\mathrm{localNode},\ lr.\mathrm{currentTerm},\ lr.\mathrm{lastAcceptedTerm},\ lr.\mathrm{lastAcceptedVersion},\ s.\mathrm{committed},\ s.\mathrm{accepted},\ \mathrm{votes}(r_1)).Q=isElectionQuorumFor(es, r.localNode, lr.currentTerm, lr.lastAcceptedTerm, lr.lastAcceptedVersion, s.committed, s.accepted, votes(r1​)).
  • (a) If QQQ is false: (r1,false,some resp.currentTerm)(r_1, \mathrm{false}, \text{some } resp.\mathrm{currentTerm})(r1​,false,some resp.currentTerm).
  • (b) Else if r1.electionStartedr_1.\mathrm{electionStarted}r1​.electionStarted (which equals r.electionStartedr.\mathrm{electionStarted}r.electionStarted): (r1,false,some resp.currentTerm)(r_1, \mathrm{false}, \text{some } resp.\mathrm{currentTerm})(r1​,false,some resp.currentTerm).
  • (c) Else: (r1 with electionStarted:=true, true, some resp.currentTerm)(r_1 \text{ with } \mathrm{electionStarted} := \mathrm{true},\ \mathrm{true},\ \text{some } resp.\mathrm{currentTerm})(r1​ with electionStarted:=true, true, some resp.currentTerm).

Consequences that can be read off:

  • The start flag is true only in case 3(c).
  • The third component is "none" exactly in the closed case.
  • The round's cluster state, local node and closed flag never change.
  • The entry is stored even when the sender is not cluster-manager-eligible. Such a sender then contributes no vote.
  • lrlrlr enters only as the strategy's term and version arguments, so under the default strategy it is irrelevant.

I checked by evaluation that a fresher response leaves the list unchanged and still reports its current term, and that a closed round reports "none".

Source check: PVC:225–279 does the following in order:

  • returns if closed (PVC:226–229);
  • calls updateMaxTermSeen.accept(response.getCurrentTerm()) (PVC:231);
  • returns on the fresher test (PVC:233–238);
  • calls preVotesReceived.put(sender, response) (PVC:240);
  • rebuilds the votes;
  • tests electionStrategy.isElectionQuorum(localNode, localPreVoteResponse.getCurrentTerm(), …getLastAcceptedTerm(), …getLastAcceptedVersion(), lastCommitted, lastAccepted, voteCollection), where localPreVoteResponse = getPreVoteResponse() is the collector's current state (PVC:245);
  • does electionStarted.compareAndSet(false, true) and calls startElection.run().

Matches, including that the max-term argument is reported in the fresher case. Java's map put replaces by ephemeral-id equality. The filter here removes by (id, role) equality, as the module docstring says.

Declaration 11: PreVotingRound.close

close(r)\mathrm{close}(r)close(r) is rrr with isClosed:=true\mathrm{isClosed} := \mathrm{true}isClosed:=true. It is idempotent here.

Source check: PVC:296–299 does isClosed.compareAndSet(false, true) and asserts that it was not already closed. The assertion is not modelled.

Declaration 12: NoFresher

For a response resprespresp and a cluster state sss, NoFresher(resp,s)\mathrm{NoFresher}(resp, s)NoFresher(resp,s) is the proposition

resp.lastAcceptedTerm<s.term  ∨  (resp.lastAcceptedTerm=s.term∧resp.lastAcceptedVersion≤vomv(s)).resp.\mathrm{lastAcceptedTerm} < s.\mathrm{term} \;\vee\; \big(resp.\mathrm{lastAcceptedTerm} = s.\mathrm{term} \wedge resp.\mathrm{lastAcceptedVersion} \le \mathrm{vomv}(s)\big).resp.lastAcceptedTerm<s.term∨(resp.lastAcceptedTerm=s.term∧resp.lastAcceptedVersion≤vomv(s)).

This is lexicographic ≤\le≤ of (term,version)(\text{term}, \text{version})(term,version) against (s.term,vomv(s))(s.\mathrm{term}, \mathrm{vomv}(s))(s.term,vomv(s)). It is exactly the negation of the "fresher" guard of Declaration 10, case 2.

Source check: the docstring cites PVC:232–238. The test is at PVC:233–238 (232 is blank). Matches.

Declaration 13: RoundReachable

Fix a strategy eseses and an arbitrary predicate Delivered(sender,resp)\mathit{Delivered}(\mathit{sender}, resp)Delivered(sender,resp) on (discovery node, response) pairs. RoundReachablees,Delivered\mathrm{RoundReachable}_{es,\mathit{Delivered}}RoundReachablees,Delivered​ is the least predicate on rounds that is closed under three rules:

  • start: for every cluster state sss and node nnn, start(s,n)\mathrm{start}(s, n)start(s,n) is reachable;
  • handle: if rrr is reachable and Delivered(sender,resp)\mathit{Delivered}(\mathit{sender}, resp)Delivered(sender,resp) holds, then for every lrlrlr, the first component of handlePreVoteResponse(es,lr,r,resp,sender)\mathrm{handlePreVoteResponse}(es, lr, r, resp, \mathit{sender})handlePreVoteResponse(es,lr,r,resp,sender) is reachable;
  • close: if rrr is reachable, so is close(r)\mathrm{close}(r)close(r).

Consequences of this definition:

  • Delivered\mathit{Delivered}Delivered is one fixed predicate for the whole run. It does not depend on time or on the round.
  • The local response lrlrlr is chosen freely at each step.
  • A sender can deliver any number of times, with different responses each time. Senders need not be among any requested nodes.
  • Handle and close steps interleave freely. A handle step after close is a no-op, and close can be repeated.
  • The start state sss and the local node nnn are arbitrary and unrelated to each other.
  • Along any derivation the round's cluster state and local node stay those given at start.

The docstring says "started over its accepted state". Nothing in the term makes sss anyone's accepted state.

Declaration 14: handleJoins

handleJoins(es,cs,js)=foldl(λ cs j. if handleJoin(es,cs,j)=success(cs′,_) then cs′ else cs,  cs, js).\mathrm{handleJoins}(es, cs, js) = \mathrm{foldl}\big(\lambda\, cs\, j.\ \text{if } \mathrm{handleJoin}(es, cs, j) = \text{success}(cs', \_) \text{ then } cs' \text{ else } cs,\ \ cs,\ js\big).handleJoins(es,cs,js)=foldl(λcsj. if handleJoin(es,cs,j)=success(cs′,_) then cs′ else cs,  cs, js).

The joins are applied from left to right, each to the state the previous one produced. A rejected join leaves the state unchanged, and the "added" Boolean is discarded. A join whose term is above the current term is simply rejected by guard 1 of handleJoin. Nothing moves the state to that term. Nothing checks the joins' target node.

Source check: Coordinator.handleJoin (CO:1267–1287) first calls ensureTermAtLeast(…, join.getTerm()), which only matters for a higher term (CO:1269). It then calls CoordinationState.handleJoin either through handleJoinIgnoringExceptions (CO:1292–1299) when the election is already won, or directly. In CoordinationState.handleJoin (CoordinationState.java:264–339) every rejection throws before the first mutation (the throws are at lines 269–317; the vote is added at line 320). So "a rejected join leaves the state unchanged" is correct. Java asserts join.targetMatches(localNode) (line 265); that assertion is not modelled. The docstring restricts the claim to joins whose term is not above the current term. The definition itself imposes no such restriction.

Declaration 15: startElectionTerm

startElectionTerm(tc,tm)=max⁡(tc,tm)+1.\mathrm{startElectionTerm}(t_c, t_m) = \max(t_c, t_m) + 1.startElectionTerm(tc​,tm​)=max(tc​,tm​)+1.

Source check: CO:593 builds new StartJoinRequest(getLocalNode(), Math.max(getCurrentTerm(), maxTermSeen) + 1). Matches. Java's guards (mode == CANDIDATE and localNodeMayWinElection, CO:587–591) and the sending to discovered non-Zen1 nodes (CO:595–599) are not part of this definition.

Declaration 16: nodeMayWinElection

For a cluster state sss, a list of node ids excluded\mathit{excluded}excluded and a node id nnn:

nodeMayWinElection(s,excluded,n)=(n∈s.committed.ids)∨(n∈s.accepted.ids)∨(n∉excluded).\mathrm{nodeMayWinElection}(s, \mathit{excluded}, n) = (n \in s.\mathrm{committed}.\mathrm{ids}) \vee (n \in s.\mathrm{accepted}.\mathrm{ids}) \vee (n \notin \mathit{excluded}).nodeMayWinElection(s,excluded,n)=(n∈s.committed.ids)∨(n∈s.accepted.ids)∨(n∈/excluded).

The exclusions are a separate argument, unrelated to sss. No theorem of this mission uses this definition.

Source check: CO:628–633 matches, with getVotingConfigExclusions().stream().noneMatch(…) as n∉excludedn \notin \mathit{excluded}n∈/excluded.

Declaration 17: SchedulerSettings

This is a structure with four natural-number fields: initialTimeout\mathrm{initialTimeout}initialTimeout, backoffTime\mathrm{backoffTime}backoffTime, maxTimeout\mathrm{maxTimeout}maxTimeout and duration\mathrm{duration}duration. The docstring says they are milliseconds. The type carries no unit and no bounds.

Source check: the setting keys (ESF:66–69) are cluster.election.initial_timeout, back_off_time, max_timeout and duration. Their defaults and bounds (ESF:85–115) are:

SettingDefaultRange
initial_timeout100 ms1 ms – 10 s
back_off_time100 ms1 ms – 60 s
max_timeout10 s200 ms – 300 s
duration500 ms1 ms – 300 s

These match the docstring. Java reads them as TimeValue.millis().

Declaration 18: SchedulerSettings.Valid

Valid(s)\mathrm{Valid}(s)Valid(s) is the conjunction:

  • 1≤initialTimeout≤100001 \le \mathrm{initialTimeout} \le 100001≤initialTimeout≤10000;
  • 1≤backoffTime≤600001 \le \mathrm{backoffTime} \le 600001≤backoffTime≤60000;
  • 200≤maxTimeout≤300000200 \le \mathrm{maxTimeout} \le 300000200≤maxTimeout≤300000;
  • initialTimeout≤maxTimeout\mathrm{initialTimeout} \le \mathrm{maxTimeout}initialTimeout≤maxTimeout;
  • 1≤duration≤3000001 \le \mathrm{duration} \le 3000001≤duration≤300000.

Source check: these are the setting bounds above, plus the constructor check at ESF:133–143 (it throws if maxTimeout.millis() < initialTimeout.millis()). Matches. Setting.java is not in the local checkout, so I could not see how the bounds are checked for sub-millisecond TimeValues.

Declaration 19: SchedulerSettings.default

⟨100,100,10000,500⟩\langle 100, 100, 10000, 500\rangle⟨100,100,10000,500⟩, that is: initialTimeout 100100100, backoffTime 100100100, maxTimeout 100001000010000, duration 500500500. These match the Java defaults, and the value satisfies Valid\mathrm{Valid}Valid. No theorem of this mission uses it.

Declaration 20: maxDelay

maxDelay(s,k)=min⁡(s.maxTimeout, s.initialTimeout+k⋅s.backoffTime),\mathrm{maxDelay}(s, k) = \min\big(s.\mathrm{maxTimeout},\ s.\mathrm{initialTimeout} + k \cdot s.\mathrm{backoffTime}\big),maxDelay(s,k)=min(s.maxTimeout, s.initialTimeout+k⋅s.backoffTime),

in unbounded natural-number arithmetic, so there is no overflow. With the defaults it is 100+100k100 + 100k100+100k up to k=99k = 99k=99, where it first reaches 100001000010000; I checked this by evaluation. Without Valid\mathrm{Valid}Valid it can be 000, for example with initialTimeout 000 and backoffTime 000.

Source check: ESF:203 is Math.min(maxTimeout.millis(), initialTimeout.millis() + thisAttempt * backoffTime.millis()), where thisAttempt counts from 000 (ESF:201). Matches. The Java comment there notes that overflow would take "over a million years".

Declaration 21: nonNegative

For any integer nnn:

nonNegative(n)={0if n=−263,∣n∣otherwise.\mathrm{nonNegative}(n) = \begin{cases} 0 & \text{if } n = -2^{63},\\ |n| & \text{otherwise.}\end{cases}nonNegative(n)={0∣n∣​if n=−263,otherwise.​

-2 ^ 63 parses as −(263)=−9223372036854775808-(2^{63}) = -9223372036854775808−(263)=−9223372036854775808, which is Long.MIN_VALUE. I confirmed the parse with pp.parens; since 636363 is odd, (−2)63(-2)^{63}(−2)63 would give the same value anyway.

The domain is all of Z\mathbb{Z}Z, not only Java's long range. Outside [−263,263)[-2^{63}, 2^{63})[−263,263) the function returns ∣n∣|n|∣n∣, for example nonNegative(−263−1)=263+1\mathrm{nonNegative}(-2^{63}-1) = 2^{63}+1nonNegative(−263−1)=263+1. No Java long gives such a value. The docstring states the long range, but the definition does not restrict to it.

Source check: ESF:159–161 is n == Long.MIN_VALUE ? 0 : Math.abs(n). Matches on longs.

Declaration 22: toPositiveLongAtMost

For an integer xxx and u∈Nu \in \mathbb{N}u∈N:

toPositiveLongAtMost(x,u)=(nonNegative(x) mod u)+1,\mathrm{toPositiveLongAtMost}(x, u) = \big(\mathrm{nonNegative}(x) \bmod u\big) + 1,toPositiveLongAtMost(x,u)=(nonNegative(x)modu)+1,

with natural-number  mod \bmodmod.

  • For u≥1u \ge 1u≥1 the result is in [1,u][1, u][1,u].
  • For u=0u = 0u=0, Lean's  mod 0\bmod 0mod0 returns the dividend, so the result is nonNegative(x)+1\mathrm{nonNegative}(x) + 1nonNegative(x)+1. Java asserts 0 < upperBound, and Java's % by zero would throw. The definition leaves this case defined but meaningless.

Source check: ESF:169–172. Matches for u>0u > 0u>0.

Declaration 23: attemptDelay

For settings sss, an attempt index kkk, an integer xxx (the random long) and a grace period g∈Ng \in \mathbb{N}g∈N:

attemptDelay(s,k,x,g)=toPositiveLongAtMost(x,maxDelay(s,k))+g.\mathrm{attemptDelay}(s, k, x, g) = \mathrm{toPositiveLongAtMost}\big(x, \mathrm{maxDelay}(s, k)\big) + g.attemptDelay(s,k,x,g)=toPositiveLongAtMost(x,maxDelay(s,k))+g.

The docstring says ggg is 000 for the first attempt and s.durations.\mathrm{duration}s.duration for later ones. The definition takes ggg as a free argument, and nothing ties it to 000 or to s.durations.\mathrm{duration}s.duration. In fact s.durations.\mathrm{duration}s.duration is read by no definition of the file except Valid\mathrm{Valid}Valid.

Source check: ESF:195–204 computes delayMillis = toPositiveLongAtMost(random.nextLong(), maxDelayMillis) + gracePeriod.millis(). Later attempts are rescheduled with scheduleNextElection(duration, …) (ESF:218). The first grace period is TimeValue.ZERO (CO:1574). Matches.


Remarks on the docstrings

  • Module docstring, "Both handlers first raise the Coordinator's maxTermSeen." handlePreVoteResponse tests the closed flag first and raises the term only if the round is open. Its own docstring and code say so correctly; the module sentence is loose.
  • Module docstring, "the leader moves to that term and starts an election itself (CO:565-577)." In Java this happens only when no publication is in progress; otherwise the term bump is deferred (CO:567–568). If the bump fails, the node becomes a candidate (CO:574–576). The docstring places this effect outside the functions, and no definition models it.
  • Module docstring on node equality. It says the Lean and Java comparisons "agree except between two incarnations of the same node". Two incarnations with different roles are distinct under both comparisons. The real disagreement is between two incarnations with the same id and role.
  • PreVotingRound, "at most one entry per sender." This is not a type invariant (see Declaration 6). "Sender" here means a discovery-node value, that is, an (id, role) pair, so two entries may share an id. I checked by evaluation: senders ⟨5,true⟩\langle 5,\mathrm{true}\rangle⟨5,true⟩ and ⟨5,false⟩\langle 5,\mathrm{false}\rangle⟨5,false⟩ both stay in the list.
  • RoundReachable, "started over its accepted state." The start rule accepts any cluster state.
  • nonNegative, "on a Java long." The definition is total on Z\mathbb{Z}Z.
  • attemptDelay, the grace-period description. This describes how Java calls the function. The grace period is a free parameter here.
  • Unused declarations. No theorem of this mission uses nodeMayWinElection or SchedulerSettings.default.
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