quorum-set 0.6.0

Quorum sets, hierarchical quorum trees, and quorum-accepted progress tracking for consensus protocols
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162

use maplit::btreeset;

use crate::quorum::Joint;
use crate::quorum::QuorumBridge;
use crate::quorum::QuorumIntersection;
use crate::quorum::QuorumSet;
use crate::quorum::ThresholdQuorumSet;
use crate::quorum::threshold_quorum_set_test::all_subsets;
use crate::quorum::threshold_quorum_set_test::all_thresholds;
use crate::quorum::threshold_quorum_set_test::threshold;
use crate::quorum::verify_intersection;

/// Returns the empty joint, and every joint of one or two rules over subsets of {1,2,3}.
///
/// Three IDs keep the checks over pairs of joints short: four IDs give about 5.5 million pairs.
fn all_joints() -> Vec<Joint<ThresholdQuorumSet<u64>>> {
    let thresholds = all_thresholds(&btreeset! {1, 2, 3});

    let mut joints = vec![Joint::default()];
    for a in &thresholds {
        joints.push(Joint::new([a.clone()]));
        for b in &thresholds {
            joints.push(Joint::new([a.clone(), b.clone()]));
        }
    }
    joints
}

#[test]
fn test_joint_of_thresholds() {
    let old = threshold(2, btreeset! {1, 2, 3});
    let new = threshold(2, btreeset! {2, 3, 4});
    let joint = Joint::new([old, new]);

    let mut accepted = vec![];
    for ids in all_subsets(&btreeset! {1, 2, 3, 4}) {
        let is_quorum = joint.is_quorum(ids.iter());
        if is_quorum {
            accepted.push(ids);
        }
    }

    // The smallest quorums {2,3}, {1,2,4} and {1,3,4} differ in size, so no single threshold rule
    // accepts the same sets.
    let want = vec![
        btreeset! {2, 3},
        btreeset! {1, 2, 3},
        btreeset! {1, 2, 4},
        btreeset! {1, 3, 4},
        btreeset! {2, 3, 4},
        btreeset! {1, 2, 3, 4},
    ];
    assert_eq!(want, accepted);

    let ids = joint.ids().collect::<Vec<_>>();
    assert_eq!(vec![1, 2, 3, 4], ids);
}

#[test]
fn test_empty_joint_accepts_no_set() {
    let empty = Joint::<ThresholdQuorumSet<u64>>::default();

    let empty_input = empty.is_quorum(std::iter::empty());
    assert!(!empty_input);
    let some_ids = empty.is_quorum([1, 2].iter());
    assert!(!some_ids);

    let ids = empty.ids().collect::<Vec<_>>();
    assert_eq!(Vec::<u64>::new(), ids);
}

#[test]
fn test_intersects_with() {
    let r123 = || threshold(2, btreeset! {1, 2, 3});
    let r345 = || threshold(2, btreeset! {3, 4, 5});
    let r789 = || threshold(2, btreeset! {7, 8, 9});

    let j123 = Joint::new([r123()]);
    let j345 = Joint::new([r345()]);
    let j123_345 = Joint::new([r123(), r345()]);
    let j345_789 = Joint::new([r345(), r789()]);

    // Two joints of one rule each get the answer of the rule check: {1,2} and {4,5} are disjoint
    // quorums.
    let uniform = j123.intersects_with(&j345);
    assert_eq!(Some(false), uniform);

    // Other joints answer `Some(true)` when some rule pair intersects, and `None` when no pair
    // does.
    let shared_rule = j123_345.intersects_with(&j345_789);
    assert_eq!(Some(true), shared_rule);
    let no_shared_rule = j123.intersects_with(&j345_789);
    assert_eq!(None, no_shared_rule);
}

#[test]
fn test_intersects_with_agrees_with_verify_intersection() {
    let joints = all_joints();

    // Two joints of at most one rule each always get the exact answer. For other joints,
    // `intersects_with` may answer `None`, but every `Some` answer must match the exact relation.
    for a in &joints {
        for b in &joints {
            let intersects = a.intersects_with(b);
            let at_most_one_rule = a.rules().len() <= 1 && b.rules().len() <= 1;
            if at_most_one_rule {
                let exact = verify_intersection(a, b);
                assert_eq!(Some(exact), intersects, "a: {a:?}, b: {b:?}");
                continue;
            }

            let Some(intersects) = intersects else {
                continue;
            };
            let exact = verify_intersection(a, b);
            assert_eq!(exact, intersects, "a: {a:?}, b: {b:?}");
        }
    }
}

#[test]
fn test_joint_with() {
    let r1 = || threshold(2, btreeset! {1, 2, 3});
    let r2 = || threshold(1, btreeset! {3, 4});
    let r3 = || threshold(3, btreeset! {4, 5, 6});

    let j12 = Joint::new([r1(), r2()]);
    let j3 = Joint::new([r3()]);

    let joint = j12.joint_with(j3.clone());
    let want = Joint::new([r1(), r2(), r3()]);
    assert_eq!(want, joint);

    // An empty joint has no quorum, so a joint with it has no quorum either.
    let empty = Joint::default();
    let with_empty = j12.joint_with(empty.clone());
    assert_eq!(empty, with_empty);
    let from_empty = empty.joint_with(j3);
    assert_eq!(empty, from_empty);
}

#[test]
fn test_joint_with_accepts_quorums_of_both_sides() {
    let joints = all_joints();
    let id_sets = all_subsets(&btreeset! {1, 2, 3});

    for current in &joints {
        for goal in &joints {
            let joint = current.joint_with(goal.clone());
            for ids in &id_sets {
                let in_current = current.is_quorum(ids.iter());
                let in_goal = goal.is_quorum(ids.iter());
                let in_both = in_current && in_goal;
                let in_joint = joint.is_quorum(ids.iter());
                assert_eq!(
                    in_both, in_joint,
                    "{current:?} joint with {goal:?} on {ids:?}"
                );
            }
        }
    }
}