minerva 0.2.0

Causal ordering for distributed systems
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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189

extern crate alloc;

use alloc::vec::Vec;

use super::super::support::{dot, vv};
use crate::metis::{Cut, Dot, DotSet, Stability};

#[test]
fn test_floor_is_gap_free_and_maximal() {
    let mut have = DotSet::new();
    assert!(have.insert(dot(1, 1)));
    assert!(have.insert(dot(1, 2)));
    assert!(have.insert(dot(1, 5)));
    // The floor stops at the first hole; the high water runs to the top dot.
    assert_eq!(have.floor(), vv(&[(1, 2)]));
    assert_eq!(have.high_water(), vv(&[(1, 5)]));
    let holes: Vec<_> = have.holes().collect();
    assert_eq!(holes, [dot(1, 3), dot(1, 4)]);
}

#[test]
fn test_station_summaries_expose_compact_bounds_without_empty_rows() {
    let mut have = DotSet::new();
    for (station, counter) in [(7, 1), (7, 3), (11, 1), (11, 2)] {
        assert!(have.insert(dot(station, counter)));
    }

    assert_eq!(have.station_count(), 2);
    let summaries: Vec<_> = have.stations().collect();
    assert_eq!(
        summaries,
        [
            have.station(7).expect("station seven exists"),
            have.station(11).expect("station eleven exists"),
        ]
    );
    assert_eq!(summaries[0].station(), 7);
    assert_eq!(summaries[0].floor(), 1);
    assert_eq!(summaries[0].high_water(), 3);
    assert_eq!(summaries[0].forward_gap(), 2);
    assert_eq!(summaries[1].forward_gap(), 0);
    assert_eq!(have.station(9), None);
}

#[test]
fn test_out_of_order_arrival_converges() {
    let mut have = DotSet::new();
    assert!(have.insert(dot(1, 3)));
    assert!(have.insert(dot(1, 1)));
    assert!(have.insert(dot(1, 2)));
    // Once every gap fills, the disorder leaves no trace: floor meets high
    // water and the exceptions are empty.
    assert_eq!(have.floor(), vv(&[(1, 3)]));
    assert_eq!(have.high_water(), vv(&[(1, 3)]));
    assert_eq!(have.exceptions_len(), 0);
    assert_eq!(have.holes().count(), 0);
}

#[test]
fn test_dot_zero_is_not_a_dot() {
    // The refusal moved off the door and onto the type (ruling R-91): the
    // non-dot counter zero is unrepresentable, so no `DotSet` call can be
    // offered it. The set that never took it stays the canonical empty set.
    assert!(Dot::from_parts(1, 0).is_err());
    assert!(Dot::try_from((1, 0)).is_err());
    let have = DotSet::new();
    assert_eq!(have, DotSet::new());
}

#[test]
fn test_duplicate_insert_is_idempotent() {
    let mut have = DotSet::new();
    assert!(have.insert(dot(2, 4)));
    let before = have.clone();
    assert!(!have.insert(dot(2, 4)));
    assert_eq!(have, before);
}

#[test]
fn test_hole_fill_absorbs_the_parked_run() {
    let mut have = DotSet::new();
    for counter in [1, 3, 4, 5] {
        assert!(have.insert(dot(1, counter)));
    }
    assert_eq!(have.floor(), vv(&[(1, 1)]));
    assert_eq!(have.exceptions_len(), 3);
    // Filling the one hole folds the whole parked run into the floor: the
    // steady state pays nothing for the disorder that has passed.
    assert!(have.insert(dot(1, 2)));
    assert_eq!(have.floor(), vv(&[(1, 5)]));
    assert_eq!(have.exceptions_len(), 0);
}

#[test]
fn test_from_witnessed_round_trips() {
    let cut = vv(&[(1, 3), (4, 1)]);
    // A witness for the vector: `floor_of` of its gap-free embedding is a `Cut`
    // equal to it, the only public path into `from_witnessed`.
    let witness = Cut::floor_of(&DotSet::from_cut(&cut));
    let have = DotSet::from_witnessed(&witness);
    assert_eq!(have.floor(), cut);
    assert_eq!(have.high_water(), cut);
    assert_eq!(have.holes().count(), 0);
    assert!(have.contains(dot(1, 3)));
    assert!(!have.contains(dot(1, 4)));
}

#[test]
fn test_merge_fills_each_others_holes() {
    let mut a = DotSet::new();
    assert!(a.insert(dot(1, 1)));
    assert!(a.insert(dot(1, 3)));
    let mut b = DotSet::new();
    assert!(b.insert(dot(1, 2)));
    // The union's floor strictly exceeds the join of the floors: b's dot fills
    // a's hole. This is the lax law paying rent, and why replicas exchanging
    // exact have-sets converge faster than replicas exchanging floors.
    let union = a.merge(&b);
    assert_eq!(a.floor().merge(&b.floor()), vv(&[(1, 1)]));
    assert_eq!(union.floor(), vv(&[(1, 3)]));
}

#[test]
fn test_high_water_matches_the_horizon_shape() {
    // The cross-repo example (minerva S80 / pinax R9, in the 1-based dot
    // basis): a store holding dots {1, 6} publishes high water 6, an upper
    // bound of a cut. The floor refuses the over-claim: only dot 1 is vouched.
    let mut have = DotSet::new();
    assert!(have.insert(dot(1, 1)));
    assert!(have.insert(dot(1, 6)));
    assert_eq!(have.high_water(), vv(&[(1, 6)]));
    assert_eq!(have.floor(), vv(&[(1, 1)]));
    let holes: Vec<_> = have.holes().collect();
    assert_eq!(holes, [dot(1, 2), dot(1, 3), dot(1, 4), dot(1, 5)]);
}

#[test]
fn test_difference_names_the_owed_dots() {
    // The debtor holds {1..=5, 8}; the creditor holds {1, 2, 4}. Owed: the
    // prefix part (3, 5] minus the creditor's parked 4, plus the exception 8.
    let mut mine = DotSet::new();
    for counter in [1, 2, 3, 4, 5, 8] {
        assert!(mine.insert(dot(1, counter)));
    }
    let mut yours = DotSet::new();
    for counter in [1, 2, 4] {
        assert!(yours.insert(dot(1, counter)));
    }
    let owed: Vec<_> = mine.difference(&yours).collect();
    assert_eq!(owed, [dot(1, 3), dot(1, 5), dot(1, 8)]);
    // Serving the owed dots converges the creditor to the union.
    for owed_dot in owed {
        assert!(yours.insert(owed_dot));
    }
    assert_eq!(yours, mine.merge(&yours));
    // Nothing is owed in return once the creditor has caught up.
    assert_eq!(yours.difference(&mine).next(), None);
}

#[test]
fn test_cut_difference_is_the_residual_span() {
    // The dot-level face of the vector example (claims, never subtractions):
    // between cuts 5 and 3 the owed dots are the span (3, 5], two dots whose
    // *names* come from the claim, not from the subtraction.
    let mine = DotSet::from_cut(&vv(&[(1, 5)]));
    let yours = DotSet::from_cut(&vv(&[(1, 3)]));
    let owed: Vec<_> = mine.difference(&yours).collect();
    assert_eq!(owed, [dot(1, 4), dot(1, 5)]);
}

#[test]
fn test_reports_honestly_for_stability() {
    // A two-member roster; member 2's receipt ran past a hole. Reporting the
    // floor (never the high water) keeps every hole above the watermark, so
    // nothing a member still needs can be declared safe to forget.
    let mut have = DotSet::new();
    for (station, counter) in [(1, 1), (1, 2), (2, 1), (2, 3)] {
        assert!(have.insert(dot(station, counter)));
    }
    let mut tracker = Stability::new([1, 2]);
    tracker.report(1, &vv(&[(1, 4), (2, 3)])).unwrap();
    tracker.report(2, &have.floor()).unwrap();
    let watermark = tracker.watermark();
    assert_eq!(watermark, vv(&[(1, 2), (2, 1)]));
    // The hole (2, 2) sits strictly above the watermark's station-2 prefix.
    let holes: Vec<_> = have.holes().collect();
    assert_eq!(holes, [dot(2, 2)]);
    assert!(watermark.get(2) < 2);
}