quorum_set/quorum/
both_quorums.rs

1use std::collections::BTreeSet;
2use std::collections::btree_set;
3
4use crate::quorum::QuorumSet;
5#[cfg(doc)]
6use crate::verify_intersection;
7
8/// A quorum rule that accepts an ID set only when both a read rule and a write rule accept it.
9///
10/// Two read quorums may be disjoint, and so may two write quorums. Every set this rule accepts is
11/// both a read quorum and a write quorum. So when every read quorum intersects every write quorum,
12/// any two accepted sets intersect; [`verify_intersection`] checks that condition. A consensus
13/// election can use this rule, so that two candidates cannot both win in one term.
14///
15/// [`ids()`](QuorumSet::ids) returns the union of the read and write IDs, each ID once.
16#[derive(Clone, Debug)]
17pub struct BothQuorums<R, W> {
18    read: R,
19    write: W,
20}
21
22impl<R, W> BothQuorums<R, W> {
23    /// Builds a rule that accepts an ID set only when both `read` and `write` accept it.
24    pub fn new(read: R, write: W) -> Self {
25        Self { read, write }
26    }
27}
28
29impl<R, W> QuorumSet for BothQuorums<R, W>
30where
31    R: QuorumSet,
32    W: QuorumSet<Id = R::Id>,
33    R::Id: Ord,
34{
35    type Id = R::Id;
36    type Iter = btree_set::IntoIter<R::Id>;
37
38    fn is_quorum<'a, I>(&self, ids: I) -> bool
39    where
40        Self::Id: 'a,
41        I: Iterator<Item = &'a Self::Id> + Clone,
42    {
43        let is_read_quorum = self.read.is_quorum(ids.clone());
44        is_read_quorum && self.write.is_quorum(ids)
45    }
46
47    fn ids(&self) -> Self::Iter {
48        let mut ids = BTreeSet::new();
49        ids.extend(self.read.ids());
50        ids.extend(self.write.ids());
51        ids.into_iter()
52    }
53}
54
55#[cfg(test)]
56mod tests {
57    use std::collections::BTreeSet;
58
59    use maplit::btreeset;
60
61    use super::BothQuorums;
62    use crate::Node;
63    use crate::QuorumTree;
64    use crate::quorum::QuorumSet;
65    use crate::quorum::verify_intersection;
66
67    /// Nodes form a 2x2 grid, `1 2` over `3 4`. A read quorum holds a row and a write quorum holds
68    /// a column, so the read quorums `{1,2}` and `{3,4}` are disjoint.
69    #[test]
70    fn test_grid_rows_and_columns() -> anyhow::Result<()> {
71        let read = QuorumTree::new(1, [
72            Node::Subtree(QuorumTree::new(2, [Node::Id(1), Node::Id(2)])?),
73            Node::Subtree(QuorumTree::new(2, [Node::Id(3), Node::Id(4)])?),
74        ])?;
75        let write = QuorumTree::new(1, [
76            Node::Subtree(QuorumTree::new(2, [Node::Id(1), Node::Id(3)])?),
77            Node::Subtree(QuorumTree::new(2, [Node::Id(2), Node::Id(4)])?),
78        ])?;
79        assert!(!verify_intersection(&read, &read));
80        assert!(verify_intersection(&read, &write));
81
82        let both = BothQuorums::new(read, write);
83
84        let mut accepted = vec![];
85        for mask in 0..16_u64 {
86            let ids = (1..=4).filter(|id| mask & (1 << (id - 1)) != 0);
87            let ids = ids.collect::<BTreeSet<u64>>();
88            let is_quorum = both.is_quorum(ids.iter());
89            if is_quorum {
90                accepted.push(ids);
91            }
92        }
93        let want = vec![
94            btreeset! {1,2,3},
95            btreeset! {1,2,4},
96            btreeset! {1,3,4},
97            btreeset! {2,3,4},
98            btreeset! {1,2,3,4},
99        ];
100        assert_eq!(want, accepted);
101
102        assert!(verify_intersection(&both, &both));
103
104        Ok(())
105    }
106
107    /// The read and write rules may be different types over different IDs.
108    #[test]
109    fn test_ids_are_union_of_read_and_write_ids() -> anyhow::Result<()> {
110        let read = btreeset! {1u64, 2, 3};
111        let write = QuorumTree::new(2, [Node::Id(3), Node::Id(4), Node::Id(5)])?;
112        let both = BothQuorums::new(read, write);
113
114        let ids = both.ids().collect::<Vec<_>>();
115        assert_eq!(vec![1, 2, 3, 4, 5], ids);
116
117        Ok(())
118    }
119}
quorum_set/quorum/both_quorums.rs

quorum_set/quorum/
both_quorums.rs
