quorum_set/quorum/
weighted_quorum_set.rs

1use std::collections::BTreeMap;
2use std::collections::BTreeSet;
3use std::collections::btree_set;
4
5use crate::quorum::QuorumIntersection;
6use crate::quorum::QuorumSet;
7use crate::quorum::WeightedQuorumSetError;
8
9/// A quorum rule that accepts an ID set whose IDs weigh at least `threshold` together.
10///
11/// Each ID of the rule has a positive weight. A set counts the weight of each of its IDs once,
12/// and an ID that the rule does not weigh adds nothing. A sum that would exceed `u64::MAX` exceeds
13/// every threshold, so [`is_quorum()`](QuorumSet::is_quorum) saturates instead of overflowing. A
14/// `threshold` above the total weight gives a rule that accepts no set.
15///
16/// Two disjoint sets together weigh at most the total weight. So two rules with the same weights
17/// have quorum intersection when their thresholds sum to more than the total weight. This
18/// condition is sufficient but not necessary, because a set adds all of an ID's weight or none of
19/// it. With weights `{1:2, 2:2}`, thresholds 3 and 1 sum to only the total weight 4, yet the only
20/// quorum of threshold 3, `{1,2}`, meets every quorum of threshold 1.
21///
22/// # Examples
23///
24/// ```
25/// use std::collections::BTreeMap;
26///
27/// use quorum_set::{QuorumIntersection, QuorumSet, WeightedQuorumSet};
28///
29/// // ID 1 weighs as much as IDs 2 and 3 together; the total weight is 4.
30/// let weights = BTreeMap::from([(1, 2), (2, 1), (3, 1)]);
31/// let read = WeightedQuorumSet::new(3, weights.clone()).unwrap();
32/// let write = WeightedQuorumSet::new(2, weights).unwrap();
33///
34/// let write_accepts_one = write.is_quorum([1].iter());
35/// assert!(write_accepts_one);
36/// let read_accepts_two_three = read.is_quorum([2, 3].iter());
37/// assert!(!read_accepts_two_three);
38///
39/// // 3 + 2 > 4, so every read quorum intersects every write quorum.
40/// let intersects = read.intersects_with(&write);
41/// assert_eq!(Some(true), intersects);
42/// ```
43#[derive(Clone, Debug, PartialEq, Eq)]
44pub struct WeightedQuorumSet<ID> {
45    weights: BTreeMap<ID, u64>,
46    threshold: u64,
47}
48
49impl<ID> WeightedQuorumSet<ID>
50where ID: Ord + Clone
51{
52    /// Builds a rule that accepts an ID set whose IDs weigh at least `threshold` together, with
53    /// the weight of each ID in `weights`.
54    ///
55    /// # Errors
56    ///
57    /// - [`WeightedQuorumSetError::ZeroWeight`]: the first ID with weight 0, which would never
58    ///   count.
59    /// - [`WeightedQuorumSetError::ZeroThreshold`]: a `threshold` of 0, which would make the empty
60    ///   set a quorum.
61    pub fn new(
62        threshold: u64,
63        weights: BTreeMap<ID, u64>,
64    ) -> Result<Self, WeightedQuorumSetError<ID>> {
65        for (id, weight) in weights.iter() {
66            if *weight == 0 {
67                let id = id.clone();
68                return Err(WeightedQuorumSetError::ZeroWeight { id });
69            }
70        }
71        if threshold == 0 {
72            return Err(WeightedQuorumSetError::ZeroThreshold);
73        }
74
75        let rule = Self { weights, threshold };
76        Ok(rule)
77    }
78
79    /// Returns the weight of each ID. [`QuorumSet::ids()`] yields its IDs.
80    pub fn weights(&self) -> &BTreeMap<ID, u64> {
81        &self.weights
82    }
83
84    /// Returns the weight that an accepted set must reach.
85    pub fn threshold(&self) -> u64 {
86        self.threshold
87    }
88}
89
90impl<ID> QuorumSet for WeightedQuorumSet<ID>
91where ID: Ord + Clone
92{
93    type Id = ID;
94    type Iter = btree_set::IntoIter<ID>;
95
96    fn is_quorum<'a, I>(&self, ids: I) -> bool
97    where
98        ID: 'a,
99        I: Iterator<Item = &'a ID> + Clone,
100    {
101        let threshold = self.threshold();
102        let mut sum = 0u64;
103        for (id, weight) in self.weights.iter() {
104            if ids.clone().any(|candidate| candidate == id) {
105                sum = sum.saturating_add(*weight);
106                if sum >= threshold {
107                    return true;
108                }
109            }
110        }
111        false
112    }
113
114    fn ids(&self) -> Self::Iter {
115        let keys = self.weights.keys();
116        let ids: BTreeSet<ID> = keys.cloned().collect();
117        ids.into_iter()
118    }
119}
120
121/// Sufficient quorum intersection for two weighted rules.
122///
123/// Two disjoint sets together weigh at most the total weight. When two rules hold the same weights
124/// and their thresholds sum to more than the total weight, a quorum of one and a quorum of the
125/// other are therefore never disjoint. The check runs in O(n) for `n` IDs.
126impl<ID> QuorumIntersection<WeightedQuorumSet<ID>> for WeightedQuorumSet<ID>
127where ID: Ord + Clone
128{
129    /// Return `Some(true)` when both rules hold the same weights and their thresholds sum to more
130    /// than the total weight, and `None` otherwise, including for every pair of rules with
131    /// different weights. This check never returns `Some(false)`.
132    ///
133    /// The sums are computed in `u128`, so they never overflow.
134    fn intersects_with(&self, other: &WeightedQuorumSet<ID>) -> Option<bool> {
135        if self.weights != other.weights {
136            return None;
137        }
138
139        let mut total_weight = 0u128;
140        for weight in self.weights.values() {
141            total_weight += u128::from(*weight);
142        }
143        let thresholds = u128::from(self.threshold()) + u128::from(other.threshold());
144
145        if thresholds > total_weight {
146            Some(true)
147        } else {
148            None
149        }
150    }
151}
quorum_set/quorum/weighted_quorum_set.rs

quorum_set/quorum/
weighted_quorum_set.rs
