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)` and on `None` they
43    /// must take the unconditionally safe path, e.g. bridge through a joint
44    /// config built by [`QuorumBridge`]. [`verify_intersection`] computes the
45    /// exact relation in exponential time.
46    fn intersects_with(&self, other: &Other) -> Option<bool>;
47}
48
49/// Exhaustively check the [`QuorumIntersection`] relation between two quorum
50/// sets.
51///
52/// Returns `true` iff every quorum of `a` intersects every quorum of `b`.
53/// Unlike [`QuorumIntersection::intersects_with`], which may answer `None`,
54/// this check is exact for any two [`QuorumSet`] implementations, e.g. a read
55/// [`QuorumTree`] against a write [`QuorumTree`].
56///
57/// It tests every split of the combined voter IDs `U` into `(S, U ∖ S)`: a
58/// disjoint quorum pair exists iff for some split, `S` is a quorum of `a` and
59/// `U ∖ S` is a quorum of `b`. Quorum sets are upward-closed, so "some quorum
60/// of `b` fits inside `U ∖ S`" is the same as "`U ∖ S` is itself a quorum of
61/// `b`". This argument relies on two [`QuorumSet`] rules: implementations are
62/// upward-closed, and IDs outside [`QuorumSet::ids`] never affect
63/// [`QuorumSet::is_quorum`].
64///
65/// The check runs `2^n` quorum evaluations for `n` distinct IDs. It is meant
66/// for validating small configurations and as a test oracle.
67///
68/// # Panics
69///
70/// Panics if `a` and `b` together track 64 or more distinct IDs.
71///
72/// # Examples
73///
74/// ```
75/// use std::collections::BTreeSet;
76///
77/// use quorum_set::verify_intersection;
78///
79/// let abc = BTreeSet::from([1, 2, 3]);
80/// let de = BTreeSet::from([4, 5]);
81///
82/// // Majorities of one voter set always intersect each other.
83/// assert!(verify_intersection(&abc, &abc));
84/// // Majorities of disjoint voter sets never intersect.
85/// assert!(!verify_intersection(&abc, &de));
86/// ```
87pub fn verify_intersection<A, B>(a: &A, b: &B) -> bool
88where
89    A: QuorumSet,
90    B: QuorumSet<Id = A::Id>,
91    A::Id: Ord,
92{
93    let universe: BTreeSet<A::Id> = a.ids().chain(b.ids()).collect();
94    let universe: Vec<A::Id> = universe.into_iter().collect();
95    let n = universe.len();
96    assert!(
97        n < 64,
98        "verify_intersection enumerates 2^n subsets; {n} distinct ids do not fit a u64 mask"
99    );
100
101    for mask in 0u64..(1u64 << n) {
102        let selected = universe
103            .iter()
104            .enumerate()
105            .filter(move |&(i, _)| mask & (1u64 << i) != 0)
106            .map(|(_, id)| id);
107        let complement = universe
108            .iter()
109            .enumerate()
110            .filter(move |&(i, _)| mask & (1u64 << i) == 0)
111            .map(|(_, id)| id);
112        if a.is_quorum(selected) && b.is_quorum(complement) {
113            return false;
114        }
115    }
116    true
117}
quorum_set/quorum/quorum_intersection.rs

quorum_set/quorum/
quorum_intersection.rs
