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

extern crate alloc;

use super::super::support::dot;
use crate::metis::{DotSet, Retired, Retirement, UnknownStation};

/// A `DotSet` from `(station, dot)` pairs, the retirement-suite way.
fn dots(pairs: &[(u32, u64)]) -> DotSet {
    let mut set = DotSet::new();
    for &(station, counter) in pairs {
        let _ = set.insert(dot(station, counter));
    }
    set
}

/// The claimed have-set inside a `Retired`, for asserting the meet's shape.
/// Round-trips through `trust`/`condense` invariance: two `Retired` claiming the
/// same dots excise the same tombstones, so equality on the wrapped set is the
/// honest read, exposed here only in test via reconstructing the expected claim.
fn retired_eq(retired: &Retired, expected: &DotSet) -> bool {
    *retired == Retired::trust(expected.clone())
}

#[test]
fn test_retired_is_the_meet_across_the_roster() {
    // DotSets are exact have-sets (dots enumerated, not prefix-closed cuts), so
    // each acknowledgement names its applied dots explicitly.
    let mut tracker = Retirement::new([1, 2, 3]);
    tracker.acknowledge(1, &dots(&[(1, 1), (2, 1)])).unwrap();
    tracker
        .acknowledge(2, &dots(&[(1, 1), (2, 1), (3, 1)]))
        .unwrap();
    tracker
        .acknowledge(3, &dots(&[(1, 1), (2, 1), (2, 2)]))
        .unwrap();
    // The intersection: only the dots EVERY member acknowledged. (1,1) and (2,1)
    // survive (all three hold them), (3,1) drops (only member 2), (2,2) drops
    // (only member 3).
    assert!(retired_eq(&tracker.retired(), &dots(&[(1, 1), (2, 1)])));
}

#[test]
fn test_retired_requires_every_member() {
    let mut tracker = Retirement::new([1, 2]);
    tracker.acknowledge(1, &dots(&[(1, 9), (2, 9)])).unwrap();
    // Member 2 has never acknowledged: it vouches for nothing, so nothing is
    // retired everywhere.
    assert!(retired_eq(&tracker.retired(), &DotSet::new()));
}

#[test]
fn test_unknown_station_is_refused_unchanged() {
    let mut tracker = Retirement::new([1, 2]);
    tracker.acknowledge(1, &dots(&[(1, 1)])).unwrap();
    let before = tracker.clone();
    let refused = tracker.acknowledge(7, &dots(&[(1, 5)]));
    assert_eq!(refused, Err(UnknownStation { station: 7 }));
    assert_eq!(tracker, before);
}

#[test]
fn test_acknowledge_is_order_invariant() {
    // The same acknowledgements in any order yield the same tracker: fold by a
    // join is commutative.
    let mut forward = Retirement::new([1, 2]);
    forward.acknowledge(1, &dots(&[(1, 1)])).unwrap();
    forward.acknowledge(2, &dots(&[(1, 1), (2, 2)])).unwrap();
    forward.acknowledge(1, &dots(&[(1, 4)])).unwrap();

    let mut backward = Retirement::new([1, 2]);
    backward.acknowledge(1, &dots(&[(1, 4)])).unwrap();
    backward.acknowledge(2, &dots(&[(1, 1), (2, 2)])).unwrap();
    backward.acknowledge(1, &dots(&[(1, 1)])).unwrap();

    assert_eq!(forward, backward);
}

#[test]
fn test_stale_acknowledgement_is_absorbed() {
    let mut tracker = Retirement::new([1, 2]);
    tracker.acknowledge(1, &dots(&[(1, 4)])).unwrap();
    tracker.acknowledge(2, &dots(&[(1, 4)])).unwrap();
    let high = tracker.retired();
    assert!(retired_eq(&high, &dots(&[(1, 4)])));
    // A late, subset acknowledgement is join-absorbed: the meet never regresses.
    tracker.acknowledge(1, &dots(&[(1, 4)])).unwrap();
    assert_eq!(tracker.retired(), high);
}

#[test]
fn test_retired_is_monotone_non_decreasing() {
    // Adding an acknowledgement can only grow (never shrink) the meet once every
    // member vouches: the license to excise below it.
    let mut tracker = Retirement::new([1, 2]);
    tracker.acknowledge(1, &dots(&[(1, 3)])).unwrap();
    tracker.acknowledge(2, &dots(&[(1, 3)])).unwrap();
    let first = tracker.retired();
    // Both members now also acknowledge (2, 1): the meet grows to include it.
    tracker.acknowledge(1, &dots(&[(1, 3), (2, 1)])).unwrap();
    tracker.acknowledge(2, &dots(&[(1, 3), (2, 1)])).unwrap();
    let second = tracker.retired();
    assert!(retired_eq(&first, &dots(&[(1, 3)])));
    assert!(retired_eq(&second, &dots(&[(1, 3), (2, 1)])));
}

#[test]
fn test_empty_roster_retired_is_bottom() {
    // The empty family's mathematical meet is the lattice top ("every dot is
    // retired", vacuously): the maximally unsafe fabrication for a safe-to-excise
    // quantity, so the degenerate answer is bottom, nobody vouches for nothing.
    let tracker = Retirement::new(core::iter::empty::<u32>());
    assert!(retired_eq(&tracker.retired(), &DotSet::new()));
}

#[test]
fn test_acknowledged_reader_exposes_the_laggard() {
    let mut tracker = Retirement::new([2, 1]);
    tracker.acknowledge(1, &dots(&[(1, 6)])).unwrap();
    // Ascending station order, un-acknowledged members at bottom: the member
    // pinning the meet is visible.
    let slots: alloc::vec::Vec<_> = tracker.acknowledged().collect();
    assert_eq!(slots.len(), 2);
    assert_eq!(slots[0], (1, &dots(&[(1, 6)])));
    assert_eq!(slots[1], (2, &DotSet::new()));
}

#[test]
fn test_trust_is_the_audited_escape() {
    // trust wraps a caller-gathered claim identically to the tracker's meet when
    // the dots agree: the two constructors are interchangeable at the claim they
    // name, and only the burden differs (the tracker gathers it, trust asserts).
    let mut tracker = Retirement::new([1]);
    tracker.acknowledge(1, &dots(&[(1, 2), (1, 3)])).unwrap();
    assert_eq!(tracker.retired(), Retired::trust(dots(&[(1, 2), (1, 3)])));
}