quorum_set/quorum/
explicit_quorum_set.rs

1use std::collections::BTreeSet;
2use std::collections::btree_set;
3
4use crate::quorum::QuorumIntersection;
5use crate::quorum::QuorumSet;
6
7/// A quorum rule that accepts an ID set holding every ID of one of its listed quorums.
8///
9/// The rule keeps only the minimal quorums. [`new()`](Self::new) sorts the list, drops duplicate
10/// quorums, and drops each quorum that holds another listed quorum, because every set that holds
11/// the larger quorum also holds the smaller one. Two rules that accept the same sets therefore
12/// hold the same list.
13///
14/// Every accepted set holds a listed quorum, so two rules have quorum intersection exactly when
15/// every listed quorum of one meets every listed quorum of the other. The check compares each
16/// pair of listed quorums. A rule with no listed quorum accepts no set.
17///
18/// Listing quorums costs memory that grows with the policy. Some policies need exponentially many
19/// minimal quorums: a majority of `n` IDs has `C(n, n/2 + 1)` of them, 126 for 9 IDs and
20/// 6435 for 15.
21///
22/// # Examples
23///
24/// ```
25/// use std::collections::BTreeSet;
26///
27/// use quorum_set::{ExplicitQuorumSet, QuorumIntersection, QuorumSet};
28///
29/// // {1,2,3} holds {1,2}, so the rule keeps only {1,2} and {3,4}.
30/// let quorums = [BTreeSet::from([1, 2, 3]), BTreeSet::from([3, 4]), BTreeSet::from([1, 2])];
31/// let rule = ExplicitQuorumSet::new(quorums).unwrap();
32/// assert_eq!(&[BTreeSet::from([1, 2]), BTreeSet::from([3, 4])], rule.quorums());
33///
34/// let accepts = rule.is_quorum([4, 3, 9].iter());
35/// assert!(accepts);
36/// let accepts = rule.is_quorum([1, 3].iter());
37/// assert!(!accepts);
38///
39/// // {3,4} misses {1,2}.
40/// let intersects = rule.intersects_with(&rule);
41/// assert_eq!(Some(false), intersects);
42/// ```
43#[derive(Clone, Debug, PartialEq, Eq)]
44pub struct ExplicitQuorumSet<ID> {
45    /// The minimal quorums, sorted.
46    quorums: Vec<BTreeSet<ID>>,
47}
48
49impl<ID> ExplicitQuorumSet<ID>
50where ID: Ord + Clone
51{
52    /// Builds a rule that accepts an ID set holding every ID of one of `quorums`.
53    ///
54    /// Returns `None` when a listed quorum is empty: every set holds the empty set, so every set,
55    /// the empty one included, would be a quorum.
56    pub fn new<I>(quorums: I) -> Option<Self>
57    where I: IntoIterator<Item = BTreeSet<ID>> {
58        let mut quorums: Vec<BTreeSet<ID>> = quorums.into_iter().collect();
59        let has_empty_quorum = quorums.iter().any(|quorum| quorum.is_empty());
60        if has_empty_quorum {
61            return None;
62        }
63
64        quorums.sort();
65        quorums.dedup();
66
67        let mut minimal = Vec::new();
68        for quorum in &quorums {
69            let holds_other =
70                quorums.iter().any(|other| other != quorum && other.is_subset(quorum));
71            if holds_other {
72                continue;
73            }
74            minimal.push(quorum.clone());
75        }
76
77        let rule = Self { quorums: minimal };
78        Some(rule)
79    }
80
81    /// Returns the minimal quorums, sorted.
82    pub fn quorums(&self) -> &[BTreeSet<ID>] {
83        &self.quorums
84    }
85
86    /// Returns the first pair of a listed quorum of `self` and a listed quorum of `other` that
87    /// share no ID, in the order of the two lists, or `None` when every pair meets.
88    ///
89    /// Such a pair shows two disjoint quorums, so `None` means the two rules have quorum
90    /// intersection.
91    pub fn disjoint_quorums<'a>(
92        &'a self,
93        other: &'a Self,
94    ) -> Option<(&'a BTreeSet<ID>, &'a BTreeSet<ID>)> {
95        for quorum in &self.quorums {
96            for other_quorum in &other.quorums {
97                if quorum.is_disjoint(other_quorum) {
98                    return Some((quorum, other_quorum));
99                }
100            }
101        }
102        None
103    }
104}
105
106impl<ID> QuorumSet for ExplicitQuorumSet<ID>
107where ID: Ord + Clone
108{
109    type Id = ID;
110    type Iter = btree_set::IntoIter<ID>;
111
112    fn is_quorum<'a, I>(&self, ids: I) -> bool
113    where
114        ID: 'a,
115        I: Iterator<Item = &'a ID> + Clone,
116    {
117        let candidates: BTreeSet<&ID> = ids.collect();
118        for quorum in &self.quorums {
119            let holds_quorum = quorum.iter().all(|id| candidates.contains(id));
120            if holds_quorum {
121                return true;
122            }
123        }
124        false
125    }
126
127    fn ids(&self) -> Self::Iter {
128        let mut ids = BTreeSet::new();
129        for quorum in &self.quorums {
130            ids.extend(quorum.iter().cloned());
131        }
132        ids.into_iter()
133    }
134}
135
136/// Exact quorum intersection for two lists of minimal quorums.
137///
138/// Every quorum of a rule holds one of its listed quorums, and every listed quorum is a quorum.
139/// Two quorums are therefore disjoint only when two listed quorums are, so the check is exact.
140/// It runs in `O(a * b * n)` for `a` and `b` listed quorums of at most `n` IDs.
141impl<ID> QuorumIntersection<ExplicitQuorumSet<ID>> for ExplicitQuorumSet<ID>
142where ID: Ord + Clone
143{
144    /// Return `Some(false)` when a listed quorum of `self` and one of `other` are disjoint, and
145    /// `Some(true)` otherwise. This check never returns `None`.
146    ///
147    /// A rule with no listed quorum has no quorum, so it has quorum intersection with every rule.
148    fn intersects_with(&self, other: &ExplicitQuorumSet<ID>) -> Option<bool> {
149        let disjoint = self.disjoint_quorums(other);
150        Some(disjoint.is_none())
151    }
152}
quorum_set/quorum/explicit_quorum_set.rs

quorum_set/quorum/
explicit_quorum_set.rs
