quorum_set/quorum/
quorum_intersection.rs

1use std::collections::BTreeSet;
2
3#[cfg(doc)]
4use crate::QuorumTree;
5use crate::quorum::QuorumSet;
6
7/// Relation between quorum sets whose quorums always intersect.
8///
9/// Quorum sets A and B have **quorum intersection**, written `A ~ B`, when:
10/// `∀ qᵢ ∈ A, ∀ qⱼ ∈ B: qᵢ ∩ qⱼ != ø`.
11/// In words, every quorum in A intersects every quorum in B. Consensus
12/// protocols use this relation to make membership changes without losing
13/// overlap between old and new decisions.
14///
15/// The relation is symmetric, and both universal quantifiers are load-bearing:
16/// weakening either one to "some quorum" (∃) breaks safety, because a reader
17/// or a candidate cannot know which quorum is "the right one" — the overlap
18/// must hold for every quorum it may legally assemble. E.g. for write quorums
19/// `{a,b}, {b,c}, {a,c}` and read quorums `{b,c}, {x,y}`: every write quorum
20/// intersects *some* read quorum, yet a read using `{x,y}` observes no
21/// committed write.
22///
23/// In a Raft-style membership change, quorum intersection is one safety
24/// requirement. The protocol also has to prevent an old, smaller candidate
25/// from being elected during the transition.
26pub trait QuorumIntersection<Other>
27where
28    Self: QuorumSet,
29    Other: QuorumSet<Id = Self::Id>,
30{
31    /// Return whether every quorum of this quorum set intersects every quorum
32    /// of the other quorum set.
33    ///
34    /// - `Some(true)`: the check proved that every quorum pair intersects.
35    /// - `Some(false)`: the check proved that some quorum pair is disjoint.
36    /// - `None`: the check proved neither. An implementation may use a condition that is sufficient
37    ///   but not necessary, so failing that condition tells the caller nothing about the true
38    ///   relation.
39    ///
40    /// Callers can act on `Some(true)`. On `Some(false)` and on `None` they
41    /// must take the unconditionally safe path, e.g. bridge through a joint
42    /// config built by [`QuorumBridge`]. [`verify_intersection`] computes the
43    /// exact relation in exponential time.
44    fn intersects_with(&self, other: &Other) -> Option<bool>;
45}
46
47/// Builds an intermediate quorum set that has [`QuorumIntersection`] with both
48/// the source and the target quorum set.
49pub trait QuorumBridge<Other>
50where
51    Self: QuorumSet,
52    Other: QuorumSet<Id = Self::Id>,
53{
54    /// Build a quorum set `X` so that `self ~ X ~ other`, where `~` is the
55    /// [`QuorumIntersection`] relation.
56    ///
57    /// Then `X` is the intermediate quorum set when changing membership from
58    /// `self` to `other`.
59    ///
60    /// E.g.(`cᵢcⱼ` is a joint of `cᵢ` and `cⱼ`):
61    /// - `c₁.bridge_to(c₁)`   returns `c₁`
62    /// - `c₁.bridge_to(c₂)`   returns `c₁c₂`
63    /// - `c₁c₂.bridge_to(c₂)` returns `c₂`
64    /// - `c₁c₂.bridge_to(c₁)` returns `c₁`
65    /// - `c₁c₂.bridge_to(c₃)` returns `c₂c₃`
66    fn bridge_to(&self, other: Other) -> Self;
67}
68
69/// Exhaustively check the [`QuorumIntersection`] relation between two quorum
70/// sets.
71///
72/// Returns `true` iff every quorum of `a` intersects every quorum of `b`.
73/// Unlike [`QuorumIntersection::intersects_with`], which may answer `None`,
74/// this check is exact for any two [`QuorumSet`] implementations, e.g. a read
75/// [`QuorumTree`] against a write [`QuorumTree`].
76///
77/// It tests every split of the combined voter IDs `U` into `(S, U ∖ S)`: a
78/// disjoint quorum pair exists iff for some split, `S` is a quorum of `a` and
79/// `U ∖ S` is a quorum of `b`. Quorum sets are upward-closed, so "some quorum
80/// of `b` fits inside `U ∖ S`" is the same as "`U ∖ S` is itself a quorum of
81/// `b`". This argument relies on two [`QuorumSet`] rules: implementations are
82/// upward-closed, and IDs outside [`QuorumSet::ids`] never affect
83/// [`QuorumSet::is_quorum`].
84///
85/// The check runs `2^n` quorum evaluations for `n` distinct IDs. It is meant
86/// for validating small configurations and as a test oracle.
87///
88/// # Panics
89///
90/// Panics if `a` and `b` together track 64 or more distinct IDs.
91///
92/// # Examples
93///
94/// ```
95/// use std::collections::BTreeSet;
96///
97/// use quorum_set::verify_intersection;
98///
99/// let abc = BTreeSet::from([1, 2, 3]);
100/// let de = BTreeSet::from([4, 5]);
101///
102/// // Majorities of one voter set always intersect each other.
103/// assert!(verify_intersection(&abc, &abc));
104/// // Majorities of disjoint voter sets never intersect.
105/// assert!(!verify_intersection(&abc, &de));
106/// ```
107pub fn verify_intersection<A, B>(a: &A, b: &B) -> bool
108where
109    A: QuorumSet,
110    B: QuorumSet<Id = A::Id>,
111    A::Id: Ord,
112{
113    let universe: BTreeSet<A::Id> = a.ids().chain(b.ids()).collect();
114    let universe: Vec<A::Id> = universe.into_iter().collect();
115    let n = universe.len();
116    assert!(
117        n < 64,
118        "verify_intersection enumerates 2^n subsets; {n} distinct ids do not fit a u64 mask"
119    );
120
121    for mask in 0u64..(1u64 << n) {
122        let selected = universe
123            .iter()
124            .enumerate()
125            .filter(move |&(i, _)| mask & (1u64 << i) != 0)
126            .map(|(_, id)| id);
127        let complement = universe
128            .iter()
129            .enumerate()
130            .filter(move |&(i, _)| mask & (1u64 << i) == 0)
131            .map(|(_, id)| id);
132        if a.is_quorum(selected) && b.is_quorum(complement) {
133            return false;
134        }
135    }
136    true
137}
quorum_set/quorum/quorum_intersection.rs

quorum_set/quorum/
quorum_intersection.rs
