Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

OpenSearch coordination as a message-passing system: every node runs CoordinationState, messages may be lost, duplicated or reordered, nodes restart; the safety vocabulary and the inductive invariant

Definition
OpenSearchSafety

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

cluster-coordinationconsensuscrash-recoveryelasticsearchformal-verificationinductive-invariantleader-electionmessage-passingopensearchpaxosraftreconfigurationsafetyzen2

A model of an OpenSearch cluster at revision b2a54ba5c0defba3d1d20423e911d4bf920bab19 in which every node runs the CoordinationState of the OpenSearchCoordination mission (its NodeId, DiscoveryNode, VotingConfiguration, ClusterState, message types, ElectionStrategy, CoordinationState, handlers and contracts are used as they are), the notions in which the safety theorems are stated, and the inductive invariant Inv from which they are proved. CO is Coordinator.java, CBS is ClusterBootstrapService.java.

Messages. Message V — join j, a Join; publishRequest source state parentTerm parentVersion, a PublishRequest of state from source, together with ghost data that the real message does not carry: the term and version of the state the publisher had accepted when it published, the publication's parent; publishResponse source dest resp, a PublishResponse from source to dest; applyCommit c, an ApplyCommitRequest.

Parameters. Params — eligible n, whether node n has the cluster-manager role (DiscoveryNode.isClusterManagerNode(), fixed); initConfs, the configurations a node may bootstrap with (a predicate on configurations); strategy, the election strategy of every node. P.dn n — the DiscoveryNode ⟨n, P.eligible n⟩. P.InitCompatible — for all configurations X, Y with P.initConfs X and P.initConfs Y and all lists q₁, q₂ of eligible node ids with X.hasQuorum q₁ and Y.hasQuorum q₂, some node id is in both lists. BootstrapConfig k resolve placeholder matched X — X has the form of a configuration that ClusterBootstrapService bootstraps with (CBS:176-215, 259-273, 306-335): the k bootstrap requirements (cluster.initial_cluster_manager_nodes) are numbered 0 … k-1; the members of X are exactly, for i < k, resolve i if matched i (the node has discovered the node requirement i names) and the placeholder id placeholder i otherwise ("{bootstrap-placeholder}-" + requirement); and more than half of the k requirements are matched. The predicate does not require resolve or placeholder to be injective or their values to be distinct (bootstrap_compatible assumes this; in Java the requirements have no duplicates and checkRequirements matches each requirement and each discovered node at most once, CBS:150-155, 306-335), nor the bootstrapping node to be eligible and matched (Java requires both, CBS:179, 202-209); no other definition refers to it (the bootstrap step uses P.initConfs).

Clusters. Cluster V — node : NodeId → CoordinationState V, the state of every node, and sent : Message V → Prop, the messages sent so far. W.set n cs replaces node n's state by cs; W.send m adds m to the sent messages. Initial P W — every node n is CoordinationState.init (P.dn n) 0 s for some cluster state s of term 0 whose last committed and last accepted configurations are empty (its other fields, version and metadata version included, are arbitrary), and no message has been sent. RestartState s s' — the accepted state s' a restarting cluster-manager-eligible node comes back with, given the accepted state s it had: s' has the term, the version, the two configurations and the two cluster-UUID flags of s (its metadata version, cluster-manager node and payload may differ: Java rebuilds the cluster-manager node and the parts of the state outside the persisted metadata, and leaving the persisted metadata, metadata version included, free only adds behaviours); or s has term 0, empty configurations and an unknown cluster UUID, and s' has term 0 and empty configurations (a node that never joined a cluster, restoring a state from the remote store).

Steps. Step P W W' — one successful handler call at a node n, its output, if any, being added to the sent messages:

  • bootstrap: (W.node n).setInitialState s = .ok cs' for a state s whose two configurations are some X with P.initConfs X, with initialStateContract (the method's asserted preconditions); W' = W.set n cs';
  • startJoin: handleStartJoin ⟨P.dn src, t⟩ = .ok (cs', j) for any eligible src and any term t; W' = (W.set n cs').send (.join j);
  • join: handleJoin P.strategy j = .ok (cs', b) for a sent join j with j.targetNode.id = n; W' = W.set n cs';
  • clientValue: handleClientValue s = .ok (cs', p) with clientValueContract (the asserted precondition: s carries n's last committed configuration); sends publishRequest n p.acceptedState lt lv, where (lt, lv) are n's last accepted term and version before the call;
  • publish: handlePublishRequest ⟨s⟩ = .ok (cs', r) for a sent publishRequest src s pt pv; sends publishResponse n src r;
  • respond: handlePublishResponse (P.dn src) r = .ok (cs', o) for a sent publishResponse src n r; sends applyCommit c if o = some c;
  • commit: handleCommit c = .ok cs' for a sent applyCommit c;
  • restart: for an eligible n, the state becomes CoordinationState.init (W.node n).localNode (W.node n).currentTerm s' for a state s' with RestartState (W.node n).lastAcceptedState s';
  • restartAny: for a node n that is not eligible, the state becomes CoordinationState.init (W.node n).localNode t s' for any term t and any state s'.

Reachable P W — W is initial, or is reached from a reachable cluster by a step.

Safety vocabulary. A publication is named by its key, its (term, version). Committed W t v — some applyCommit ⟨src, t, v⟩ has been sent. Parent W t v t' v' — some publishRequest src s t v with s.term = t' and s.version = v' has been sent. Descends W t v t' v' — the reflexive-transitive closure of Parent: (t', v') descends from (t, v).

Proof-side notions (used by Inv, the lemmas and their proofs only; Published appears only in the proofs). KeyLE t v t' v' — t < t' ∨ (t = t' ∧ v ≤ v'). Below lt lv bt bv — lt < bt ∨ (lt = bt ∧ (bt = 0 ∨ lv ≤ bv)): handleJoin's freshness comparison, ignoring the version at term 0, where joins carry metadata versions. Published W t v — some publication of term t and version v has been sent. Realizes P W t v x y — the pair (last committed, last accepted) (x, y) realizes the key (t, v): t = 0, x = y and P.initConfs x (a bootstrap state); or some sent publication of term t and version v has last accepted configuration y, and last committed configuration x, or last accepted configuration x with (t, v) committed. JoinVoters P W L t J — every member of J is eligible and sent node L a join of term t. BaseVoters P W L t bt bv J — every member of J is eligible and sent L a join of term t whose last accepted term and version are Below bt bv. RespVoters P W t v A — every member of A is eligible and sent a PublishResponse for (t, v) to some node. ElectionRecord P W L t bt bv x y J — bt < t, Realizes P W bt bv x y, BaseVoters P W L t bt bv J, x.hasQuorum J and y.hasQuorum J: an election of L in term t over the base (bt, bv). Won P W b t — b is eligible, and either (W.node b).electionWon = true with current term t, or b has sent a publication of term t.

Inv P W — the inductive invariant, 30 facts (field names in parentheses).

  • Every node n: its local node is P.dn n (localNode_eq); if it has not won, its last published version is 0 and its publish votes are empty (idle_of_not_won); if it has won, and if it holds join votes, it has handled a start-join since its last restart (won_started, votes_started); if it has handled one, its current term is at least 1 (started_term_pos); its join votes are a quorum of both its last committed and its last accepted configuration if it has won (won_quorum) and not if it has not (not_won_no_quorum); every join vote it holds is of an eligible node that sent it a join for its current term with a last accepted term and version Below its own (joinVotes_sent); every publish vote it holds is of an eligible node that sent it a PublishResponse for its current term and last published version (publishVotes_sent).
  • Every eligible node: its last accepted term is at most its current term (term_le); its accepted state has term 0 and empty configurations, or its two configurations realize its last accepted term and version (accepted_realizes).
  • Joins and responses: every join is from the DiscoveryNode of its source and addressed to an eligible node (join_wf); the joins of an eligible node have terms at most its current term (join_term_le), at most one per term (join_unique), and a join of an eligible node for a term later than one of its publish responses carries a last accepted (term, version) at least the response's (join_after_response); the publish responses of an eligible node have terms at most its current term and keys at most its last accepted key (response_le); every publish response answers a publication of its key sent by the node it is addressed to (response_published).
  • Publications: every publication is sent by an eligible node, has term ≥ 1, a parent of term at most its term and of smaller version, and, if the parent has term 0, a bootstrap configuration as last committed configuration (pub_wf); a parent of term ≥ 1 is the key of a sent publication, the last committed configuration is that publication's last committed one, or its last accepted one if the parent is committed, and the last accepted configuration differs from that publication's only if the last committed configuration is that publication's last accepted one (pub_parent); two publications with the same key are the same message (pub_unique); every publication descends from a key of term 0 (pub_rooted); two publications of the same term are related by descent (pub_same_term); the eligible nodes that sent the publisher a join for the publication's term include a quorum of both its configurations (pub_voters); a publication whose parent is of an older term carries an election record of its publisher for its term, over the parent, with its last committed configuration as x (pub_election).
  • Commits: every commit is of a sent publication whose publish responses from eligible nodes include a quorum A of its last accepted configuration such that A is also a quorum of its last committed configuration, or the publication's parent is committed and is a sent publication with the same last accepted configuration (commit_quorum).
  • Leaders: for each term t, at most one node b has Won P W b t (won_unique); a node that published in a term is past that term, or still in it and either elected or without a start-join handled since its last restart (pub_source_term); every publication of an elected node's current term has a version at most the node's last published version, descends to (current term, last published version), and has both configurations with a quorum in the node's join votes (leader_pubs); an elected node whose last published version differs from its last accepted version sent a publication of key (current term, last published version) with its accepted key as parent, its last published configuration is that publication's last accepted configuration, and its last committed configuration is that publication's last committed one, or that publication's last accepted one with its accepted key committed and its last accepted configuration equal to that publication's (leader_inflight); an elected node whose last published version equals its last accepted version has its last accepted term equal to its current term and its last published configuration equal to its last accepted one, or an older last accepted term while no publication of its current term has been sent (leader_settled).

Formalization Note. Messages are never removed: a step may handle any sent message any number of times, in any order, or never, which models loss, duplication, delay and reordering. A join is handled only by its target and a publish response only by its addressee; publish requests and commits may be handled by any node. Start-join requests are not messages: any node may handle a request from any eligible node for any term at any time, which covers the Coordinator's elections, abdication and ensureTermAtLeast (CO:583-657) and over-approximates them; the Coordinator's other guards only reject more calls. The asserted preconditions of setInitialState and handleClientValue are imposed at the bootstrap and clientValue steps. The ghost parent of a publication is not read by any handler. A cluster-manager-eligible node persists its current term and accepted state synchronously; a restart keeps its current term and either keeps its accepted state except for the metadata version, the cluster-manager node and the payload, which it leaves free, or, if the node never joined a cluster (term 0, empty configurations, unknown cluster UUID), replaces it by a term-0 state with empty configurations, as restored from the remote store (RestartState); a node that is not cluster-manager-eligible may come back with any term and state. Outside the model (assumptions): a node's cluster-manager role never changes; persisted state is never rolled back; the offline opensearch-node tools are not used; bootstrap requirements name the same node at every node; every node uses the same election strategy; a publication delivered through the remote cluster-state store reconstructs exactly the published state. The per-node abstractions of OpenSearchCoordination apply (terms are naturals, versions integers without overflow, the remote persisted state omitted). The safety theorems assume P.InitCompatible and P.strategy = ElectionStrategy.DEFAULT_INSTANCE. The file imports only the OpenSearchCoordination definitions (Lean core).

Definition code
import Definitions.Def_OpenSearchCoordination

/-!
# OpenSearch cluster coordination: the cluster

Every node runs the `CoordinationState` of `Def_OpenSearchCoordination` (OpenSearch
`b2a54ba5c0defba3d1d20423e911d4bf920bab19`). Nodes exchange messages through a network that may lose, duplicate, delay
and reorder them: a message, once sent, stays available forever and may be handled any number of times, by any node it
is addressed to, or never. Nodes may crash and restart at any time.

Each step is a successful call of one `CoordinationState` method, its output, if any, being sent. The steps cover every
call the `Coordinator` makes (`Coordinator.java`, cited `CO:<line>`; the `Coordinator`'s own guards only reject more):
* `bootstrap`: `setInitialState` with a bootstrap configuration (`ClusterBootstrapService`, CO:1101-1161), under the
  method's asserted preconditions; nodes may bootstrap with different configurations (`BootstrapConfig` describes
  `ClusterBootstrapService`'s configurations; the model does not refer to it);
* `startJoin`: `handleStartJoin` for a request from any cluster-manager-eligible node in any term (elections, abdication,
  and `ensureTermAtLeast` on receiving a message of a higher term, which joins that message's sender); the `Join` is
  sent to the requester;
* `join`: `handleJoin` of a sent `Join` addressed to the node;
* `clientValue`: `handleClientValue` of any cluster state satisfying the asserted precondition; the `PublishRequest` is
  sent to every node;
* `publish`: `handlePublishRequest` of a sent `PublishRequest`; the `PublishResponse` goes back to the publisher;
* `respond`: `handlePublishResponse` of a sent `PublishResponse` addressed to the node; a resulting `ApplyCommitRequest`
  is sent to every node;
* `commit`: `handleCommit` of a sent `ApplyCommitRequest`;
* `restart`: a new `CoordinationState` over the persisted state. A cluster-manager-eligible node persists its current
  term and accepted state synchronously (`GatewayMetaState.LucenePersistedState`) and rebuilds on startup the parts of
  the accepted state that are not persisted (the node list, routing table, transient settings;
  GatewayMetaState.java:164-197); the model leaves the metadata version, the cluster-manager node and the payload free,
  which only adds behaviours. A node that never joined a cluster (term 0, empty configurations, unknown cluster UUID)
  may instead come back with a term-0 state with empty configurations, as restored from the remote store
  (GatewayMetaState.java:169-188). A node that is not cluster-manager-eligible persists asynchronously or not at all,
  and may come back with any persisted state.

A `PublishRequest` records, as ghost data that the real message does not carry, the term and version of the state its
publisher had accepted when it published (its parent); this defines descent between published states.

OpenSearch's randomized safety test `CoordinationStateTestCluster` (`test/framework/.../coordination/`) runs random
executions of a similar model (messages are never removed, start-join requests carry arbitrary terms, any elected node
publishes arbitrary values and configurations, and nodes reboot) and checks the assertions of `invariant()` at every
node and, at the end, one cluster-manager per term and one cluster state per (term, version).

Assumptions (outside the model): the cluster-manager role of a node never changes (changing it and back can reset the
persisted term, GatewayMetaState.java:232-255); no disk rollback; no offline tools (`opensearch-node` unsafe-bootstrap,
detach-cluster, remove-settings, remove-customs); bootstrap requirements name the same node at every node; one election
strategy for all nodes; a publication delivered through the remote store reconstructs exactly the published state.
-/

namespace OpenSearchSafety

open OpenSearchCoordination

/-- Messages. -/
inductive Message (V : Type) where
  | join (j : Join)
  /-- A `PublishRequest` from `source`, with the ghost parent (term, version). -/
  | publishRequest (source : NodeId) (state : ClusterState V) (parentTerm : Nat) (parentVersion : Int)
  /-- A `PublishResponse` from `source` to `dest`. -/
  | publishResponse (source dest : NodeId) (resp : PublishResponse)
  | applyCommit (c : ApplyCommitRequest)

/-- The fixed parameters of a cluster. -/
structure Params where
  /-- `DiscoveryNode.isClusterManagerNode()` of each node. -/
  eligible : NodeId → Bool
  /-- The configurations a node may bootstrap with. -/
  initConfs : VotingConfiguration → Prop
  /-- The election strategy of every node. -/
  strategy : ElectionStrategy

/-- The `DiscoveryNode` of node `n`. -/
def Params.dn (P : Params) (n : NodeId) : DiscoveryNode := ⟨n, P.eligible n⟩

/-- The bootstrap configurations are compatible: votes of cluster-manager-eligible nodes that form a quorum of one
bootstrap configuration share a voter with votes that form a quorum of another. -/
def Params.InitCompatible (P : Params) : Prop :=
  ∀ X Y, P.initConfs X → P.initConfs Y → ∀ q₁ q₂ : List NodeId,
    (∀ x ∈ q₁, P.eligible x = true) → (∀ x ∈ q₂, P.eligible x = true) →
    X.hasQuorum q₁ = true → Y.hasQuorum q₂ = true → ∃ x, x ∈ q₁ ∧ x ∈ q₂

/-- The form of the configurations `ClusterBootstrapService` bootstraps with (CBS:176-215, CBS:259-273, CBS:306-335):
the bootstrap requirements (`cluster.initial_cluster_manager_nodes`, without duplicates) are numbered `0 … k-1`;
requirement `i`, when the node has discovered the node it names, contributes that node's id `resolve i`, and otherwise a
placeholder id `placeholder i` (`"{bootstrap-placeholder}-" + requirement`); more than half of the requirements must be
matched. The predicate does not require `resolve` or `placeholder` to be injective or their values to be distinct
(`bootstrap_compatible` assumes this), nor the bootstrapping node to be eligible and matched (Java requires both,
CBS:179, 202-209). No other definition refers to it: the `bootstrap` step uses `P.initConfs`. -/
def BootstrapConfig (k : Nat) (resolve placeholder : Nat → NodeId) (matched : Nat → Bool)
    (X : VotingConfiguration) : Prop :=
  (∀ x, x ∈ X.nodeIds ↔ ∃ i, i < k ∧ x = if matched i then resolve i else placeholder i) ∧
  ((List.range k).filter matched).length * 2 > k

/-- A cluster: the coordination state of every node and the set of messages sent so far. -/
structure Cluster (V : Type) where
  node : NodeId → CoordinationState V
  sent : Message V → Prop

namespace Cluster

variable {V : Type}

/-- Replace node `n`'s state. -/
def set (W : Cluster V) (n : NodeId) (cs : CoordinationState V) : Cluster V :=
  { W with node := fun m => if m = n then cs else W.node m }

/-- Send a message. -/
def send (W : Cluster V) (m : Message V) : Cluster V := { W with sent := fun x => W.sent x ∨ x = m }

end Cluster

variable {V : Type}

/-- A fresh cluster: every node is in term 0 with an accepted term-0 state with empty configurations (its version,
metadata version, cluster-manager node, cluster-UUID flags and payload are arbitrary and may differ between nodes — a
fresh node has version 0, a node restored from the remote store or upgraded from an older version may have others),
and no message has been sent. -/
def Initial (P : Params) (W : Cluster V) : Prop :=
  (∀ n, ∃ s : ClusterState V, s.term = 0 ∧ s.lastCommittedConfiguration = VotingConfiguration.EMPTY_CONFIG ∧
      s.lastAcceptedConfiguration = VotingConfiguration.EMPTY_CONFIG ∧
      W.node n = CoordinationState.init (P.dn n) 0 s) ∧
  (∀ m, ¬ W.sent m)

/-- The accepted state a restarting cluster-manager-eligible node comes back with, given the one it had: the persisted
term, version, configurations and cluster-UUID flags, with the rest (metadata version, cluster-manager node, payload)
left free — Java rebuilds the cluster-manager node and the parts of the state outside the persisted metadata, and
leaving the persisted metadata free only adds behaviours; or, if it never joined a cluster (term 0, empty
configurations, unknown cluster UUID), a term-0 state with empty configurations, as restored from the remote store. -/
def RestartState (s s' : ClusterState V) : Prop :=
  (s'.term = s.term ∧ s'.version = s.version ∧
    s'.lastCommittedConfiguration = s.lastCommittedConfiguration ∧
    s'.lastAcceptedConfiguration = s.lastAcceptedConfiguration ∧
    s'.clusterUUIDKnown = s.clusterUUIDKnown ∧ s'.clusterUUIDCommitted = s.clusterUUIDCommitted) ∨
  (s.term = 0 ∧ s.lastCommittedConfiguration = VotingConfiguration.EMPTY_CONFIG ∧
    s.lastAcceptedConfiguration = VotingConfiguration.EMPTY_CONFIG ∧ s.clusterUUIDKnown = false ∧
    s'.term = 0 ∧ s'.lastCommittedConfiguration = VotingConfiguration.EMPTY_CONFIG ∧
    s'.lastAcceptedConfiguration = VotingConfiguration.EMPTY_CONFIG)

/-- One step of the cluster. -/
inductive Step (P : Params) : Cluster V → Cluster V → Prop where
  | bootstrap (W : Cluster V) (n : NodeId) (X : VotingConfiguration) (s : ClusterState V)
      (cs' : CoordinationState V) (hX : P.initConfs X)
      (hcontract : (W.node n).initialStateContract s)
      (hconf : s.lastCommittedConfiguration = X ∧ s.lastAcceptedConfiguration = X)
      (h : (W.node n).setInitialState s = .ok cs') :
      Step P W (W.set n cs')
  | startJoin (W : Cluster V) (n src : NodeId) (t : Nat) (cs' : CoordinationState V) (j : Join)
      (hsrc : P.eligible src = true)
      (h : (W.node n).handleStartJoin ⟨P.dn src, t⟩ = .ok (cs', j)) :
      Step P W ((W.set n cs').send (.join j))
  | join (W : Cluster V) (n : NodeId) (j : Join) (cs' : CoordinationState V) (b : Bool)
      (hsent : W.sent (.join j)) (hdest : j.targetNode.id = n)
      (h : (W.node n).handleJoin P.strategy j = .ok (cs', b)) :
      Step P W (W.set n cs')
  | clientValue (W : Cluster V) (n : NodeId) (s : ClusterState V) (cs' : CoordinationState V)
      (p : PublishRequest V) (hcontract : (W.node n).clientValueContract s)
      (h : (W.node n).handleClientValue s = .ok (cs', p)) :
      Step P W ((W.set n cs').send (.publishRequest n p.acceptedState (W.node n).lastAcceptedTerm
        (W.node n).lastAcceptedVersion))
  | publish (W : Cluster V) (n src : NodeId) (s : ClusterState V) (pt : Nat) (pv : Int)
      (cs' : CoordinationState V) (r : PublishResponse) (hsent : W.sent (.publishRequest src s pt pv))
      (h : (W.node n).handlePublishRequest ⟨s⟩ = .ok (cs', r)) :
      Step P W ((W.set n cs').send (.publishResponse n src r))
  | respond (W : Cluster V) (n src : NodeId) (r : PublishResponse) (cs' : CoordinationState V)
      (o : Option ApplyCommitRequest) (hsent : W.sent (.publishResponse src n r))
      (h : (W.node n).handlePublishResponse (P.dn src) r = .ok (cs', o)) :
      Step P W (match o with
        | none => W.set n cs'
        | some c => (W.set n cs').send (.applyCommit c))
  | commit (W : Cluster V) (n : NodeId) (c : ApplyCommitRequest) (cs' : CoordinationState V)
      (hsent : W.sent (.applyCommit c)) (h : (W.node n).handleCommit c = .ok cs') :
      Step P W (W.set n cs')
  | restart (W : Cluster V) (n : NodeId) (s' : ClusterState V) (hn : P.eligible n = true)
      (hs : RestartState (W.node n).lastAcceptedState s') :
      Step P W (W.set n (CoordinationState.init (W.node n).localNode (W.node n).currentTerm s'))
  | restartAny (W : Cluster V) (n : NodeId) (t : Nat) (s' : ClusterState V) (hn : P.eligible n = false) :
      Step P W (W.set n (CoordinationState.init (W.node n).localNode t s'))

/-- The clusters reachable from a fresh cluster. -/
inductive Reachable (P : Params) : Cluster V → Prop where
  | init (W : Cluster V) : Initial P W → Reachable P W
  | step (W W' : Cluster V) : Reachable P W → Step P W W' → Reachable P W'

/-- A (term, version) is committed when an `ApplyCommitRequest` for it has been sent (that it is then the key of a sent
publication follows from the invariant, `inv_committed_published`). -/
def Committed (W : Cluster V) (t : Nat) (v : Int) : Prop := ∃ src, W.sent (.applyCommit ⟨src, t, v⟩)

/-- `(t, v)` is the parent of `(t', v')`: a publication of `(t', v')` was made on top of an accepted `(t, v)`. -/
def Parent (W : Cluster V) (t : Nat) (v : Int) (t' : Nat) (v' : Int) : Prop :=
  ∃ src s, W.sent (.publishRequest src s t v) ∧ s.term = t' ∧ s.version = v'

/-- Descent between (term, version) pairs: the reflexive-transitive closure of `Parent` (reflexive on every pair,
published or not). -/
inductive Descends (W : Cluster V) : Nat → Int → Nat → Int → Prop where
  | refl (t : Nat) (v : Int) : Descends W t v t v
  | step (t : Nat) (v : Int) (t' : Nat) (v' : Int) (t'' : Nat) (v'' : Int) :
      Descends W t v t' v' → Parent W t' v' t'' v'' → Descends W t v t'' v''

/-! ## The inductive invariant

Proof-side notions (none of them is used by the model above) and the invariant `Inv`, from which the safety theorems
follow. A publication is named by its *key*, its (term, version); its ghost parent is the key of the state its publisher
had accepted. Publications thus form a forest: following parents, versions strictly decrease until a term-0 key, the
*root*, which stands for a bootstrap state (several nodes may bootstrap, with different bootstrap configurations). All
notions are relations, never functions computed from the messages sent: `KeyLE` and `Below` compare keys, `Won` also
reads node states, and the others depend on the messages sent only. All sets of voters are lists of
cluster-manager-eligible nodes, so that `Params.InitCompatible` applies to them. -/

/-- The lexicographic order on (term, version) keys: `(t, v)` is at most `(t', v')`. -/
def KeyLE (t : Nat) (v : Int) (t' : Nat) (v' : Int) : Prop := t < t' ∨ (t = t' ∧ v ≤ v')

/-- The last accepted (term, version) `(lt, lv)` carried by a join is at or below the base `(bt, bv)` in the way
`handleJoin` compares them: an older term, or the same term and, unless that term is 0, a version at most `bv`.
(At term 0 a join carries a metadata version, `versionOrMetadataVersion`, which plays no role in safety.) -/
def Below (lt : Nat) (lv : Int) (bt : Nat) (bv : Int) : Prop := lt < bt ∨ (lt = bt ∧ (bt = 0 ∨ lv ≤ bv))

/-- A publication of term `t` and version `v` has been sent. -/
def Published (W : Cluster V) (t : Nat) (v : Int) : Prop :=
  ∃ src s pt pv, W.sent (.publishRequest src s pt pv) ∧ s.term = t ∧ s.version = v

/-- The pair of configurations `(x, y)` (last committed, last accepted) *realizes* the key `(t, v)`: either `t = 0`
and `x = y` is a bootstrap configuration (a bootstrap state), or `(t, v)` is the key of a sent publication whose last
accepted configuration is `y` and whose last committed configuration is `x` — or, if `(t, v)` is committed, whose last
accepted configuration is also `x` (a node that applied the commit, `markCommitted`). The accepted state of every
bootstrapped cluster-manager-eligible node realizes its own key (`Inv.accepted_realizes`). -/
def Realizes (P : Params) (W : Cluster V) (t : Nat) (v : Int) (x y : VotingConfiguration) : Prop :=
  (t = 0 ∧ x = y ∧ P.initConfs x) ∨
  ∃ src s pt pv, W.sent (.publishRequest src s pt pv) ∧ s.term = t ∧ s.version = v ∧
    y = s.lastAcceptedConfiguration ∧
    (x = s.lastCommittedConfiguration ∨ (x = s.lastAcceptedConfiguration ∧ Committed W t v))

/-- Every member of `J` is a cluster-manager-eligible node that sent node `L` a join for term `t`. -/
def JoinVoters (P : Params) (W : Cluster V) (L : NodeId) (t : Nat) (J : List NodeId) : Prop :=
  ∀ x ∈ J, P.eligible x = true ∧
    ∃ j : Join, W.sent (.join j) ∧ j.sourceNode.id = x ∧ j.targetNode.id = L ∧ j.term = t

/-- Every member of `J` is a cluster-manager-eligible node that sent node `L` a join for term `t` whose last accepted
(term, version) is `Below` the base `(bt, bv)`. -/
def BaseVoters (P : Params) (W : Cluster V) (L : NodeId) (t bt : Nat) (bv : Int) (J : List NodeId) : Prop :=
  ∀ x ∈ J, P.eligible x = true ∧
    ∃ j : Join, W.sent (.join j) ∧ j.sourceNode.id = x ∧ j.targetNode.id = L ∧ j.term = t ∧
      Below j.lastAcceptedTerm j.lastAcceptedVersion bt bv

/-- Every member of `A` is a cluster-manager-eligible node that sent a `PublishResponse` for term `t` and version
`v` (to any node). -/
def RespVoters (P : Params) (W : Cluster V) (t : Nat) (v : Int) (A : List NodeId) : Prop :=
  ∀ x ∈ A, P.eligible x = true ∧ ∃ d, W.sent (.publishResponse x d ⟨t, v⟩)

/-- An *election record* of node `L` for term `t`: the base `(bt, bv)` is of an older term, `(x, y)` realizes it, and
`J`, a quorum of both `x` and `y`, consists of eligible nodes that each sent `L` a term-`t` join with a last accepted
(term, version) `Below` the base. Both a node that has just won its election (its accepted state is the base) and the
first publication of a term (the publisher's state when it won) carry one. -/
def ElectionRecord (P : Params) (W : Cluster V) (L : NodeId) (t bt : Nat) (bv : Int) (x y : VotingConfiguration)
    (J : List NodeId) : Prop :=
  bt < t ∧ Realizes P W bt bv x y ∧ BaseVoters P W L t bt bv J ∧ x.hasQuorum J = true ∧ y.hasQuorum J = true

/-- Node `b` *won* term `t`: it is cluster-manager-eligible, and it has currently won the election of its current
term `t`, or it has sent a publication of term `t`. -/
def Won (P : Params) (W : Cluster V) (b : NodeId) (t : Nat) : Prop :=
  P.eligible b = true ∧
    (((W.node b).electionWon = true ∧ (W.node b).currentTerm = t) ∨
      ∃ s pt pv, W.sent (.publishRequest b s pt pv) ∧ s.term = t)

/-- The inductive invariant. Field names are descriptive; each docstring names the conjunct of the design it
transcribes (labels P*, C1, J*, R*, N*, L*, listed in `NOTES_OpenSearchSafety.md`). Node facts about the persisted
state hold for cluster-manager-eligible nodes only (a node that is not eligible may restart with any persisted state);
facts about the transient state hold for every node (a node that is not eligible never receives a join, so never holds
votes or wins). -/
structure Inv (P : Params) (W : Cluster V) : Prop where
  -- Every node.
  /-- Every node's `localNode` is its own `DiscoveryNode` `P.dn n`. -/
  localNode_eq : ∀ n, (W.node n).localNode = P.dn n
  /-- (N4) A node that has not won its election has last published version 0 and holds no publish votes. -/
  idle_of_not_won : ∀ n, (W.node n).electionWon = false →
    (W.node n).lastPublishedVersion = 0 ∧ (W.node n).publishVotes = VoteCollection.empty
  /-- (N2) A node that has won its election has started a join since its last restart. -/
  won_started : ∀ n, (W.node n).electionWon = true → (W.node n).startedJoinSinceLastReboot = true
  /-- (N6) A node that holds join votes has started a join since its last restart. -/
  votes_started : ∀ n, (W.node n).joinVotes.nodes ≠ [] → (W.node n).startedJoinSinceLastReboot = true
  /-- (N10) A node that has started a join since its last restart is in a term ≥ 1. -/
  started_term_pos : ∀ n, (W.node n).startedJoinSinceLastReboot = true → 1 ≤ (W.node n).currentTerm
  /-- (N3) The join votes of a node that has won are a quorum of both its last committed and its last accepted
  configuration. -/
  won_quorum : ∀ n, (W.node n).electionWon = true →
    (W.node n).joinVotes.isQuorum (W.node n).lastCommittedConfiguration = true ∧
    (W.node n).joinVotes.isQuorum (W.node n).lastAcceptedConfiguration = true
  /-- (N3r: for the default election strategy, the reverse half of `invariant()`'s second assertion; it omits the
  strategy's additional constraint) The join votes of a node that has not won are not a quorum of both its last
  committed and its last accepted configuration. -/
  not_won_no_quorum : ∀ n, (W.node n).electionWon = false →
    ¬ ((W.node n).joinVotes.isQuorum (W.node n).lastCommittedConfiguration = true ∧
      (W.node n).joinVotes.isQuorum (W.node n).lastAcceptedConfiguration = true)
  /-- (N8) Every join vote node `n` holds is of an eligible node `m` that sent `n` a join for `n`'s current term, with
  a last accepted (term, version) `Below` `n`'s last accepted (term, version). -/
  joinVotes_sent : ∀ n m, m ∈ (W.node n).joinVotes.nodes → P.eligible m = true ∧
    ∃ j : Join, W.sent (.join j) ∧ j.sourceNode.id = m ∧ j.targetNode.id = n ∧
      j.term = (W.node n).currentTerm ∧
      Below j.lastAcceptedTerm j.lastAcceptedVersion (W.node n).lastAcceptedTerm (W.node n).lastAcceptedVersion
  /-- (N9) Every publish vote node `n` holds is of an eligible node `m` that sent `n` a `PublishResponse` for `n`'s
  current term and last published version. -/
  publishVotes_sent : ∀ n m, m ∈ (W.node n).publishVotes.nodes → P.eligible m = true ∧
    W.sent (.publishResponse m n ⟨(W.node n).currentTerm, (W.node n).lastPublishedVersion⟩)
  -- Cluster-manager-eligible nodes.
  /-- (N1) The last accepted term of an eligible node is at most its current term. -/
  term_le : ∀ n, P.eligible n = true → (W.node n).lastAcceptedTerm ≤ (W.node n).currentTerm
  /-- (N7) The accepted state of an eligible node is either a never-bootstrapped term-0 state with empty
  configurations, or its configurations `Realize` its key: a bootstrap state with a bootstrap configuration, or a sent
  publication's term, version and configurations (the last committed one possibly replaced by the last accepted one,
  if the publication is committed). Nothing else of the state (payload, metadata version, cluster-manager node,
  cluster-UUID flags) is related to the publication, since a restart may rebuild it. -/
  accepted_realizes : ∀ n, P.eligible n = true →
    ((W.node n).lastAcceptedTerm = 0 ∧
      (W.node n).lastCommittedConfiguration = VotingConfiguration.EMPTY_CONFIG ∧
      (W.node n).lastAcceptedConfiguration = VotingConfiguration.EMPTY_CONFIG) ∨
    Realizes P W (W.node n).lastAcceptedTerm (W.node n).lastAcceptedVersion
      (W.node n).lastCommittedConfiguration (W.node n).lastAcceptedConfiguration
  -- Joins and publish responses.
  /-- Every join comes from the `DiscoveryNode` of its source and is addressed to an eligible node. -/
  join_wf : ∀ j : Join, W.sent (.join j) →
    j.sourceNode = P.dn j.sourceNode.id ∧ P.eligible j.targetNode.id = true
  /-- (J1) An eligible node's joins are for terms at most its current term. -/
  join_term_le : ∀ j : Join, W.sent (.join j) → P.eligible j.sourceNode.id = true →
    j.term ≤ (W.node j.sourceNode.id).currentTerm
  /-- (J2) An eligible node sends at most one join per term. -/
  join_unique : ∀ j j' : Join, W.sent (.join j) → W.sent (.join j') → P.eligible j.sourceNode.id = true →
    j.sourceNode.id = j'.sourceNode.id → j.term = j'.term → j = j'
  /-- (J3) An eligible node's join for a term later than one of its publish responses carries a last accepted
  (term, version) at least that of the response: it accepted before it voted. -/
  join_after_response : ∀ (j : Join) (a d : NodeId) (r : PublishResponse), W.sent (.join j) →
    W.sent (.publishResponse a d r) → j.sourceNode.id = a → P.eligible a = true → r.term < j.term →
    KeyLE r.term r.version j.lastAcceptedTerm j.lastAcceptedVersion
  /-- (R1) An eligible node's publish responses are for terms at most its current term, and for (term, version)s at
  most its last accepted (term, version). -/
  response_le : ∀ (a d : NodeId) (r : PublishResponse), W.sent (.publishResponse a d r) → P.eligible a = true →
    r.term ≤ (W.node a).currentTerm ∧
    KeyLE r.term r.version (W.node a).lastAcceptedTerm (W.node a).lastAcceptedVersion
  /-- (R2) Every publish response answers a publication of its (term, version) sent by the node it is addressed to. -/
  response_published : ∀ (a d : NodeId) (r : PublishResponse), W.sent (.publishResponse a d r) →
    ∃ s pt pv, W.sent (.publishRequest d s pt pv) ∧ s.term = r.term ∧ s.version = r.version
  -- Publications.
  /-- (P1) Every publication is sent by an eligible node, has term ≥ 1 (so the Zen1 branch of
  `handlePublishRequest` is dead), a parent of at most its term and of a smaller version, and, if its parent is a
  bootstrap state (term 0), a bootstrap configuration as last committed configuration. -/
  pub_wf : ∀ src s pt pv, W.sent (.publishRequest src s pt pv) →
    P.eligible src = true ∧ 1 ≤ s.term ∧ pt ≤ s.term ∧ pv < s.version ∧
    (pt = 0 → P.initConfs s.lastCommittedConfiguration)
  /-- (P1, P5) The parent of a publication, if not a bootstrap state, is a publication (of key `(pt, pv)`), and the
  configurations follow the reconfiguration discipline: the last committed configuration is the parent's, or, if the
  parent is committed, the parent's last accepted one (reconfiguration rule R1); and the last accepted configuration
  changes only if the last committed configuration is the parent's last accepted one (reconfiguration rule R2). -/
  pub_parent : ∀ src s pt pv, W.sent (.publishRequest src s pt pv) → 1 ≤ pt →
    ∃ src' s' pt' pv', W.sent (.publishRequest src' s' pt' pv') ∧ s'.term = pt ∧ s'.version = pv ∧
      (s.lastCommittedConfiguration = s'.lastCommittedConfiguration ∨
        (s.lastCommittedConfiguration = s'.lastAcceptedConfiguration ∧ Committed W pt pv)) ∧
      (s.lastAcceptedConfiguration ≠ s'.lastAcceptedConfiguration →
        s.lastCommittedConfiguration = s'.lastAcceptedConfiguration)
  /-- (P2) Two publications with the same key are the same message (source, state and parent). -/
  pub_unique : ∀ src s pt pv src' s' pt' pv', W.sent (.publishRequest src s pt pv) →
    W.sent (.publishRequest src' s' pt' pv') → s.term = s'.term → s.version = s'.version →
    src = src' ∧ s = s' ∧ pt = pt' ∧ pv = pv'
  /-- Every publication descends from a root (a term-0 key): the chain of its ancestors is finite. -/
  pub_rooted : ∀ src s pt pv, W.sent (.publishRequest src s pt pv) → ∃ v₀, Descends W 0 v₀ s.term s.version
  /-- (P4) Two publications of the same term are related by descent. -/
  pub_same_term : ∀ src s pt pv src' s' pt' pv', W.sent (.publishRequest src s pt pv) →
    W.sent (.publishRequest src' s' pt' pv') → s.term = s'.term →
    Descends W s.term s.version s'.term s'.version ∨ Descends W s'.term s'.version s.term s.version
  /-- (P6) The eligible nodes that sent the publisher a join for the publication's term include a quorum of both of
  the publication's configurations. -/
  pub_voters : ∀ src s pt pv, W.sent (.publishRequest src s pt pv) →
    ∃ J, JoinVoters P W src s.term J ∧ s.lastCommittedConfiguration.hasQuorum J = true ∧
      s.lastAcceptedConfiguration.hasQuorum J = true
  /-- (P7) The first publication of a term (its parent is of an older term) carries the election record of its
  publisher: the parent key, realized by the publication's last committed configuration and some `y` (the parent's
  last accepted configuration), with a quorum of joins `Below` the parent. -/
  pub_election : ∀ src s pt pv, W.sent (.publishRequest src s pt pv) → pt < s.term →
    ∃ y J, ElectionRecord P W src s.term pt pv s.lastCommittedConfiguration y J
  -- Commits.
  /-- (C1, with the weakening forced by `handleCommit` at a leader, D1) Every commit is of a sent publication whose
  publish responses from eligible nodes include a quorum `A` of its last accepted configuration and either of its last
  committed configuration, or (D1) its parent is committed and has the same last accepted configuration. -/
  commit_quorum : ∀ c : ApplyCommitRequest, W.sent (.applyCommit c) →
    ∃ src s pt pv, W.sent (.publishRequest src s pt pv) ∧ s.term = c.term ∧ s.version = c.version ∧
      ∃ A, RespVoters P W c.term c.version A ∧ s.lastAcceptedConfiguration.hasQuorum A = true ∧
        (s.lastCommittedConfiguration.hasQuorum A = true ∨
          (Committed W pt pv ∧ ∃ src' s' pt' pv', W.sent (.publishRequest src' s' pt' pv') ∧ s'.term = pt ∧
            s'.version = pv ∧ s'.lastAcceptedConfiguration = s.lastAcceptedConfiguration))
  -- Leaders.
  /-- (L1) For each term `t`, at most one node `b` has `Won P W b t`. -/
  won_unique : ∀ a b t, Won P W a t → Won P W b t → a = b
  /-- (L2) A node that published in a term is past that term, or still in it and either still elected or restarted
  since (so it cannot win that term again). -/
  pub_source_term : ∀ src s pt pv, W.sent (.publishRequest src s pt pv) →
    s.term < (W.node src).currentTerm ∨
    (s.term = (W.node src).currentTerm ∧
      ((W.node src).electionWon = true ∨ (W.node src).startedJoinSinceLastReboot = false))
  /-- (L3) Every publication of an elected node's current term, whoever sent it, has a version at most the node's last
  published version, (current term, last published version) descends from it, and the node's join votes are a quorum
  of both of its configurations. -/
  leader_pubs : ∀ n, (W.node n).electionWon = true → ∀ src s pt pv, W.sent (.publishRequest src s pt pv) →
    s.term = (W.node n).currentTerm →
    s.version ≤ (W.node n).lastPublishedVersion ∧
    Descends W s.term s.version (W.node n).currentTerm (W.node n).lastPublishedVersion ∧
    (W.node n).joinVotes.isQuorum s.lastCommittedConfiguration = true ∧
    (W.node n).joinVotes.isQuorum s.lastAcceptedConfiguration = true
  /-- (L4) An elected node with a publication in flight (last published version ≠ last accepted version) sent it on
  top of its current accepted key; its last published configuration is that publication's last accepted one; and its
  last committed configuration is the publication's, or (D1: the node applied the commit of its accepted state) the
  publication's last accepted configuration, its accepted state being committed with that same last accepted
  configuration. -/
  leader_inflight : ∀ n, (W.node n).electionWon = true →
    (W.node n).lastPublishedVersion ≠ (W.node n).lastAcceptedVersion →
    ∃ s, W.sent (.publishRequest n s (W.node n).lastAcceptedTerm (W.node n).lastAcceptedVersion) ∧
      s.term = (W.node n).currentTerm ∧ s.version = (W.node n).lastPublishedVersion ∧
      (W.node n).lastPublishedConfiguration = s.lastAcceptedConfiguration ∧
      ((W.node n).lastCommittedConfiguration = s.lastCommittedConfiguration ∨
        ((W.node n).lastCommittedConfiguration = s.lastAcceptedConfiguration ∧
          Committed W (W.node n).lastAcceptedTerm (W.node n).lastAcceptedVersion ∧
          (W.node n).lastAcceptedConfiguration = s.lastAcceptedConfiguration))
  /-- (L5) An elected node with no publication in flight has either accepted a publication of its term (and its last
  published configuration is its last accepted one), or has an accepted state of an older term and no publication of
  its term exists. -/
  leader_settled : ∀ n, (W.node n).electionWon = true →
    (W.node n).lastPublishedVersion = (W.node n).lastAcceptedVersion →
    ((W.node n).lastAcceptedTerm = (W.node n).currentTerm ∧
      (W.node n).lastPublishedConfiguration = (W.node n).lastAcceptedConfiguration) ∨
    ((W.node n).lastAcceptedTerm < (W.node n).currentTerm ∧
      ∀ src s pt pv, W.sent (.publishRequest src s pt pv) → s.term ≠ (W.node n).currentTerm)

end OpenSearchSafety
Source
OpenSearch b2a54ba5c0defba3d1d20423e911d4bf920bab19: CoordinationState (the per-node handlers as transcribed by the OpenSearchCoordination mission; handleCommit lines 523-573, isPublishQuorum 156-158, invariant 601-611): https://github.com/opensearch-project/OpenSearch/blob/b2a54ba5c0defba3d1d20423e911d4bf920bab19/server/src/main/java/org/opensearch/cluster/coordination/CoordinationState.java; Coordinator (the calls into CoordinationState: handleApplyCommit lines 419-452, handlePublishRequest 454-526, startElection 583-602, abdicateTo 604-620, ensureTermAtLeast 635-641, joinLeaderInTerm 643-657, setInitialConfiguration 1101-1161, handleJoin 1267-1299, publish 1350 with the handleClientValue call at 1404, CoordinatorPublication.handlePublishResponse 1871-1876): https://github.com/opensearch-project/OpenSearch/blob/b2a54ba5c0defba3d1d20423e911d4bf920bab19/server/src/main/java/org/opensearch/cluster/coordination/Coordinator.java; ClusterBootstrapService (requirements 146-157, onFoundPeersUpdated 176-215, startBootstrap 259-273, checkRequirements 306-335): https://github.com/opensearch-project/OpenSearch/blob/b2a54ba5c0defba3d1d20423e911d4bf920bab19/server/src/main/java/org/opensearch/cluster/coordination/ClusterBootstrapService.java#L146-L335; GatewayMetaState.start (persisted state loaded and rebuilt 141-231, remote restore 169-188, synchronous and asynchronous persistence 199-207, nodes without the cluster-manager and data roles 232-255): https://github.com/opensearch-project/OpenSearch/blob/b2a54ba5c0defba3d1d20423e911d4bf920bab19/server/src/main/java/org/opensearch/gateway/GatewayMetaState.java#L126-L257; PersistedStateRegistry.addPersistedState (lines 38-41): https://github.com/opensearch-project/OpenSearch/blob/b2a54ba5c0defba3d1d20423e911d4bf920bab19/server/src/main/java/org/opensearch/cluster/coordination/PersistedStateRegistry.java#L38-L41; ElectionStrategy (DEFAULT_INSTANCE lines 46-59): https://github.com/opensearch-project/OpenSearch/blob/b2a54ba5c0defba3d1d20423e911d4bf920bab19/server/src/main/java/org/opensearch/cluster/coordination/ElectionStrategy.java#L44-L110; the randomized safety test CoordinationStateTestCluster (reboot 156-193, runRandomly 279-329, invariant 331-370): https://github.com/opensearch-project/OpenSearch/blob/b2a54ba5c0defba3d1d20423e911d4bf920bab19/test/framework/src/main/java/org/opensearch/cluster/coordination/CoordinationStateTestCluster.java and CoordinationStateTests.testSafety (lines 917-924): https://github.com/opensearch-project/OpenSearch/blob/b2a54ba5c0defba3d1d20423e911d4bf920bab19/server/src/test/java/org/opensearch/cluster/coordination/CoordinationStateTests.java#L917-L924; for comparison, Elastic's TLA+ model ZenWithTerms (HandleCommit 241-250, CommittedValuesDescendantsFromInitialValue 338-347, CommitHasQuorumVsPreviousCommittedConfiguration 349-358): https://github.com/elastic/elasticsearch-formal-models/blob/ca30663506a7e18de9d23fabbc70a369903d7c98/ZenWithTerms/tla/ZenWithTerms.tla
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_OpenSearchSafety.lean

This file imports Definitions.Def_OpenSearchCoordination and introduces, in the namespace OpenSearchSafety (with OpenSearchCoordination opened), 25 declarations, in this order: the message type Message; the parameters Params, with Params.dn and the condition Params.InitCompatible; the predicate BootstrapConfig; the cluster type Cluster with the updates Cluster.set and Cluster.send; Initial, RestartState, the step relation Step and Reachable (together, the model); the relations Committed, Parent and Descends on (term, version) pairs; and, under the heading "The inductive invariant", the proof-side notions KeyLE, Below, Published, Realizes, JoinVoters, BaseVoters, RespVoters, ElectionRecord, Won and the 30-field invariant Inv. The imported notions are expanded first so that each declaration can be read on its own. Java line citations were checked against the local OpenSearch checkout, whose HEAD is the cited revision b2a54ba5c0defba3d1d20423e911d4bf920bab19.

Imported notions, expanded

Node ids and discovery nodes. A node id is a natural number (Java: a string; only equality is used). A discovery node is a pair (id ∈N\in \mathbb{N}∈N, cluster-manager flag ∈Bool\in \mathrm{Bool}∈Bool); two discovery nodes are equal iff both components are equal. ZEN1_BWC_TERM=0\mathrm{ZEN1\_BWC\_TERM} = 0ZEN1_BWC_TERM=0.

Voting configurations. A voting configuration ccc is a list c.nodeIdsc.\mathrm{nodeIds}c.nodeIds of node ids together with a proof that the list is strictly increasing. It therefore has no duplicates, and two configurations are equal iff their lists are equal, i.e. iff they contain the same ids. EMPTY\mathrm{EMPTY}EMPTY is the configuration with the empty list; ccc is empty iff its list is empty. For a list qqq of node ids,

c.hasQuorum(q)  ⟺  2⋅∣{x∈c.nodeIds:x∈q}∣>∣c.nodeIds∣,c.\mathrm{hasQuorum}(q) \iff 2\cdot\big|\{x \in c.\mathrm{nodeIds} : x \in q\}\big| > |c.\mathrm{nodeIds}|,c.hasQuorum(q)⟺2⋅​{x∈c.nodeIds:x∈q}​>∣c.nodeIds∣,

the count ranging over the (duplicate-free) members of ccc: strictly more than half of the members of ccc occur in qqq. Members of qqq outside ccc, the order of qqq and repetitions in qqq are irrelevant, and EMPTY\mathrm{EMPTY}EMPTY has no quorum (not even of [ ][\,][], since 0>00 > 00>0 fails). Below, "qqq is a quorum of ccc" means c.hasQuorum(q)c.\mathrm{hasQuorum}(q)c.hasQuorum(q).

Vote collections. A vote collection is a list of node ids (most recent first); the empty collection is [ ][\,][]. For a discovery node δ\deltaδ, addVote(v,δ)\mathrm{addVote}(v, \delta)addVote(v,δ) is (δ.id::v, true)(\delta.\mathrm{id} :: v,\ \mathrm{true})(δ.id::v, true) if δ\deltaδ's cluster-manager flag is true and δ.id∉v\delta.\mathrm{id} \notin vδ.id∈/v, and (v, false)(v,\ \mathrm{false})(v, false) otherwise; so a vote from a node whose flag is false is never recorded, and a node is recorded at most once. A collection vvv is a quorum of ccc iff c.hasQuorum(v)c.\mathrm{hasQuorum}(v)c.hasQuorum(v); it contains a vote for δ\deltaδ iff δ.id∈v\delta.\mathrm{id} \in vδ.id∈v; it is empty iff v=[ ]v = [\,]v=[].

Cluster states. A cluster state sss over a payload type VVV has nine fields: s.term∈Ns.\mathrm{term} \in \mathbb{N}s.term∈N; s.version∈Zs.\mathrm{version} \in \mathbb{Z}s.version∈Z; s.metadataVersion∈Zs.\mathrm{metadataVersion} \in \mathbb{Z}s.metadataVersion∈Z; configurations s.lccs.\mathrm{lcc}s.lcc (last committed) and s.lacs.\mathrm{lac}s.lac (last accepted); s.cmns.\mathrm{cmn}s.cmn, the cluster-manager node, which is "none" or "some mmm" with m∈Nm \in \mathbb{N}m∈N; Booleans s.uuidKnowns.\mathrm{uuidKnown}s.uuidKnown and s.uuidCommitteds.\mathrm{uuidCommitted}s.uuidCommitted; and a payload s.value∈Vs.\mathrm{value} \in Vs.value∈V. Its key is the pair (s.term,s.version)∈N×Z(s.\mathrm{term}, s.\mathrm{version}) \in \mathbb{N} \times \mathbb{Z}(s.term,s.version)∈N×Z. vomv(s)\mathrm{vomv}(s)vomv(s) ("version or metadata version") is s.metadataVersions.\mathrm{metadataVersion}s.metadataVersion if s.term=0s.\mathrm{term} = 0s.term=0 and s.versions.\mathrm{version}s.version otherwise. markCommitted(s)\mathrm{markCommitted}(s)markCommitted(s) is sss with s.lccs.\mathrm{lcc}s.lcc replaced by s.lacs.\mathrm{lac}s.lac (no change if they are already equal) and then, if s.uuidKnowns.\mathrm{uuidKnown}s.uuidKnown is true and s.uuidCommitteds.\mathrm{uuidCommitted}s.uuidCommitted is false, s.uuidCommitteds.\mathrm{uuidCommitted}s.uuidCommitted set to true; every other field is unchanged.

Message payloads. A start-join request is a pair (source discovery node, term ∈N\in \mathbb{N}∈N). A join jjj consists of a source discovery node j.srcj.\mathrm{src}j.src, a target discovery node j.tgtj.\mathrm{tgt}j.tgt, a term j.term∈Nj.\mathrm{term} \in \mathbb{N}j.term∈N, a last accepted term j.lat∈Nj.\mathrm{lat} \in \mathbb{N}j.lat∈N and a last accepted version j.lav∈Zj.\mathrm{lav} \in \mathbb{Z}j.lav∈Z; equality of joins is equality of all five fields. A publish request wraps one cluster state. A publish response is a pair (t,v)∈N×Z(t, v) \in \mathbb{N} \times \mathbb{Z}(t,v)∈N×Z. An apply-commit request is a triple (source discovery node, term ∈N\in \mathbb{N}∈N, version ∈Z\in \mathbb{Z}∈Z).

Election strategies. An election strategy is a single Boolean function extra(δ,t,at,av,c1,c2,votes)\mathrm{extra}(\delta, t, at, av, c_1, c_2, \mathit{votes})extra(δ,t,at,av,c1​,c2​,votes) of a discovery node, a current term, an accepted term, an accepted version, two configurations and a vote collection. The default strategy returns true on every input. (ElectionStrategy.Monotone is defined in the imported file and not used in this one.)

Coordination states. A coordination state ccc has nine fields: c.localNodec.\mathrm{localNode}c.localNode, a discovery node; the persisted part c.currentTerm∈Nc.\mathrm{currentTerm} \in \mathbb{N}c.currentTerm∈N and c.accc.\mathrm{acc}c.acc (the last accepted cluster state); and the transient part c.joinVotesc.\mathrm{joinVotes}c.joinVotes, c.startedc.\mathrm{started}c.started ("started a join since the last reboot"), c.wonc.\mathrm{won}c.won ("election won"), c.lpv∈Zc.\mathrm{lpv} \in \mathbb{Z}c.lpv∈Z (last published version), c.lpcc.\mathrm{lpc}c.lpc (last published configuration) and c.publishVotesc.\mathrm{publishVotes}c.publishVotes. Derived: c.lat=c.acc.termc.\mathrm{lat} = c.\mathrm{acc}.\mathrm{term}c.lat=c.acc.term, c.lav=c.acc.versionc.\mathrm{lav} = c.\mathrm{acc}.\mathrm{version}c.lav=c.acc.version, c.lcc=c.acc.lccc.\mathrm{lcc} = c.\mathrm{acc}.\mathrm{lcc}c.lcc=c.acc.lcc, c.lac=c.acc.lacc.\mathrm{lac} = c.\mathrm{acc}.\mathrm{lac}c.lac=c.acc.lac. The constructor init(δ,t,s)\mathrm{init}(\delta, t, s)init(δ,t,s) is the coordination state with local node δ\deltaδ, current term ttt, accepted state sss, empty join votes, started=won=false\mathrm{started} = \mathrm{won} = \mathrm{false}started=won=false, lpv=0\mathrm{lpv} = 0lpv=0, lpc=s.lac\mathrm{lpc} = s.\mathrm{lac}lpc=s.lac and empty publish votes.

isElectionQuorum(es,c,votes)\mathrm{isElectionQuorum}(es, c, \mathit{votes})isElectionQuorum(es,c,votes) holds iff votes\mathit{votes}votes is a quorum of c.lccc.\mathrm{lcc}c.lcc, is a quorum of c.lacc.\mathrm{lac}c.lac, and es.extra(c.localNode,c.currentTerm,c.lat,c.lav,c.lcc,c.lac,votes)es.\mathrm{extra}(c.\mathrm{localNode}, c.\mathrm{currentTerm}, c.\mathrm{lat}, c.\mathrm{lav}, c.\mathrm{lcc}, c.\mathrm{lac}, \mathit{votes})es.extra(c.localNode,c.currentTerm,c.lat,c.lav,c.lcc,c.lac,votes) is true. isPublishQuorum(c,votes)\mathrm{isPublishQuorum}(c, \mathit{votes})isPublishQuorum(c,votes) holds iff votes\mathit{votes}votes is a quorum of c.lccc.\mathrm{lcc}c.lcc and of c.lpcc.\mathrm{lpc}c.lpc.

The handlers return either an error or a result; the cluster steps below use only successful calls ("succeeds with"). Guards are tested in the order listed, and the first guard that applies produces the error.

  • setInitialState(c,s)\mathrm{setInitialState}(c, s)setInitialState(c,s): error if c.lacc.\mathrm{lac}c.lac is non-empty; otherwise succeeds with ccc with acc:=s\mathrm{acc} := sacc:=s. Its contract initialStateContract(c,s)\mathrm{initialStateContract}(c, s)initialStateContract(c,s) (Java assertions, not checked by the handler) is the conjunction: c.lat=0c.\mathrm{lat} = 0c.lat=0; c.lccc.\mathrm{lcc}c.lcc empty; c.lpv=0c.\mathrm{lpv} = 0c.lpv=0; c.lpcc.\mathrm{lpc}c.lpc empty; c.won=falsec.\mathrm{won} = \mathrm{false}c.won=false; c.joinVotesc.\mathrm{joinVotes}c.joinVotes empty; c.publishVotesc.\mathrm{publishVotes}c.publishVotes empty; s.term=0s.\mathrm{term} = 0s.term=0; s.version=c.lavs.\mathrm{version} = c.\mathrm{lav}s.version=c.lav; s.lacs.\mathrm{lac}s.lac non-empty; s.lccs.\mathrm{lcc}s.lcc non-empty.
  • handleStartJoin(c,(δ,t))\mathrm{handleStartJoin}(c, (\delta, t))handleStartJoin(c,(δ,t)): error if t≤c.currentTermt \le c.\mathrm{currentTerm}t≤c.currentTerm; otherwise succeeds with the pair of (ccc with currentTerm:=t\mathrm{currentTerm} := tcurrentTerm:=t, lpv:=0\mathrm{lpv} := 0lpv:=0, lpc:=c.lac\mathrm{lpc} := c.\mathrm{lac}lpc:=c.lac, started:=true\mathrm{started} := \mathrm{true}started:=true, won:=false\mathrm{won} := \mathrm{false}won:=false, joinVotes:=[ ]\mathrm{joinVotes} := [\,]joinVotes:=[], publishVotes:=[ ]\mathrm{publishVotes} := [\,]publishVotes:=[]) and the join (c.localNode, δ, t, c.lat, vomv(c.acc))(c.\mathrm{localNode},\ \delta,\ t,\ c.\mathrm{lat},\ \mathrm{vomv}(c.\mathrm{acc}))(c.localNode, δ, t, c.lat, vomv(c.acc)). The accepted state is unchanged.
  • handleJoin(es,c,j)\mathrm{handleJoin}(es, c, j)handleJoin(es,c,j): (1) error if j.term≠c.currentTermj.\mathrm{term} \neq c.\mathrm{currentTerm}j.term=c.currentTerm; (2) error if c.startedc.\mathrm{started}c.started is false; (3) error if j.lat>c.latj.\mathrm{lat} > c.\mathrm{lat}j.lat>c.lat; (4) error if j.lat=c.latj.\mathrm{lat} = c.\mathrm{lat}j.lat=c.lat and j.lav>vomv(c.acc)j.\mathrm{lav} > \mathrm{vomv}(c.\mathrm{acc})j.lav>vomv(c.acc); (5) error if c.lacc.\mathrm{lac}c.lac is empty; otherwise, with (votes,added)=addVote(c.joinVotes,j.src)(\mathit{votes}, \mathit{added}) = \mathrm{addVote}(c.\mathrm{joinVotes}, j.\mathrm{src})(votes,added)=addVote(c.joinVotes,j.src) and w=isElectionQuorum(es,c,votes)w = \mathrm{isElectionQuorum}(es, c, \mathit{votes})w=isElectionQuorum(es,c,votes) (evaluated on ccc's own terms and configurations, which the call does not change), succeeds with (c′,added)(c', \mathit{added})(c′,added), where c′c'c′ is ccc with joinVotes:=votes\mathrm{joinVotes} := \mathit{votes}joinVotes:=votes and won:=w\mathrm{won} := wwon:=w, and in addition lpv:=c.lav\mathrm{lpv} := c.\mathrm{lav}lpv:=c.lav when www is true and c.wonc.\mathrm{won}c.won was false. The target of jjj is not checked (Java asserts it), and nothing prevents won\mathrm{won}won from going from true to false (Java only asserts that it cannot).
  • handleClientValue(c,s)\mathrm{handleClientValue}(c, s)handleClientValue(c,s): (1) error if c.wonc.\mathrm{won}c.won is false; (2) error if c.lpv≠c.lavc.\mathrm{lpv} \neq c.\mathrm{lav}c.lpv=c.lav; (3) error if s.term≠c.currentTerms.\mathrm{term} \neq c.\mathrm{currentTerm}s.term=c.currentTerm; (4) error if s.version≤c.lpvs.\mathrm{version} \le c.\mathrm{lpv}s.version≤c.lpv; (5) error if s.lac≠c.lacs.\mathrm{lac} \neq c.\mathrm{lac}s.lac=c.lac and c.lcc≠c.lacc.\mathrm{lcc} \neq c.\mathrm{lac}c.lcc=c.lac; (6) error if c.joinVotesc.\mathrm{joinVotes}c.joinVotes is not a quorum of s.lacs.\mathrm{lac}s.lac; otherwise succeeds with (ccc with lpv:=s.version\mathrm{lpv} := s.\mathrm{version}lpv:=s.version, lpc:=s.lac\mathrm{lpc} := s.\mathrm{lac}lpc:=s.lac, publishVotes:=[ ]\mathrm{publishVotes} := [\,]publishVotes:=[]; the publish request of sss). Its contract clientValueContract(c,s)\mathrm{clientValueContract}(c, s)clientValueContract(c,s) is s.lcc=c.lccs.\mathrm{lcc} = c.\mathrm{lcc}s.lcc=c.lcc.
  • handlePublishRequest(c,s)\mathrm{handlePublishRequest}(c, s)handlePublishRequest(c,s): (1) error if s.term≠c.currentTerms.\mathrm{term} \neq c.\mathrm{currentTerm}s.term=c.currentTerm; (2) else, if s.term=c.lats.\mathrm{term} = c.\mathrm{lat}s.term=c.lat and s.version≤c.lavs.\mathrm{version} \le c.\mathrm{lav}s.version≤c.lav: when s.term=0s.\mathrm{term} = 0s.term=0, error if s.cmns.\mathrm{cmn}s.cmn is none, accept if s.cmn=some ms.\mathrm{cmn} = \text{some } ms.cmn=some m and "some mmm" differs from c.acc.cmnc.\mathrm{acc}.\mathrm{cmn}c.acc.cmn, error otherwise; when s.term≠0s.\mathrm{term} \neq 0s.term=0, error; (3) otherwise accept. Accept means: succeed with (ccc with acc:=s\mathrm{acc} := sacc:=s; the response (s.term,s.version)(s.\mathrm{term}, s.\mathrm{version})(s.term,s.version)). Transient fields are unchanged.
  • handlePublishResponse(c,δ,(t,v))\mathrm{handlePublishResponse}(c, \delta, (t, v))handlePublishResponse(c,δ,(t,v)): (1) error if c.wonc.\mathrm{won}c.won is false; (2) error if t≠c.currentTermt \neq c.\mathrm{currentTerm}t=c.currentTerm; (3) error if v≠c.lpvv \neq c.\mathrm{lpv}v=c.lpv; otherwise, with votes\mathit{votes}votes the first component of addVote(c.publishVotes,δ)\mathrm{addVote}(c.\mathrm{publishVotes}, \delta)addVote(c.publishVotes,δ) and c′c'c′ equal to ccc with publishVotes:=votes\mathrm{publishVotes} := \mathit{votes}publishVotes:=votes, succeeds with (c′, some (c.localNode,t,v))(c',\ \text{some }(c.\mathrm{localNode}, t, v))(c′, some (c.localNode,t,v)) if votes\mathit{votes}votes is a quorum of c.lccc.\mathrm{lcc}c.lcc and of c.lpcc.\mathrm{lpc}c.lpc, and with (c′, none)(c',\ \text{none})(c′, none) otherwise.
  • handleCommit(c,(σ,t,v))\mathrm{handleCommit}(c, (\sigma, t, v))handleCommit(c,(σ,t,v)): (1) error if t≠c.currentTermt \neq c.\mathrm{currentTerm}t=c.currentTerm; (2) error if t≠c.latt \neq c.\mathrm{lat}t=c.lat; (3) error if v≠c.lavv \neq c.\mathrm{lav}v=c.lav; otherwise succeeds with ccc with acc:=markCommitted(c.acc)\mathrm{acc} := \mathrm{markCommitted}(c.\mathrm{acc})acc:=markCommitted(c.acc).

(javaInvariant is defined in the imported file and not used in this one.)

Citation check of the imported transcription. The handlers above, the constructor (CS:84-106), isElectionQuorum (CS:144-154 with ES:68-88), isPublishQuorum (CS:156-158), VoteCollection.addVote (CS:755-757; handleJoin calls addJoinVote, CS:759-765, which calls addVote and only additionally records the join), VotingConfiguration.hasQuorum, isEmpty and EMPTY_CONFIG (CM:405-409, 433-435, 385), getVersionOrMetadataVersion (CLS:239-244), markLastAcceptedStateAsCommitted with commitVotingConfiguration (CS:703-740) and ZEN1_BWC_TERM (Coordinator.java:134) were compared with the cited lines and match, guards and their order included, up to the abstractions the imported file declares (remote persisted state omitted, Java assertions turned into contracts, a null incoming cluster-manager in the Zen1 branch treated as a rejection).

Declaration 1: Message

Message V is an inductive type with four constructors; messages are equal iff they have the same constructor and equal arguments (for publish requests this includes the whole cluster state, payload included).

  • join j, for a join jjj.
  • publishRequest src s pt pv, written PR(src,s,pt,pv)\mathrm{PR}(\mathit{src}, s, pt, pv)PR(src,s,pt,pv): a source node id src\mathit{src}src, a cluster state sss, and pt∈Npt \in \mathbb{N}pt∈N, pv∈Zpv \in \mathbb{Z}pv∈Z, the ghost parent (term, version) (docstring: "with the ghost parent"). A publish request has no addressee.
  • publishResponse src dest r, written RESP(src,dest,(t,v))\mathrm{RESP}(\mathit{src}, \mathit{dest}, (t, v))RESP(src,dest,(t,v)) for r=(t,v)r = (t, v)r=(t,v): a response from node id src\mathit{src}src to node id dest\mathit{dest}dest.
  • applyCommit c, written AC(σ,t,v)\mathrm{AC}(\sigma, t, v)AC(σ,t,v) for c=(σ,t,v)c = (\sigma, t, v)c=(σ,t,v); the source σ\sigmaσ is a discovery node. It has no addressee.

Start-join requests are not messages of the model.

Declaration 2: Params

A structure with three fields: P.eligible:N→BoolP.\mathrm{eligible} : \mathbb{N} \to \mathrm{Bool}P.eligible:N→Bool (docstring: DiscoveryNode.isClusterManagerNode() of each node; it is fixed for the whole execution); P.initConfsP.\mathrm{initConfs}P.initConfs, an arbitrary predicate on voting configurations, "the configurations a node may bootstrap with" (it may be empty, a single configuration, or infinitely many); and P.strategyP.\mathrm{strategy}P.strategy, one election strategy used by every node. Below, E(x)E(x)E(x) abbreviates P.eligible(x)=trueP.\mathrm{eligible}(x) = \mathrm{true}P.eligible(x)=true ("xxx is eligible").

Declaration 3: Params.dn

P.dn(n)P.\mathrm{dn}(n)P.dn(n) is the discovery node (n, P.eligible(n))(n,\ P.\mathrm{eligible}(n))(n, P.eligible(n)).

Declaration 4: Params.InitCompatible

P.InitCompatibleP.\mathrm{InitCompatible}P.InitCompatible is the proposition: for all configurations X,YX, YX,Y with P.initConfs(X)P.\mathrm{initConfs}(X)P.initConfs(X) and P.initConfs(Y)P.\mathrm{initConfs}(Y)P.initConfs(Y), and all lists q1,q2q_1, q_2q1​,q2​ of node ids all of whose members are eligible,

X.hasQuorum(q1)∧Y.hasQuorum(q2)  ⇒  ∃x, x∈q1∧x∈q2.X.\mathrm{hasQuorum}(q_1) \wedge Y.\mathrm{hasQuorum}(q_2) \;\Rightarrow\; \exists x,\ x \in q_1 \wedge x \in q_2 .X.hasQuorum(q1​)∧Y.hasQuorum(q2​)⇒∃x, x∈q1​∧x∈q2​.

X=YX = YX=Y is included, but for X=YX = YX=Y the implication holds automatically (two sets of members of XXX, each of more than half its size, intersect), so the condition constrains only pairs of distinct bootstrap configurations. It holds trivially when P.initConfsP.\mathrm{initConfs}P.initConfs has at most one element. A configuration with no eligible member has no eligible quorum and so imposes nothing. The docstring ("votes of cluster-manager-eligible nodes that form a quorum of one bootstrap configuration share a voter with votes that form a quorum of another") matches. This condition is not used by the model; it appears only as a hypothesis of theorems.

Declaration 5: BootstrapConfig

For k∈Nk \in \mathbb{N}k∈N, functions resolve,placeholder:N→N\mathrm{resolve}, \mathrm{placeholder} : \mathbb{N} \to \mathbb{N}resolve,placeholder:N→N, matched:N→Bool\mathrm{matched} : \mathbb{N} \to \mathrm{Bool}matched:N→Bool and a configuration XXX, BootstrapConfig(k,resolve,placeholder,matched,X)\mathrm{BootstrapConfig}(k, \mathrm{resolve}, \mathrm{placeholder}, \mathrm{matched}, X)BootstrapConfig(k,resolve,placeholder,matched,X) is the conjunction of

  1. for every node id xxx: x∈X.nodeIds  ⟺  ∃i<k, x=(if matched(i) then resolve(i) else placeholder(i))x \in X.\mathrm{nodeIds} \iff \exists i < k,\ x = \big(\text{if } \mathrm{matched}(i) \text{ then } \mathrm{resolve}(i) \text{ else } \mathrm{placeholder}(i)\big)x∈X.nodeIds⟺∃i<k, x=(if matched(i) then resolve(i) else placeholder(i));
  2. 2⋅∣{i<k:matched(i)}∣>k2 \cdot \big|\{ i < k : \mathrm{matched}(i) \}\big| > k2⋅​{i<k:matched(i)}​>k.

So XXX is exactly the set of the kkk contributions (requirement iii contributes resolve(i)\mathrm{resolve}(i)resolve(i) if matched and placeholder(i)\mathrm{placeholder}(i)placeholder(i) otherwise), and strictly more than half of the requirement indices are matched; in particular k≥1k \ge 1k≥1. Left unconstrained: resolve\mathrm{resolve}resolve and placeholder\mathrm{placeholder}placeholder need not be injective and their images need not be disjoint, so XXX may have fewer than kkk members and the matched count need not equal the number of distinct resolved ids; nothing is said about the eligibility of any id; nothing requires the bootstrapping node to be among the resolved ids. This predicate is not referenced by any other declaration of the file; in particular the bootstrap step uses P.initConfsP.\mathrm{initConfs}P.initConfs, and nothing in this file links the two.

Citation check. CBS:176-215 (onFoundPeersUpdated) bootstraps only if nodesMatchingRequirements.size() * 2 > bootstrapRequirements.size(); CBS:259-273 (startBootstrap) forms the configuration from the ids of the matching nodes and "{bootstrap-placeholder}-" + requirement for each unsatisfied requirement; CBS:306-335 (checkRequirements) cancels bootstrapping if a requirement matches several nodes or a node matches several requirements. The Lean predicate matches the counting and the shape of the configuration. The Java code additionally requires the local node to be cluster-manager-eligible and among the matching nodes (CBS:179, 202-209) and guarantees the injectivity that the Lean leaves open; Java's best-effort bootstrap without configured requirements (scheduleUnconfiguredBootstrap, CBS:217-250) is not described by this predicate.

Declaration 6: Cluster

Cluster V is a structure with two fields: W.node:N→W.\mathrm{node} : \mathbb{N} \toW.node:N→ coordination states (one for every natural number), and W.sentW.\mathrm{sent}W.sent, a predicate on messages ("has been sent"). For an arbitrary cluster, W.sentW.\mathrm{sent}W.sent is an arbitrary, possibly infinite, set of messages.

Declaration 7: Cluster.set

W.set(n,cs)W.\mathrm{set}(n, cs)W.set(n,cs) is WWW with node nnn's state replaced by cscscs: its node function maps mmm to cscscs if m=nm = nm=n and to W.node(m)W.\mathrm{node}(m)W.node(m) otherwise; sent\mathrm{sent}sent is unchanged.

Declaration 8: Cluster.send

W.send(m)W.\mathrm{send}(m)W.send(m) is WWW with sent\mathrm{sent}sent replaced by x↦W.sent(x)∨x=mx \mapsto W.\mathrm{sent}(x) \vee x = mx↦W.sent(x)∨x=m; the node states are unchanged.

Declaration 9: Initial

Initial(P,W)\mathrm{Initial}(P, W)Initial(P,W) is the conjunction of

  1. for every node nnn there is a cluster state sss with s.term=0s.\mathrm{term} = 0s.term=0, s.lcc=EMPTYs.\mathrm{lcc} = \mathrm{EMPTY}s.lcc=EMPTY, s.lac=EMPTYs.\mathrm{lac} = \mathrm{EMPTY}s.lac=EMPTY and W.node(n)=init(P.dn(n),0,s)W.\mathrm{node}(n) = \mathrm{init}(P.\mathrm{dn}(n), 0, s)W.node(n)=init(P.dn(n),0,s);
  2. no message has been sent: ∀m, ¬W.sent(m)\forall m,\ \neg W.\mathrm{sent}(m)∀m, ¬W.sent(m).

So every node (eligible or not) has local node P.dn(n)P.\mathrm{dn}(n)P.dn(n), current term 000, an accepted state of term 000 with empty configurations, no votes, started=won=false\mathrm{started} = \mathrm{won} = \mathrm{false}started=won=false, lpv=0\mathrm{lpv} = 0lpv=0 and lpc=EMPTY\mathrm{lpc} = \mathrm{EMPTY}lpc=EMPTY. The state sss may differ from node to node, and its version, metadata version, cluster-manager node, both cluster-UUID flags and payload are unconstrained. The docstring lists only "version, metadata version and payload" as arbitrary; the cluster-manager node and the UUID flags (so a fresh node may have uuidKnown = true, even uuidCommitted = true) are left free as well.

Declaration 10: RestartState

For cluster states sss (the accepted state before the restart) and s′s's′ (after), RestartState(s,s′)\mathrm{RestartState}(s, s')RestartState(s,s′) is the disjunction of

  1. (persisted state) s′.term=s.terms'.\mathrm{term} = s.\mathrm{term}s′.term=s.term, s′.version=s.versions'.\mathrm{version} = s.\mathrm{version}s′.version=s.version, s′.lcc=s.lccs'.\mathrm{lcc} = s.\mathrm{lcc}s′.lcc=s.lcc, s′.lac=s.lacs'.\mathrm{lac} = s.\mathrm{lac}s′.lac=s.lac, s′.uuidKnown=s.uuidKnowns'.\mathrm{uuidKnown} = s.\mathrm{uuidKnown}s′.uuidKnown=s.uuidKnown and s′.uuidCommitted=s.uuidCommitteds'.\mathrm{uuidCommitted} = s.\mathrm{uuidCommitted}s′.uuidCommitted=s.uuidCommitted — the metadata version, the cluster-manager node and the payload of s′s's′ are free;
  2. (remote-store restore) s.term=0s.\mathrm{term} = 0s.term=0, s.lcc=s.lac=EMPTYs.\mathrm{lcc} = s.\mathrm{lac} = \mathrm{EMPTY}s.lcc=s.lac=EMPTY, s.uuidKnown=falses.\mathrm{uuidKnown} = \mathrm{false}s.uuidKnown=false, and s′.term=0s'.\mathrm{term} = 0s′.term=0, s′.lcc=s′.lac=EMPTYs'.\mathrm{lcc} = s'.\mathrm{lac} = \mathrm{EMPTY}s′.lcc=s′.lac=EMPTY — everything else of s′s's′ (version, metadata version, cluster-manager node, UUID flags, payload) is free.

The docstring matches. Citation check. GatewayMetaState.java:164-197 builds the restarted node's state from the on-disk metadata (which carries the coordination metadata — term and both configurations — and the cluster UUID with its committed flag) and the persisted version, then rebuilds the rest (prepareInitialClusterState); this supports branch 1 (the metadata version is also left free in Lean, which only adds behaviours; the module docstring mentions only the payload and the cluster-manager node as rebuilt). The remote-store restore is GatewayMetaState.java:169-188 (the cited 166-185 is off by a few lines): it is attempted when the node is cluster-manager-eligible, remote cluster state is enabled, the locally loaded cluster UUID is unknown, and the remote store knows a last cluster UUID; the restore starts from Metadata.EMPTY_METADATA (GatewayMetaState.java:293-299) and copies back only index metadata, persistent settings, templates, customs and the version (RemoteStoreRestoreService.java:218-267, 279-307), so the coordination metadata stays empty (term 0, empty configurations) while the version is taken from the remote state. Lean's branch 2 has this result but a narrower trigger: Java tests only that the cluster UUID is unknown, whereas Lean also requires the old state to have term 0 and empty configurations. In the Lean model the UUID flags are otherwise unconstrained (bootstrap and client-value states may carry uuidKnown = false at term ≥1\geq 1≥1 or with non-empty configurations), so for such states the Lean restart relation omits a Java restore behaviour; whether such states occur in Java (where bootstrapping generates a UUID) is outside the model.

Declaration 11: Step

Step(P,W,W′)\mathrm{Step}(P, W, W')Step(P,W,W′) is an inductive relation with nine cases. In each case W′W'W′ is WWW with exactly one node's state replaced (via set) and possibly one message added (via send); no case removes a message. Write c=W.node(n)c = W.\mathrm{node}(n)c=W.node(n) for the acting node's state before the step.

  1. bootstrap (node nnn, configuration XXX, cluster state sss, coordination state cs′cs'cs′): if P.initConfs(X)P.\mathrm{initConfs}(X)P.initConfs(X), initialStateContract(c,s)\mathrm{initialStateContract}(c, s)initialStateContract(c,s), s.lcc=X∧s.lac=Xs.\mathrm{lcc} = X \wedge s.\mathrm{lac} = Xs.lcc=X∧s.lac=X, and setInitialState(c,s)\mathrm{setInitialState}(c, s)setInitialState(c,s) succeeds with cs′cs'cs′, then W′=W.set(n,cs′)W' = W.\mathrm{set}(n, cs')W′=W.set(n,cs′). Unfolded: ccc has accepted term 000, empty last committed and last accepted configurations, lpv=0\mathrm{lpv} = 0lpv=0, empty lpc\mathrm{lpc}lpc, has not won and holds no votes; sss has term 000, version c.lavc.\mathrm{lav}c.lav, and both configurations equal to the non-empty bootstrap configuration XXX; cs′cs'cs′ is ccc with accepted state sss (current term and transient fields unchanged, so lpc\mathrm{lpc}lpc stays empty). The metadata version, cluster-manager node, UUID flags and payload of sss are free. Not required: that nnn be eligible, that n∈Xn \in Xn∈X, or any quorum of discovered nodes (Java's setInitialConfiguration, CO:1101-1161, checks all three and throws otherwise). No message is sent. Several nodes may bootstrap, with different configurations.
  2. startJoin (nodes nnn, src\mathit{src}src, term ttt, cs′cs'cs′, join jjj): if E(src)E(\mathit{src})E(src) and handleStartJoin(c,(P.dn(src),t))\mathrm{handleStartJoin}(c, (P.\mathrm{dn}(\mathit{src}), t))handleStartJoin(c,(P.dn(src),t)) succeeds with (cs′,j)(cs', j)(cs′,j), then W′=(W.set(n,cs′)).send(join j)W' = (W.\mathrm{set}(n, cs')).\mathrm{send}(\mathrm{join}\ j)W′=(W.set(n,cs′)).send(join j). Unfolded: t>c.currentTermt > c.\mathrm{currentTerm}t>c.currentTerm; cs′cs'cs′ has current term ttt, lpv=0\mathrm{lpv} = 0lpv=0, lpc=c.lac\mathrm{lpc} = c.\mathrm{lac}lpc=c.lac, started\mathrm{started}started, not won, no votes, same accepted state; j=(c.localNode, P.dn(src), t, c.lat, vomv(c.acc))j = (c.\mathrm{localNode},\ P.\mathrm{dn}(\mathit{src}),\ t,\ c.\mathrm{lat},\ \mathrm{vomv}(c.\mathrm{acc}))j=(c.localNode, P.dn(src), t, c.lat, vomv(c.acc)). Any node, eligible or not, may do this at any time, for any eligible requester (itself included) and any larger term.
  3. join (node nnn, join jjj, cs′cs'cs′, Boolean bbb): if join j\mathrm{join}\ jjoin j has been sent, j.tgt.id=nj.\mathrm{tgt}.\mathrm{id} = nj.tgt.id=n, and handleJoin(P.strategy,c,j)\mathrm{handleJoin}(P.\mathrm{strategy}, c, j)handleJoin(P.strategy,c,j) succeeds with (cs′,b)(cs', b)(cs′,b), then W′=W.set(n,cs′)W' = W.\mathrm{set}(n, cs')W′=W.set(n,cs′). (bbb is unused.)
  4. clientValue (node nnn, cluster state sss, cs′cs'cs′, publish request ppp): if clientValueContract(c,s)\mathrm{clientValueContract}(c, s)clientValueContract(c,s) (i.e. s.lcc=c.lccs.\mathrm{lcc} = c.\mathrm{lcc}s.lcc=c.lcc) and handleClientValue(c,s)\mathrm{handleClientValue}(c, s)handleClientValue(c,s) succeeds with (cs′,p)(cs', p)(cs′,p), then W′=(W.set(n,cs′)).send(PR(n, p.acceptedState, c.lat, c.lav))W' = (W.\mathrm{set}(n, cs')).\mathrm{send}(\mathrm{PR}(n,\ p.\mathrm{acceptedState},\ c.\mathrm{lat},\ c.\mathrm{lav}))W′=(W.set(n,cs′)).send(PR(n, p.acceptedState, c.lat, c.lav)). Since p.acceptedState=sp.\mathrm{acceptedState} = sp.acceptedState=s, the message is PR(n,s,c.lat,c.lav)\mathrm{PR}(n, s, c.\mathrm{lat}, c.\mathrm{lav})PR(n,s,c.lat,c.lav): its ghost parent is the publisher's accepted key at that moment. Unfolded conditions: c.wonc.\mathrm{won}c.won; c.lpv=c.lavc.\mathrm{lpv} = c.\mathrm{lav}c.lpv=c.lav; s.term=c.currentTerms.\mathrm{term} = c.\mathrm{currentTerm}s.term=c.currentTerm; s.version>c.lpvs.\mathrm{version} > c.\mathrm{lpv}s.version>c.lpv; s.lac=c.lacs.\mathrm{lac} = c.\mathrm{lac}s.lac=c.lac or c.lcc=c.lacc.\mathrm{lcc} = c.\mathrm{lac}c.lcc=c.lac; c.joinVotesc.\mathrm{joinVotes}c.joinVotes is a quorum of s.lacs.\mathrm{lac}s.lac; s.lcc=c.lccs.\mathrm{lcc} = c.\mathrm{lcc}s.lcc=c.lcc. The rest of sss is free. cs′cs'cs′ is ccc with lpv:=s.version\mathrm{lpv} := s.\mathrm{version}lpv:=s.version, lpc:=s.lac\mathrm{lpc} := s.\mathrm{lac}lpc:=s.lac, no publish votes.
  5. publish (nodes nnn, src\mathit{src}src, state sss, ptptpt, pvpvpv, cs′cs'cs′, response rrr): if PR(src,s,pt,pv)\mathrm{PR}(\mathit{src}, s, pt, pv)PR(src,s,pt,pv) has been sent and handlePublishRequest(c,s)\mathrm{handlePublishRequest}(c, s)handlePublishRequest(c,s) succeeds with (cs′,r)(cs', r)(cs′,r), then W′=(W.set(n,cs′)).send(RESP(n,src,r))W' = (W.\mathrm{set}(n, cs')).\mathrm{send}(\mathrm{RESP}(n, \mathit{src}, r))W′=(W.set(n,cs′)).send(RESP(n,src,r)). Any node nnn (the publisher itself, an ineligible node, a node never bootstrapped) may handle any sent publish request, any number of times; the ghost parent plays no role; r=(s.term,s.version)r = (s.\mathrm{term}, s.\mathrm{version})r=(s.term,s.version) and cs′cs'cs′ is ccc with accepted state sss.
  6. respond (nodes nnn, src\mathit{src}src, response rrr, cs′cs'cs′, optional apply-commit ooo): if RESP(src,n,r)\mathrm{RESP}(\mathit{src}, n, r)RESP(src,n,r) has been sent (addressed to nnn) and handlePublishResponse(c,P.dn(src),r)\mathrm{handlePublishResponse}(c, P.\mathrm{dn}(\mathit{src}), r)handlePublishResponse(c,P.dn(src),r) succeeds with (cs′,o)(cs', o)(cs′,o), then W′=W.set(n,cs′)W' = W.\mathrm{set}(n, cs')W′=W.set(n,cs′) if ooo is none and W′=(W.set(n,cs′)).send(AC(o))W' = (W.\mathrm{set}(n, cs')).\mathrm{send}(\mathrm{AC}(o))W′=(W.set(n,cs′)).send(AC(o)) if ooo is some apply-commit. The voter added is P.dn(src)P.\mathrm{dn}(\mathit{src})P.dn(src), so an ineligible responder is never counted; the apply-commit, when produced, is (c.localNode,r.term,r.version)(c.\mathrm{localNode}, r.\mathrm{term}, r.\mathrm{version})(c.localNode,r.term,r.version).
  7. commit (node nnn, apply-commit aaa, cs′cs'cs′): if AC(a)\mathrm{AC}(a)AC(a) has been sent and handleCommit(c,a)\mathrm{handleCommit}(c, a)handleCommit(c,a) succeeds with cs′cs'cs′, then W′=W.set(n,cs′)W' = W.\mathrm{set}(n, cs')W′=W.set(n,cs′). Any node may handle any sent apply-commit.
  8. restart (node nnn, state s′s's′): if E(n)E(n)E(n) and RestartState(c.acc,s′)\mathrm{RestartState}(c.\mathrm{acc}, s')RestartState(c.acc,s′), then W′=W.set(n,init(c.localNode,c.currentTerm,s′))W' = W.\mathrm{set}(n, \mathrm{init}(c.\mathrm{localNode}, c.\mathrm{currentTerm}, s'))W′=W.set(n,init(c.localNode,c.currentTerm,s′)): same local node and current term, accepted state s′s's′, transient part reset (lpc=s′.lac\mathrm{lpc} = s'.\mathrm{lac}lpc=s′.lac).
  9. restartAny (node nnn, term ttt, state s′s's′): if ¬E(n)\neg E(n)¬E(n), then W′=W.set(n,init(c.localNode,t,s′))W' = W.\mathrm{set}(n, \mathrm{init}(c.\mathrm{localNode}, t, s'))W′=W.set(n,init(c.localNode,t,s′)), for any ttt (possibly smaller than before) and any s′s's′.

A message's presence in sent\mathrm{sent}sent is the only condition on it, and sent\mathrm{sent}sent never shrinks, so a sent message can be handled any number of times, or never.

Declaration 12: Reachable

Reachable(P,⋅)\mathrm{Reachable}(P, \cdot)Reachable(P,⋅) is the least predicate on clusters that contains every WWW with Initial(P,W)\mathrm{Initial}(P, W)Initial(P,W) and contains W′W'W′ whenever it contains WWW and Step(P,W,W′)\mathrm{Step}(P, W, W')Step(P,W,W′).

Declaration 13: Committed

Committed(W,t,v)  ⟺  ∃σ, W.sent(AC(σ,t,v))\mathrm{Committed}(W, t, v) \iff \exists \sigma,\ W.\mathrm{sent}(\mathrm{AC}(\sigma, t, v))Committed(W,t,v)⟺∃σ, W.sent(AC(σ,t,v)), the source σ\sigmaσ ranging over all discovery nodes. The docstring speaks of "a published state (term, version)", but the definition does not require (t,v)(t, v)(t,v) to be the key of any publication.

Declaration 14: Parent

Parent(W,t,v,t′,v′)  ⟺  ∃ src,s, W.sent(PR(src,s,t,v))∧s.term=t′∧s.version=v′\mathrm{Parent}(W, t, v, t', v') \iff \exists\, \mathit{src}, s,\ W.\mathrm{sent}(\mathrm{PR}(\mathit{src}, s, t, v)) \wedge s.\mathrm{term} = t' \wedge s.\mathrm{version} = v'Parent(W,t,v,t′,v′)⟺∃src,s, W.sent(PR(src,s,t,v))∧s.term=t′∧s.version=v′: some publication of key (t′,v′)(t', v')(t′,v′) has ghost parent (t,v)(t, v)(t,v). A key may have several parents if several publications share its key (excluded by Inv field 20, not by this definition).

Declaration 15: Descends

Descends(W,⋅,⋅,⋅,⋅)\mathrm{Descends}(W, \cdot, \cdot, \cdot, \cdot)Descends(W,⋅,⋅,⋅,⋅) is the least relation on pairs of keys with (refl) Descends(W,t,v,t,v)\mathrm{Descends}(W, t, v, t, v)Descends(W,t,v,t,v) for every (t,v)(t, v)(t,v), and (step) Descends(W,t,v,t′,v′)∧Parent(W,t′,v′,t′′,v′′)⇒Descends(W,t,v,t′′,v′′)\mathrm{Descends}(W, t, v, t', v') \wedge \mathrm{Parent}(W, t', v', t'', v'') \Rightarrow \mathrm{Descends}(W, t, v, t'', v'')Descends(W,t,v,t′,v′)∧Parent(W,t′,v′,t′′,v′′)⇒Descends(W,t,v,t′′,v′′). Writing (t,v)⪯(t′′,v′′)(t, v) \preceq (t'', v'')(t,v)⪯(t′′,v′′) for Descends(W,t,v,t′′,v′′)\mathrm{Descends}(W, t, v, t'', v'')Descends(W,t,v,t′′,v′′) — the first key is the ancestor — this holds iff there is a chain (t,v)=k0,k1,…,km=(t′′,v′′)(t, v) = k_0, k_1, \dots, k_m = (t'', v'')(t,v)=k0​,k1​,…,km​=(t′′,v′′), m≥0m \ge 0m≥0, with Parent(ki,ki+1)\mathrm{Parent}(k_i, k_{i+1})Parent(ki​,ki+1​) for every i<mi < mi<m. The docstring says "descent between published (term, version) pairs", but reflexivity holds for every pair, published or not; a pair that is not the key of a publication has no ancestor but itself. For an arbitrary WWW the relation may have cycles; acyclicity comes only from Inv.

Declaration 16: KeyLE

KeyLE(t,v,t′,v′)  ⟺  t<t′∨(t=t′∧v≤v′)\mathrm{KeyLE}(t, v, t', v') \iff t < t' \vee (t = t' \wedge v \le v')KeyLE(t,v,t′,v′)⟺t<t′∨(t=t′∧v≤v′): the lexicographic order on keys.

Declaration 17: Below

Below(lt,lv,bt,bv)  ⟺  lt<bt∨(lt=bt∧(bt=0∨lv≤bv))\mathrm{Below}(lt, lv, bt, bv) \iff lt < bt \vee \big(lt = bt \wedge (bt = 0 \vee lv \le bv)\big)Below(lt,lv,bt,bv)⟺lt<bt∨(lt=bt∧(bt=0∨lv≤bv)): lexicographic, except that when both terms are 000 the versions are not compared. handleJoin accepts a join jjj at a node ccc (as far as guards 3 and 4 go) iff j.lat<c.lat∨(j.lat=c.lat∧j.lav≤vomv(c.acc))j.\mathrm{lat} < c.\mathrm{lat} \vee (j.\mathrm{lat} = c.\mathrm{lat} \wedge j.\mathrm{lav} \le \mathrm{vomv}(c.\mathrm{acc}))j.lat<c.lat∨(j.lat=c.lat∧j.lav≤vomv(c.acc)); for c.lat≥1c.\mathrm{lat} \ge 1c.lat≥1 this is exactly Below(j.lat,j.lav,c.lat,c.lav)\mathrm{Below}(j.\mathrm{lat}, j.\mathrm{lav}, c.\mathrm{lat}, c.\mathrm{lav})Below(j.lat,j.lav,c.lat,c.lav), and for c.lat=0c.\mathrm{lat} = 0c.lat=0 Below is weaker (it drops the comparison with the metadata version). The docstring says this.

Declaration 18: Published

Published(W,t,v)  ⟺  ∃ src,s,pt,pv, W.sent(PR(src,s,pt,pv))∧s.term=t∧s.version=v\mathrm{Published}(W, t, v) \iff \exists\, \mathit{src}, s, pt, pv,\ W.\mathrm{sent}(\mathrm{PR}(\mathit{src}, s, pt, pv)) \wedge s.\mathrm{term} = t \wedge s.\mathrm{version} = vPublished(W,t,v)⟺∃src,s,pt,pv, W.sent(PR(src,s,pt,pv))∧s.term=t∧s.version=v. It is not used by any other declaration of this file.

Declaration 19: Realizes

For a key (t,v)(t, v)(t,v) and configurations xxx (in the role of a last committed configuration) and yyy (last accepted), Realizes(P,W,t,v,x,y)\mathrm{Realizes}(P, W, t, v, x, y)Realizes(P,W,t,v,x,y) is the disjunction of

  1. t=0∧x=y∧P.initConfs(x)t = 0 \wedge x = y \wedge P.\mathrm{initConfs}(x)t=0∧x=y∧P.initConfs(x) — the version vvv is then unconstrained;
  2. there is a sent PR(src,s,pt,pv)\mathrm{PR}(\mathit{src}, s, pt, pv)PR(src,s,pt,pv) with key (t,v)(t, v)(t,v), y=s.lacy = s.\mathrm{lac}y=s.lac, and either x=s.lccx = s.\mathrm{lcc}x=s.lcc, or x=s.lacx = s.\mathrm{lac}x=s.lac and Committed(W,t,v)\mathrm{Committed}(W, t, v)Committed(W,t,v).

The docstring matches; its last sentence (that eligible bootstrapped nodes realize their own key) is a claim made by Inv field 11, not by this definition.

Declarations 20–22: JoinVoters, BaseVoters, RespVoters

For a list JJJ (or AAA) of node ids:

  • JoinVoters(P,W,L,t,J)\mathrm{JoinVoters}(P, W, L, t, J)JoinVoters(P,W,L,t,J): every x∈Jx \in Jx∈J has E(x)E(x)E(x) and there is a sent join j\mathrm{join}\ jjoin j with j.src.id=xj.\mathrm{src}.\mathrm{id} = xj.src.id=x, j.tgt.id=Lj.\mathrm{tgt}.\mathrm{id} = Lj.tgt.id=L and j.term=tj.\mathrm{term} = tj.term=t.
  • BaseVoters(P,W,L,t,bt,bv,J)\mathrm{BaseVoters}(P, W, L, t, bt, bv, J)BaseVoters(P,W,L,t,bt,bv,J): the same, with in addition Below(j.lat,j.lav,bt,bv)\mathrm{Below}(j.\mathrm{lat}, j.\mathrm{lav}, bt, bv)Below(j.lat,j.lav,bt,bv) for that join.
  • RespVoters(P,W,t,v,A)\mathrm{RespVoters}(P, W, t, v, A)RespVoters(P,W,t,v,A): every x∈Ax \in Ax∈A has E(x)E(x)E(x) and RESP(x,d,(t,v))\mathrm{RESP}(x, d, (t, v))RESP(x,d,(t,v)) has been sent for some ddd — the destination is arbitrary.

All three hold vacuously for the empty list and allow repetitions. Docstrings match.

Declaration 23: ElectionRecord

ElectionRecord(P,W,L,t,bt,bv,x,y,J)  ⟺  bt<t∧Realizes(P,W,bt,bv,x,y)∧BaseVoters(P,W,L,t,bt,bv,J)∧x.hasQuorum(J)∧y.hasQuorum(J)\mathrm{ElectionRecord}(P, W, L, t, bt, bv, x, y, J) \iff bt < t \wedge \mathrm{Realizes}(P, W, bt, bv, x, y) \wedge \mathrm{BaseVoters}(P, W, L, t, bt, bv, J) \wedge x.\mathrm{hasQuorum}(J) \wedge y.\mathrm{hasQuorum}(J)ElectionRecord(P,W,L,t,bt,bv,x,y,J)⟺bt<t∧Realizes(P,W,bt,bv,x,y)∧BaseVoters(P,W,L,t,bt,bv,J)∧x.hasQuorum(J)∧y.hasQuorum(J). The pair (bt,bv)(bt, bv)(bt,bv) is called the base. Since JJJ is a quorum of xxx, both xxx and JJJ are non-empty. Nothing requires LLL to have won, to be eligible (although, under Inv field 12, the target of a sent join is eligible) or to have published, nor the base to be published (it may be a term-0 key). The docstring's second sentence (that a node that has just won, and the first publication of a term, carry a record) is a claim about other notions, not part of the definition.

Declaration 24: Won

Won(P,W,b,t)  ⟺  E(b)∧((W.node(b).won∧W.node(b).currentTerm=t)∨∃ s,pt,pv, W.sent(PR(b,s,pt,pv))∧s.term=t)\mathrm{Won}(P, W, b, t) \iff E(b) \wedge \big( (W.\mathrm{node}(b).\mathrm{won} \wedge W.\mathrm{node}(b).\mathrm{currentTerm} = t) \vee \exists\, s, pt, pv,\ W.\mathrm{sent}(\mathrm{PR}(b, s, pt, pv)) \wedge s.\mathrm{term} = t \big)Won(P,W,b,t)⟺E(b)∧((W.node(b).won∧W.node(b).currentTerm=t)∨∃s,pt,pv, W.sent(PR(b,s,pt,pv))∧s.term=t). A node that has published in term ttt satisfies Won(b,t)\mathrm{Won}(b, t)Won(b,t) forever, whatever its later state. The docstring matches.

Declaration 25: Inv

Inv(P,W)\mathrm{Inv}(P, W)Inv(P,W) is a structure of 30 propositional fields, i.e. their conjunction. Notation: for a node nnn let cn=W.node(n)c_n = W.\mathrm{node}(n)cn​=W.node(n) and write ln(n)=cn.localNode\mathrm{ln}(n) = c_n.\mathrm{localNode}ln(n)=cn​.localNode, T(n)=cn.currentTermT(n) = c_n.\mathrm{currentTerm}T(n)=cn​.currentTerm, lat(n),lav(n),lcc(n),lac(n)\mathrm{lat}(n), \mathrm{lav}(n), \mathrm{lcc}(n), \mathrm{lac}(n)lat(n),lav(n),lcc(n),lac(n) for cn.lat,cn.lav,cn.lcc,cn.lacc_n.\mathrm{lat}, c_n.\mathrm{lav}, c_n.\mathrm{lcc}, c_n.\mathrm{lac}cn​.lat,cn​.lav,cn​.lcc,cn​.lac, won(n)\mathrm{won}(n)won(n), started(n)\mathrm{started}(n)started(n), lpv(n)\mathrm{lpv}(n)lpv(n), lpc(n)\mathrm{lpc}(n)lpc(n), and JV(n)\mathrm{JV}(n)JV(n), PV(n)\mathrm{PV}(n)PV(n) for the node-id lists of cnc_ncn​'s join and publish votes; "sent" means in W.sentW.\mathrm{sent}W.sent; node variables range over all of N\mathbb{N}N.

Every node nnn:

  1. localNode_eq: ln(n)=P.dn(n)\mathrm{ln}(n) = P.\mathrm{dn}(n)ln(n)=P.dn(n).
  2. idle_of_not_won (N4): ¬won(n)⇒lpv(n)=0∧PV(n)=[ ]\neg\mathrm{won}(n) \Rightarrow \mathrm{lpv}(n) = 0 \wedge \mathrm{PV}(n) = [\,]¬won(n)⇒lpv(n)=0∧PV(n)=[]. The docstring's "has published nothing in its term" is stronger than the term, which constrains only the local variables: a node that published in its term and then restarted has lpv=0\mathrm{lpv} = 0lpv=0 although its publication is in sent\mathrm{sent}sent.
  3. won_started (N2): won(n)⇒started(n)\mathrm{won}(n) \Rightarrow \mathrm{started}(n)won(n)⇒started(n).
  4. votes_started (N6): JV(n)≠[ ]⇒started(n)\mathrm{JV}(n) \neq [\,] \Rightarrow \mathrm{started}(n)JV(n)=[]⇒started(n).
  5. started_term_pos (N10): started(n)⇒T(n)≥1\mathrm{started}(n) \Rightarrow T(n) \ge 1started(n)⇒T(n)≥1.
  6. won_quorum (N3): won(n)⇒JV(n)\mathrm{won}(n) \Rightarrow \mathrm{JV}(n)won(n)⇒JV(n) is a quorum of lcc(n)\mathrm{lcc}(n)lcc(n) and a quorum of lac(n)\mathrm{lac}(n)lac(n).
  7. not_won_no_quorum (N3r): ¬won(n)⇒¬(JV(n)\neg\mathrm{won}(n) \Rightarrow \neg\big(\mathrm{JV}(n)¬won(n)⇒¬(JV(n) is a quorum of lcc(n)\mathrm{lcc}(n)lcc(n) and of lac(n))\mathrm{lac}(n)\big)lac(n)). The docstring calls this "the reverse half of invariant()". Java's invariant() asserts electionWon == isElectionQuorum(joinVotes), whose reverse half also includes the strategy's additional constraint; the field omits it and is therefore stronger, coinciding with Java's reverse half only when the strategy's constraint is always true (for instance the default strategy). Inv never mentions P.strategyP.\mathrm{strategy}P.strategy.
  8. joinVotes_sent (N8): for every m∈JV(n)m \in \mathrm{JV}(n)m∈JV(n): E(m)E(m)E(m), and some sent join j\mathrm{join}\ jjoin j has j.src.id=mj.\mathrm{src}.\mathrm{id} = mj.src.id=m, j.tgt.id=nj.\mathrm{tgt}.\mathrm{id} = nj.tgt.id=n, j.term=T(n)j.\mathrm{term} = T(n)j.term=T(n) and Below(j.lat,j.lav,lat(n),lav(n))\mathrm{Below}(j.\mathrm{lat}, j.\mathrm{lav}, \mathrm{lat}(n), \mathrm{lav}(n))Below(j.lat,j.lav,lat(n),lav(n)).
  9. publishVotes_sent (N9): for every m∈PV(n)m \in \mathrm{PV}(n)m∈PV(n): E(m)E(m)E(m) and RESP(m,n,(T(n),lpv(n)))\mathrm{RESP}(m, n, (T(n), \mathrm{lpv}(n)))RESP(m,n,(T(n),lpv(n))) has been sent.

Every eligible node nnn:

  1. term_le (N1): E(n)⇒lat(n)≤T(n)E(n) \Rightarrow \mathrm{lat}(n) \le T(n)E(n)⇒lat(n)≤T(n).
  2. accepted_realizes (N7): E(n)⇒(lat(n)=0∧lcc(n)=EMPTY∧lac(n)=EMPTY)∨Realizes(lat(n),lav(n),lcc(n),lac(n))E(n) \Rightarrow \big(\mathrm{lat}(n) = 0 \wedge \mathrm{lcc}(n) = \mathrm{EMPTY} \wedge \mathrm{lac}(n) = \mathrm{EMPTY}\big) \vee \mathrm{Realizes}(\mathrm{lat}(n), \mathrm{lav}(n), \mathrm{lcc}(n), \mathrm{lac}(n))E(n)⇒(lat(n)=0∧lcc(n)=EMPTY∧lac(n)=EMPTY)∨Realizes(lat(n),lav(n),lcc(n),lac(n)).

Joins and publish responses:

  1. join_wf: every sent join j\mathrm{join}\ jjoin j has j.src=P.dn(j.src.id)j.\mathrm{src} = P.\mathrm{dn}(j.\mathrm{src}.\mathrm{id})j.src=P.dn(j.src.id) and E(j.tgt.id)E(j.\mathrm{tgt}.\mathrm{id})E(j.tgt.id).
  2. join_term_le (J1): every sent join j\mathrm{join}\ jjoin j with E(j.src.id)E(j.\mathrm{src}.\mathrm{id})E(j.src.id) has j.term≤T(j.src.id)j.\mathrm{term} \le T(j.\mathrm{src}.\mathrm{id})j.term≤T(j.src.id).
  3. join_unique (J2): any two sent joins j,j′j, j'j,j′ with E(j.src.id)E(j.\mathrm{src}.\mathrm{id})E(j.src.id), j.src.id=j′.src.idj.\mathrm{src}.\mathrm{id} = j'.\mathrm{src}.\mathrm{id}j.src.id=j′.src.id and j.term=j′.termj.\mathrm{term} = j'.\mathrm{term}j.term=j′.term are equal (all five fields, in particular the same target).
  4. join_after_response (J3): for every sent join j\mathrm{join}\ jjoin j and sent RESP(a,d,(t,v))\mathrm{RESP}(a, d, (t, v))RESP(a,d,(t,v)) with j.src.id=aj.\mathrm{src}.\mathrm{id} = aj.src.id=a, E(a)E(a)E(a) and t<j.termt < j.\mathrm{term}t<j.term: KeyLE(t,v,j.lat,j.lav)\mathrm{KeyLE}(t, v, j.\mathrm{lat}, j.\mathrm{lav})KeyLE(t,v,j.lat,j.lav).
  5. response_le (R1): for every sent RESP(a,d,(t,v))\mathrm{RESP}(a, d, (t, v))RESP(a,d,(t,v)) with E(a)E(a)E(a): t≤T(a)t \le T(a)t≤T(a) and KeyLE(t,v,lat(a),lav(a))\mathrm{KeyLE}(t, v, \mathrm{lat}(a), \mathrm{lav}(a))KeyLE(t,v,lat(a),lav(a)).
  6. response_published (R2): for every sent RESP(a,d,(t,v))\mathrm{RESP}(a, d, (t, v))RESP(a,d,(t,v)) (no eligibility condition) there is a sent PR(d,s,pt,pv)\mathrm{PR}(d, s, pt, pv)PR(d,s,pt,pv) from ddd with key (t,v)(t, v)(t,v).

Publications (for every sent PR(src,s,pt,pv)\mathrm{PR}(\mathit{src}, s, pt, pv)PR(src,s,pt,pv)):

  1. pub_wf (P1): E(src)E(\mathit{src})E(src), s.term≥1s.\mathrm{term} \ge 1s.term≥1, pt≤s.termpt \le s.\mathrm{term}pt≤s.term, pv<s.versionpv < s.\mathrm{version}pv<s.version, and pt=0⇒P.initConfs(s.lcc)pt = 0 \Rightarrow P.\mathrm{initConfs}(s.\mathrm{lcc})pt=0⇒P.initConfs(s.lcc).
  2. pub_parent (P1, P5): if pt≥1pt \ge 1pt≥1, there is a sent PR(src′,s′,pt′,pv′)\mathrm{PR}(\mathit{src}', s', pt', pv')PR(src′,s′,pt′,pv′) with key (pt,pv)(pt, pv)(pt,pv) such that (a) s.lcc=s′.lccs.\mathrm{lcc} = s'.\mathrm{lcc}s.lcc=s′.lcc, or (s.lcc=s′.lacs.\mathrm{lcc} = s'.\mathrm{lac}s.lcc=s′.lac and Committed(pt,pv)\mathrm{Committed}(pt, pv)Committed(pt,pv)); and (b) s.lac≠s′.lac⇒s.lcc=s′.lacs.\mathrm{lac} \neq s'.\mathrm{lac} \Rightarrow s.\mathrm{lcc} = s'.\mathrm{lac}s.lac=s′.lac⇒s.lcc=s′.lac.
  3. pub_unique (P2): any two sent publications with the same key are the same message: same source, same cluster state (all nine fields), same parent.
  4. pub_rooted: ∃v0∈Z, (0,v0)⪯(s.term,s.version)\exists v_0 \in \mathbb{Z},\ (0, v_0) \preceq (s.\mathrm{term}, s.\mathrm{version})∃v0​∈Z, (0,v0​)⪯(s.term,s.version). (The docstring's gloss "the chain of its ancestors is finite" is an interpretation; the term asserts a finite parent chain from some term-0 key.)
  5. pub_same_term (P4): for every other sent PR(src′,s′,pt′,pv′)\mathrm{PR}(\mathit{src}', s', pt', pv')PR(src′,s′,pt′,pv′) with s′.term=s.terms'.\mathrm{term} = s.\mathrm{term}s′.term=s.term: (s.term,s.version)⪯(s′.term,s′.version)(s.\mathrm{term}, s.\mathrm{version}) \preceq (s'.\mathrm{term}, s'.\mathrm{version})(s.term,s.version)⪯(s′.term,s′.version) or the converse.
  6. pub_voters (P6): there is a list JJJ with JoinVoters(src,s.term,J)\mathrm{JoinVoters}(\mathit{src}, s.\mathrm{term}, J)JoinVoters(src,s.term,J) that is a quorum of s.lccs.\mathrm{lcc}s.lcc and of s.lacs.\mathrm{lac}s.lac.
  7. pub_election (P7): if pt<s.termpt < s.\mathrm{term}pt<s.term, there are a configuration yyy and a list JJJ with ElectionRecord(src,s.term,pt,pv,s.lcc,y,J)\mathrm{ElectionRecord}(\mathit{src}, s.\mathrm{term}, pt, pv, s.\mathrm{lcc}, y, J)ElectionRecord(src,s.term,pt,pv,s.lcc,y,J).

Commits:

  1. commit_quorum (C1, D1): for every sent AC(σ,t,v)\mathrm{AC}(\sigma, t, v)AC(σ,t,v) there are a sent PR(src,s,pt,pv)\mathrm{PR}(\mathit{src}, s, pt, pv)PR(src,s,pt,pv) with key (t,v)(t, v)(t,v) and a list AAA with RespVoters(t,v,A)\mathrm{RespVoters}(t, v, A)RespVoters(t,v,A), AAA a quorum of s.lacs.\mathrm{lac}s.lac, and either AAA a quorum of s.lccs.\mathrm{lcc}s.lcc, or (Committed(pt,pv)\mathrm{Committed}(pt, pv)Committed(pt,pv) and some sent PR(src′,s′,pt′,pv′)\mathrm{PR}(\mathit{src}', s', pt', pv')PR(src′,s′,pt′,pv′) with key (pt,pv)(pt, pv)(pt,pv) has s′.lac=s.lacs'.\mathrm{lac} = s.\mathrm{lac}s′.lac=s.lac).

Leaders:

  1. won_unique (L1): Won(a,t)∧Won(b,t)⇒a=b\mathrm{Won}(a, t) \wedge \mathrm{Won}(b, t) \Rightarrow a = bWon(a,t)∧Won(b,t)⇒a=b.
  2. pub_source_term (L2): for every sent PR(src,s,pt,pv)\mathrm{PR}(\mathit{src}, s, pt, pv)PR(src,s,pt,pv): s.term<T(src)s.\mathrm{term} < T(\mathit{src})s.term<T(src), or s.term=T(src)s.\mathrm{term} = T(\mathit{src})s.term=T(src) and (won(src)\mathrm{won}(\mathit{src})won(src) or ¬started(src)\neg\mathrm{started}(\mathit{src})¬started(src)).
  3. leader_pubs (L3): if won(n)\mathrm{won}(n)won(n), then every sent PR(src,s,pt,pv)\mathrm{PR}(\mathit{src}, s, pt, pv)PR(src,s,pt,pv) with s.term=T(n)s.\mathrm{term} = T(n)s.term=T(n) — from any source — has s.version≤lpv(n)s.\mathrm{version} \le \mathrm{lpv}(n)s.version≤lpv(n), (s.term,s.version)⪯(T(n),lpv(n))(s.\mathrm{term}, s.\mathrm{version}) \preceq (T(n), \mathrm{lpv}(n))(s.term,s.version)⪯(T(n),lpv(n)), and JV(n)\mathrm{JV}(n)JV(n) a quorum of s.lccs.\mathrm{lcc}s.lcc and of s.lacs.\mathrm{lac}s.lac. (The docstring says "an elected node's publications of its term"; the term covers all publications of that term.)
  4. leader_inflight (L4): if won(n)\mathrm{won}(n)won(n) and lpv(n)≠lav(n)\mathrm{lpv}(n) \neq \mathrm{lav}(n)lpv(n)=lav(n), there is a state sss with PR(n,s,lat(n),lav(n))\mathrm{PR}(n, s, \mathrm{lat}(n), \mathrm{lav}(n))PR(n,s,lat(n),lav(n)) sent, s.term=T(n)s.\mathrm{term} = T(n)s.term=T(n), s.version=lpv(n)s.\mathrm{version} = \mathrm{lpv}(n)s.version=lpv(n), lpc(n)=s.lac\mathrm{lpc}(n) = s.\mathrm{lac}lpc(n)=s.lac, and either lcc(n)=s.lcc\mathrm{lcc}(n) = s.\mathrm{lcc}lcc(n)=s.lcc, or (lcc(n)=s.lac\mathrm{lcc}(n) = s.\mathrm{lac}lcc(n)=s.lac, Committed(lat(n),lav(n))\mathrm{Committed}(\mathrm{lat}(n), \mathrm{lav}(n))Committed(lat(n),lav(n)) and lac(n)=s.lac\mathrm{lac}(n) = s.\mathrm{lac}lac(n)=s.lac).
  5. leader_settled (L5): if won(n)\mathrm{won}(n)won(n) and lpv(n)=lav(n)\mathrm{lpv}(n) = \mathrm{lav}(n)lpv(n)=lav(n): either (lat(n)=T(n)\mathrm{lat}(n) = T(n)lat(n)=T(n) and lpc(n)=lac(n)\mathrm{lpc}(n) = \mathrm{lac}(n)lpc(n)=lac(n)), or (lat(n)<T(n)\mathrm{lat}(n) < T(n)lat(n)<T(n) and no sent publication has term T(n)T(n)T(n)).

Docstrings of the remaining fields match their terms. Labels: localNode_eq, join_wf and pub_rooted carry none; "R1"/"R2" name both fields 16/17 and the two clauses (a)/(b) of field 19 in its docstring; "P1" names fields 18 and 19. The structure docstring's split — persisted facts for eligible nodes only, transient facts for every node — holds with the nuance that some every-node fields (5–8) mention persisted components, under a transient premise.

Satisfiability. Every Initial cluster satisfies all 30 fields: fields 1, 2, 10 and 11 by direct check, field 7 because EMPTY\mathrm{EMPTY}EMPTY has no quorum, the others vacuously (no message sent, no node won, started or holding votes). So Inv is not contradictory. Its preservation by Step is not part of this file.

The module and section docstrings

  • The network description ("a message, once sent, stays available forever and may be handled any number of times, by any node it is addressed to, or never") matches Step: joins are handled only by their target id, responses only by their destination, publish requests and apply-commits by any node.
  • "Each step is a successful call of one CoordinationState method, its output, if any, being sent" matches; restart/restartAny call the constructor. "The steps cover every call the Coordinator makes … the Coordinator's own guards only reject more" was checked only for the one cited method, CO:1101-1161 (Coordinator.setInitialConfiguration), whose extra guards (eligible local node, local node in the configuration, quorum of discovered nodes) are indeed absent from the Lean step; the bullet attributes it to ClusterBootstrapService, which calls it.
  • "nodes may bootstrap with different configurations (see BootstrapConfig)": the step uses P.initConfsP.\mathrm{initConfs}P.initConfs; BootstrapConfig is not connected to it in this file.
  • The restart bullet matches branch 1 and restartAny; for the remote-store branch see Declaration 10 (narrower trigger than Java's). GatewayMetaState.java:164-197 and the use of LucenePersistedState for cluster-manager nodes (line 200) versus AsyncLucenePersistedState (lines 202-206) or InMemoryPersistedState (line 255) for others match the description.
  • The assumption citing GatewayMetaState.java:232-255 matches: a node started with neither the cluster-manager nor the data role writes term 0 and an empty state to disk.
  • CoordinationStateTestCluster (test/framework, invariant() at lines 331-370) checks one cluster-manager per term and one state per (term, version) over all publish requests, after random runs in which messages are never removed, start-join terms are occasionally random, elected nodes occasionally publish random terms, versions and configurations, and nodes reboot (also toggling the cluster-manager role, and resetting ineligible nodes' state). The docstring's "the first two safety properties" refers to a list not present in this file.
  • Section docstring: "Publications thus form a forest: following parents, versions strictly decrease until a term-0 key" is a consequence of Inv (fields 18, 20, 21), not of the definitions, which allow arbitrary W.sentW.\mathrm{sent}W.sent.
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