quorum_set/quorum/threshold_quorum_set.rs
1use std::collections::BTreeSet;
2use std::collections::btree_set;
3use std::num::NonZeroU64;
4use std::sync::Arc;
5
6use crate::quorum::QuorumIntersection;
7use crate::quorum::QuorumSet;
8
9/// A quorum rule that accepts an ID set holding at least `quorum_size` of its IDs.
10///
11/// A read rule and a write rule over the same voters can share one ID set: build both from one
12/// [`Arc`], or build the read rule from the write rule with [`dual()`](Self::dual). Two rules over
13/// the same IDs have quorum intersection exactly when the sum of their quorum sizes exceeds the
14/// number of IDs.
15///
16/// # Examples
17///
18/// ```
19/// use std::collections::BTreeSet;
20/// use std::num::NonZeroU64;
21/// use std::sync::Arc;
22///
23/// use quorum_set::{QuorumIntersection, QuorumSet, ThresholdQuorumSet};
24///
25/// let voters = Arc::new(BTreeSet::from([1, 2, 3, 4, 5]));
26/// let read = ThresholdQuorumSet::new(NonZeroU64::new(2).unwrap(), voters.clone());
27/// let write = ThresholdQuorumSet::new(NonZeroU64::new(4).unwrap(), voters);
28///
29/// let read_accepts_two = read.is_quorum([1, 2].iter());
30/// assert!(read_accepts_two);
31/// let write_accepts_three = write.is_quorum([1, 2, 3].iter());
32/// assert!(!write_accepts_three);
33///
34/// // 2 + 4 > 5, so every read quorum intersects every write quorum.
35/// let intersects = read.intersects_with(&write);
36/// assert_eq!(Some(true), intersects);
37///
38/// let shared = Arc::ptr_eq(read.id_set(), write.id_set());
39/// assert!(shared);
40/// ```
41#[derive(Clone, Debug, PartialEq, Eq)]
42pub struct ThresholdQuorumSet<ID> {
43 ids: Arc<BTreeSet<ID>>,
44 quorum_size: NonZeroU64,
45}
46
47impl<ID> ThresholdQuorumSet<ID> {
48 /// Builds a rule that accepts an ID set holding at least `quorum_size` of `ids`.
49 ///
50 /// `ids` is a [`BTreeSet`], or an [`Arc`] of one to share it with another rule. A
51 /// `quorum_size` above the number of `ids` gives a rule that accepts no set.
52 pub fn new(quorum_size: NonZeroU64, ids: impl Into<Arc<BTreeSet<ID>>>) -> Self {
53 let ids = ids.into();
54 Self { ids, quorum_size }
55 }
56
57 /// Returns the shared ID set. [`QuorumSet::ids()`] yields the same IDs as an iterator.
58 pub fn id_set(&self) -> &Arc<BTreeSet<ID>> {
59 &self.ids
60 }
61
62 /// Returns the number of IDs that an accepted set must hold.
63 pub fn quorum_size(&self) -> u64 {
64 self.quorum_size.get()
65 }
66
67 /// Returns the rule over the same IDs that accepts exactly the sets that meet every quorum of
68 /// `self`. It shares the [`Arc`] of IDs with `self`.
69 ///
70 /// A set meets every quorum of a rule that needs `quorum_size` of `n` IDs exactly when it holds
71 /// at least `n + 1 - quorum_size` of them, so the dual needs that many. It is the threshold
72 /// rule over these IDs with the smallest quorum size that intersects `self`, so it fits as the
73 /// read rule of a write rule `self`. The dual of the dual is `self` again.
74 ///
75 /// Returns `None` when `quorum_size` exceeds the number of IDs. Such a rule has no quorum, so
76 /// every set meets all of its quorums, the empty set included, and no `ThresholdQuorumSet`
77 /// accepts the empty set.
78 ///
79 /// # Examples
80 ///
81 /// ```
82 /// use std::collections::BTreeSet;
83 /// use std::num::NonZeroU64;
84 /// use std::sync::Arc;
85 ///
86 /// use quorum_set::{QuorumIntersection, ThresholdQuorumSet};
87 ///
88 /// // A write quorum needs 2 of 5 IDs, so a read quorum needs 4 of them.
89 /// let two = NonZeroU64::new(2).unwrap();
90 /// let write = ThresholdQuorumSet::new(two, BTreeSet::from([1, 2, 3, 4, 5]));
91 /// let read = write.dual().unwrap();
92 /// assert_eq!(4, read.quorum_size());
93 ///
94 /// let shared = Arc::ptr_eq(write.id_set(), read.id_set());
95 /// assert!(shared);
96 /// let intersects = read.intersects_with(&write);
97 /// assert_eq!(Some(true), intersects);
98 /// ```
99 pub fn dual(&self) -> Option<Self> {
100 let id_count = self.ids.len() as u64;
101 let spare = id_count.checked_sub(self.quorum_size())?;
102 let quorum_size = NonZeroU64::MIN.saturating_add(spare);
103 let ids = Arc::clone(&self.ids);
104 Some(Self { ids, quorum_size })
105 }
106}
107
108impl<ID> QuorumSet for ThresholdQuorumSet<ID>
109where ID: Ord + Clone
110{
111 type Id = ID;
112 type Iter = btree_set::IntoIter<ID>;
113
114 fn is_quorum<'a, I>(&self, ids: I) -> bool
115 where
116 ID: 'a,
117 I: Iterator<Item = &'a ID> + Clone,
118 {
119 let quorum_size = self.quorum_size();
120 let mut count = 0;
121 for id in self.ids.iter() {
122 if ids.clone().any(|candidate| candidate == id) {
123 count += 1;
124 if count >= quorum_size {
125 return true;
126 }
127 }
128 }
129 false
130 }
131
132 fn ids(&self) -> Self::Iter {
133 let ids = self.ids.as_ref().clone();
134 ids.into_iter()
135 }
136}
137
138/// Exact quorum intersection for two threshold rules.
139///
140/// A smallest quorum of `self` first takes the IDs that `other` lacks, and then takes shared IDs
141/// only as needed. A smallest quorum of `other` does the same. Two disjoint quorums exist exactly
142/// when the shared IDs are enough for both, so the check is exact and runs in O(n).
143impl<ID> QuorumIntersection<ThresholdQuorumSet<ID>> for ThresholdQuorumSet<ID>
144where ID: Ord + Clone
145{
146 /// Return `Some(true)` when every quorum of `self` intersects every quorum of `other`, and
147 /// `Some(false)` otherwise. This check never returns `None`.
148 ///
149 /// A rule whose `quorum_size` exceeds its number of IDs has no quorum, so it has quorum
150 /// intersection with every rule.
151 fn intersects_with(&self, other: &ThresholdQuorumSet<ID>) -> Option<bool> {
152 let only_self = self.ids.difference(&other.ids).count() as u64;
153 let only_other = other.ids.difference(&self.ids).count() as u64;
154 let shared = self.ids.intersection(&other.ids).count() as u64;
155
156 let need_self = self.quorum_size().saturating_sub(only_self);
157 let need_other = other.quorum_size().saturating_sub(only_other);
158 let need_both = need_self.saturating_add(need_other);
159
160 Some(need_both > shared)
161 }
162}