quorum_set/quorum/
quorum_intersection.rs

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

quorum_set/quorum/
quorum_intersection.rs
