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

//! The lifecycle record frame suite (S284; PRD 0025 section 6): golden
//! layouts, framing and canonical-form refusals, the R4 displaced-record
//! fixture, Alma's joint boundary rows (S327), and round-trip,
//! canonicality, preflight, budget, and totality laws. The arrival
//! endorsement joins the family at S346 (PRD 0028 R7).

extern crate alloc;

use alloc::vec::Vec;
use core::num::NonZeroUsize;

use crate::kairos::Kairos;
use crate::metis::{Cut, Declaration, Dot, Epochs, SealedEpoch, Stability, VersionVector, Vouched};

/// Builds an identity literal. Panics on the non-dot counter zero (R-91).
#[track_caller]
fn d(station: u32, counter: u64) -> Dot {
    Dot::from_parts(station, counter).expect("test literal names the non-dot counter zero")
}

mod examples;
mod properties;

/// A rank with a known 17-byte frame (the metatheses suite's twin
/// helper).
fn rank(physical: u64) -> Kairos {
    Kairos::new(physical, 0u16, 1, 0u16)
}

fn vector(entries: &[(u32, u64)]) -> VersionVector {
    let mut vector = VersionVector::new();
    for &(station, count) in entries {
        vector.observe(station, count);
    }
    vector
}

/// A witnessed cut over `entries`, via the tracker-shaped honest door.
fn cut(entries: &[(u32, u64)]) -> Cut {
    Cut::from_witnessed(vector(entries))
}

/// Mints a declaration through the one shipped door: a tracker whose
/// watermark is exactly `at`, a fresh dot above it. The only way a test
/// outside the epoch module can hold a [`Declaration`], which is the
/// point: the codec suite exercises the same records the protocol does.
fn declaration(roster: &[u32], dot: Dot, tick: u64, at: &[(u32, u64)]) -> Declaration {
    let witnessed = cut(at);
    let mut stability = Stability::new(roster.iter().copied());
    for &station in roster {
        stability.report_cut(station, &witnessed).unwrap();
    }
    let mut epochs = Epochs::new(roster.iter().copied(), NonZeroUsize::new(1).unwrap());
    epochs
        .declare(dot, rank(tick), &stability, &Cut::bottom())
        .expect("the fixture dot is fresh above the fixture cut")
}

/// The R4 fixture window (PRD 0025 section 6): a two-station generation
/// whose seal retains an accepted-but-non-candidate declaration dot.
///
/// Station 1's declaration `(1, 3)` is minted causally *after* station
/// 2's `(2, 3)` (its cut covers that dot) but is delivered *first*; when
/// the predecessor arrives, the later record is displaced from the
/// candidate antichain while its dot stays in the protocol ledger. The
/// sealed record therefore carries `(1, 3)` in the ledger and not in the
/// candidates, the distinction the seal and lineage-proof frames must
/// keep distinct on the wire.
pub(in crate::metis::tests) fn displaced_window() -> (Epochs, SealedEpoch) {
    let mut epochs = Epochs::new([1, 2], NonZeroUsize::new(2).unwrap());

    // The causally later declaration (its cut covers (2, 3)) arrives
    // first and opens the window.
    let later = declaration(&[1, 2], d(1, 3), 9, &[(1, 2), (2, 3)]);
    let mut stability = Stability::new([1, 2]);
    for station in [1, 2] {
        stability
            .report_cut(station, &cut(&[(1, 2), (2, 3)]))
            .unwrap();
    }
    epochs
        .deliver(later, &stability, &Cut::bottom())
        .expect("the later declaration opens the window");

    // Its predecessor arrives second: the later record is displaced
    // (removed from the candidates, kept in the ledger) and the
    // predecessor becomes the sole candidate.
    let winner = declaration(&[1, 2], d(2, 3), 7, &[(1, 2), (2, 2)]);
    let address = winner.address();
    epochs
        .deliver(winner, &stability, &Cut::bottom())
        .expect("the predecessor displaces the later record");
    assert_eq!(
        epochs.candidates().count(),
        1,
        "the displaced record left the candidate antichain"
    );

    // Confirmation, adoption, and the seal, all over cuts covering both
    // declaration dots.
    let delivered = cut(&[(1, 3), (2, 3)]);
    let mut stability = Stability::new([1, 2]);
    for station in [1, 2] {
        stability.report_cut(station, &delivered).unwrap();
    }
    epochs
        .confirm(address, &Vouched::trust(1, delivered.clone()))
        .unwrap();
    epochs
        .confirm(address, &Vouched::trust(2, delivered.clone()))
        .unwrap();
    let _ = epochs.adopt(1, 3, &stability).unwrap();
    epochs.adopt_report(address, &Vouched::trust(2, 3)).unwrap();
    let sealed = epochs
        .try_seal(&stability)
        .expect("the adoption round is complete")
        .clone();

    assert_eq!(sealed.declaration(), address);
    let dots: Vec<Dot> = sealed.declaration_dots().collect();
    assert_eq!(
        dots,
        [d(1, 3), d(2, 3)],
        "the ledger keeps the displaced dot the candidates lost"
    );
    (epochs, sealed)
}