Two quorums of one voting configuration share a member
ProvedOpenSearchCoordination.quorum_intersectFor every voting configuration c and lists of node ids a and b: if c.hasQuorum a = true and c.hasQuorum b = true, then some node id x is a member of c (x ∈ c.nodeIds) and occurs in both a and b.
Here c.hasQuorum votes holds when the number of members of c occurring in votes, doubled, exceeds the number of members of c: a strict majority of the configuration. This is the intersection property every safety argument of the protocol rests on: two elections, or an election and a commit, decided by quorums of the same configuration have a voter in common.
import Definitions.Def_OpenSearchCoordination
theorem OpenSearchCoordination.quorum_intersect (c : VotingConfiguration) (a b : List NodeId)
(ha : c.hasQuorum a = true) (hb : c.hasQuorum b = true) :
∃ x, x ∈ c.nodeIds ∧ x ∈ a ∧ x ∈ b := by sorryRead-back
What the Lean code literally says, in plain math · claude-opus-5-5 (independent sub-agent, blind: Lean code + auditor instructions only)
Read-back: OpenSearchCoordination.quorum_intersect
Notions used
Voting configurations. A voting configuration is a list of natural numbers (node ids) together with a proof that the list is strictly increasing. So it has no duplicates and stands for a finite set of naturals.
Quorum test. For a list of naturals:
that is, : strictly more than half of the configuration's ids occur in . Duplicates in and entries of outside do not matter. For the empty configuration the test is always false.
1. Declaration
Binders.
- : a voting configuration;
- : lists of natural numbers (
List NodeId).
Hypotheses, in order.
- : ;
- : .
Conclusion.
If and each contain a strict majority of 's ids, then some id of lies in both.
2. What is not constrained
- and are arbitrary lists. They may contain ids outside , repeat ids, and need not be related to each other.
- The conclusion asserts one common member. It says nothing about how many there are, nor that the common member is cluster-manager-eligible: no node objects are involved, only ids.
- If is empty, the hypotheses cannot both hold, since no list is a quorum of the empty configuration. The statement is then vacuous, which is the only consistent outcome, because the conclusion would be false.
- For non-empty the hypotheses are satisfiable, for example and . The statement is not vacuous.
- The statement concerns a single configuration. It says nothing about two quorums of different configurations.
3. Plain-language summary
Two vote lists that are each a strict-majority quorum of the same voting configuration share at least one voter that belongs to the configuration. This is the usual quorum-intersection property, stated for one configuration and plain lists of ids.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.