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

extern crate alloc;

use core::num::NonZeroU32;

use crate::kairos::{Clock, LocalClock, TickCounter, VirtualTimeSource};
use alloc::vec::Vec;

fn run_len(len: u32) -> NonZeroU32 {
    NonZeroU32::new(len).expect("test run lengths are nonzero")
}

#[test]
fn test_a_run_is_the_frozen_reading_mint_succession() {
    // The run's members are byte-for-byte the stamps an equal number of
    // individual mints against a frozen reading would have committed.
    let frozen = Clock::with_default_config(VirtualTimeSource::new(41), 3).unwrap();
    let individually: Vec<_> = (0..5).map(|_| frozen.now(7u16)).collect();

    let bulk = Clock::with_default_config(VirtualTimeSource::new(41), 3).unwrap();
    let run = bulk.now_run(run_len(5), 7u16);

    assert_eq!(run.len(), 5);
    assert_eq!(run.iter().len(), 5, "the iterator is exact-sized");
    let members: Vec<_> = run.iter().collect();
    assert_eq!(members, individually);
    assert_eq!(run.first(), individually[0]);
    assert_eq!(run.last(), individually[4]);
    for (index, &stamp) in (0u32..).zip(&individually) {
        assert_eq!(run.get(index), Some(stamp));
    }
    assert_eq!(run.get(5), None, "reads past the reservation refuse");

    // Both clocks committed the same position: their next mints agree.
    assert_eq!(frozen.now(7u16), bulk.now(7u16));
}

#[test]
fn test_a_run_of_one_is_exactly_now() {
    let single = Clock::with_default_config(TickCounter::new(), 2).unwrap();
    let bulk = Clock::with_default_config(TickCounter::new(), 2).unwrap();
    let minted = single.now(0u16);
    let run = bulk.now_run(run_len(1), 0u16);
    assert_eq!(run.first(), minted);
    assert_eq!(run.last(), minted);
    assert_eq!(run.len(), 1);
}

#[test]
fn test_the_next_mint_dominates_every_run_member() {
    let clock = Clock::with_default_config(TickCounter::new(), 5).unwrap();
    let run = clock.now_run(run_len(1_000), 0u16);
    let next = clock.now(0u16);
    assert!(next > run.last(), "the commitment is the run's last member");
    for stamp in &run {
        assert!(
            next > stamp,
            "no later mint may land inside the reservation"
        );
    }
}

#[test]
fn test_a_run_rolls_the_logical_ceiling_into_physical() {
    // A run wider than one physical unit's rank slots carries into the next
    // physical unit exactly as iterated sends do (the sentinel rolls, and
    // logical restarts), and the members stay strictly ascending.
    let clock = Clock::with_default_config(VirtualTimeSource::new(100), 1).unwrap();
    let width = u32::from(u16::MAX); // rank slots per physical unit
    let run = clock.now_run(run_len(width + 2), 0u16);

    assert_eq!(run.first().physical(), 100);
    assert_eq!(run.first().logical(), 0);
    let last_in_unit = run.get(width - 1).unwrap();
    assert_eq!(last_in_unit.physical(), 100);
    assert_eq!(last_in_unit.logical(), u16::MAX - 1);
    let rolled = run.get(width).unwrap();
    assert_eq!(rolled.physical(), 101, "the sentinel rolls into physical");
    assert_eq!(rolled.logical(), 0, "logical restarts after the roll");
    assert!(rolled > last_in_unit);
    assert_eq!(run.last(), run.get(width + 1).unwrap());

    // The commitment sits past the roll: the next mint dominates it.
    assert!(clock.now(0u16) > run.last());
}

#[test]
fn test_a_unit_crossing_run_reports_the_iterated_skews() {
    // A run whose carry crosses a physical unit runs the committed
    // physical ahead of the one frozen reading, and every mint past the
    // crossing reads the source behind the committed physical. The stats
    // must tell the story the iterated mints would have told (the S211
    // gate review's finding: the first cut copied the first mint's zero
    // skews, under-reporting the gap the run itself created).
    let width = u32::from(u16::MAX);
    let bulk = Clock::with_default_config(VirtualTimeSource::new(41), 3).unwrap();
    let _ = bulk.now_run(run_len(width + 2), 0u16);
    let single = Clock::with_default_config(VirtualTimeSource::new(41), 3).unwrap();
    for _ in 0..u64::from(width) + 2 {
        let _ = single.now(0u16);
    }
    let (bulk_stats, single_stats) = (bulk.stats(), single.stats());
    assert_eq!(
        bulk_stats.max_forward_skew_ns, single_stats.max_forward_skew_ns,
        "one reservation reports the forward skew its mints would have"
    );
    assert_eq!(
        bulk_stats.max_backward_skew_ns, single_stats.max_backward_skew_ns,
        "one reservation reports the backward skew its mints would have"
    );
    assert_eq!(
        bulk_stats.max_forward_skew_ns, 1,
        "the crossing ran the committed physical one unit ahead"
    );

    // The sharp corner the extended Kani harness carved into the first cut
    // of this law: when the run's FINAL member is itself the rollover, no
    // iterated mint ever reads the rolled physical, so the honest maxima
    // sit at the penultimate member and the stats stay at zero.
    let exact = Clock::with_default_config(VirtualTimeSource::new(41), 3).unwrap();
    let _ = exact.now_run(run_len(width + 1), 0u16);
    let twin = Clock::with_default_config(VirtualTimeSource::new(41), 3).unwrap();
    for _ in 0..=u64::from(width) {
        let _ = twin.now(0u16);
    }
    assert_eq!(
        exact.stats().max_forward_skew_ns,
        twin.stats().max_forward_skew_ns
    );
    assert_eq!(exact.stats().max_forward_skew_ns, 0);
}

#[test]
fn test_a_run_observes_skew_once() {
    // The run consumes one reading, so a genuine SOURCE regression is
    // recorded once for the whole reservation, exactly what the iterated
    // mints against the same frozen reading would fold (each observes the
    // same thirty; the maximum is one observation).
    let source = VirtualTimeSource::new(50);
    let driver = source.clone();
    let clock = Clock::with_default_config(source, 1).unwrap();
    let _ = clock.now(0u16);
    driver.set(20); // thirty behind the committed physical
    let _ = clock.now_run(run_len(64), 0u16);
    assert_eq!(
        clock.stats().max_backward_skew_ns,
        30,
        "one reading, one skew observation"
    );
}

#[test]
fn test_local_clock_runs_agree_with_the_atomic_shell() {
    let atomic = Clock::with_default_config(TickCounter::new(), 4).unwrap();
    let local = LocalClock::new(TickCounter::new(), 4).unwrap();
    let a = atomic.now_run(run_len(9), 3u16);
    let b = local.now_run(run_len(9), 3u16);
    assert_eq!(a, b, "one fold, two shells: identical reservations");
    assert_eq!(atomic.now(3u16), local.now(3u16));
}