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`]. Two rules over the same IDs have quorum intersection exactly when the sum of their
13/// quorum sizes exceeds the number of IDs.
14///
15/// # Examples
16///
17/// ```
18/// use std::collections::BTreeSet;
19/// use std::num::NonZeroU64;
20/// use std::sync::Arc;
21///
22/// use quorum_set::{QuorumIntersection, QuorumSet, ThresholdQuorumSet};
23///
24/// let voters = Arc::new(BTreeSet::from([1, 2, 3, 4, 5]));
25/// let read = ThresholdQuorumSet::new(NonZeroU64::new(2).unwrap(), voters.clone());
26/// let write = ThresholdQuorumSet::new(NonZeroU64::new(4).unwrap(), voters);
27///
28/// let read_accepts_two = read.is_quorum([1, 2].iter());
29/// assert!(read_accepts_two);
30/// let write_accepts_three = write.is_quorum([1, 2, 3].iter());
31/// assert!(!write_accepts_three);
32///
33/// // 2 + 4 > 5, so every read quorum intersects every write quorum.
34/// let intersects = read.intersects_with(&write);
35/// assert_eq!(Some(true), intersects);
36///
37/// let shared = Arc::ptr_eq(read.id_set(), write.id_set());
38/// assert!(shared);
39/// ```
40#[derive(Clone, Debug, PartialEq, Eq)]
41pub struct ThresholdQuorumSet<ID> {
42    ids: Arc<BTreeSet<ID>>,
43    quorum_size: NonZeroU64,
44}
45
46impl<ID> ThresholdQuorumSet<ID> {
47    /// Builds a rule that accepts an ID set holding at least `quorum_size` of `ids`.
48    ///
49    /// `ids` is a [`BTreeSet`], or an [`Arc`] of one to share it with another rule. A
50    /// `quorum_size` above the number of `ids` gives a rule that accepts no set.
51    pub fn new(quorum_size: NonZeroU64, ids: impl Into<Arc<BTreeSet<ID>>>) -> Self {
52        let ids = ids.into();
53        Self { ids, quorum_size }
54    }
55
56    /// Returns the shared ID set. [`QuorumSet::ids()`] yields the same IDs as an iterator.
57    pub fn id_set(&self) -> &Arc<BTreeSet<ID>> {
58        &self.ids
59    }
60
61    /// Returns the number of IDs that an accepted set must hold.
62    pub fn quorum_size(&self) -> u64 {
63        self.quorum_size.get()
64    }
65}
66
67impl<ID> QuorumSet for ThresholdQuorumSet<ID>
68where ID: Ord + Clone
69{
70    type Id = ID;
71    type Iter = btree_set::IntoIter<ID>;
72
73    fn is_quorum<'a, I>(&self, ids: I) -> bool
74    where
75        ID: 'a,
76        I: Iterator<Item = &'a ID> + Clone,
77    {
78        let quorum_size = self.quorum_size();
79        let mut count = 0;
80        for id in self.ids.iter() {
81            if ids.clone().any(|candidate| candidate == id) {
82                count += 1;
83                if count >= quorum_size {
84                    return true;
85                }
86            }
87        }
88        false
89    }
90
91    fn ids(&self) -> Self::Iter {
92        let ids = self.ids.as_ref().clone();
93        ids.into_iter()
94    }
95}
96
97/// Exact quorum intersection for two threshold rules.
98///
99/// A smallest quorum of `self` first takes the IDs that `other` lacks, and then takes shared IDs
100/// only as needed. A smallest quorum of `other` does the same. Two disjoint quorums exist exactly
101/// when the shared IDs are enough for both, so the check is exact and runs in O(n).
102impl<ID> QuorumIntersection<ThresholdQuorumSet<ID>> for ThresholdQuorumSet<ID>
103where ID: Ord + Clone
104{
105    /// Return `Some(true)` when every quorum of `self` intersects every quorum of `other`, and
106    /// `Some(false)` otherwise. This check never returns `None`.
107    ///
108    /// A rule whose `quorum_size` exceeds its number of IDs has no quorum, so it has quorum
109    /// intersection with every rule.
110    fn intersects_with(&self, other: &ThresholdQuorumSet<ID>) -> Option<bool> {
111        let only_self = self.ids.difference(&other.ids).count() as u64;
112        let only_other = other.ids.difference(&self.ids).count() as u64;
113        let shared = self.ids.intersection(&other.ids).count() as u64;
114
115        let need_self = self.quorum_size().saturating_sub(only_self);
116        let need_other = other.quorum_size().saturating_sub(only_other);
117        let need_both = need_self.saturating_add(need_other);
118
119        Some(need_both > shared)
120    }
121}
quorum_set/quorum/threshold_quorum_set.rs

quorum_set/quorum/
threshold_quorum_set.rs
