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

extern crate alloc;

use alloc::collections::BTreeSet;
use alloc::vec::Vec;

use crate::kairos::Kairos;
use crate::metis::{Anchor, Dot, DotSet, DotStore, Dotted, Locus, Rhapsody};

use super::super::d;
use super::clock;

fn two_ranks() -> (Kairos, Kairos) {
    let clk = clock(1);
    (clk.now(0u16), clk.now(0u16))
}

fn covered(rhapsody: &Rhapsody) -> DotSet {
    let mut ctx = DotSet::new();
    for dot in rhapsody.dots() {
        let _ = ctx.insert(dot);
    }
    for station in 0u32..4 {
        for counter in 1u64..6 {
            if rhapsody.locus(d(station, counter)).is_some() {
                let _ = ctx.insert(d(station, counter));
            }
        }
    }
    ctx
}

fn sample(station: u32, live: &[u64], tombstones: &[u64]) -> Rhapsody {
    let (r0, r1) = two_ranks();
    let mut rhapsody = Rhapsody::new();
    let mut prev: Option<(u32, u64)> = None;
    let mut all: Vec<u64> = live.iter().chain(tombstones).copied().collect();
    all.sort_unstable();
    all.dedup();
    for &dot in &all {
        let rank = if dot % 2 == 0 { r0 } else { r1 };
        let anchor = prev.map_or(Anchor::Origin, |raw: (u32, u64)| Anchor::After(raw.into()));
        assert!(rhapsody.weave(d(station, dot), Locus { anchor, rank }));
        prev = Some((station, dot));
    }

    let mut ctx = DotSet::new();
    for &dot in tombstones {
        let _ = ctx.insert(d(station, dot));
    }
    let live_pair = Dotted::try_new(rhapsody.clone(), covered(&rhapsody)).unwrap();
    let removal = Dotted::from_context(ctx);
    live_pair.merge(&removal).store().clone()
}

#[test]
fn test_conformance_survivor_law_on_the_visible_coordinate() {
    // Three cases at once. a holds 1, 2, 3. b holds 1, saw 2 and dropped it
    // (a tombstone), and never saw 3.
    let a = sample(1, &[1, 2, 3], &[]);
    let b = sample(1, &[1], &[2]);
    let a_ctx = covered(&a);
    let b_ctx = covered(&b);
    let merged = a.causal_merge(&a_ctx, &b, &b_ctx);
    let support: BTreeSet<Dot> = merged.dots().collect();
    // (1, 1): in both stores, survives.
    assert!(support.contains(&d(1, 1)));
    // (1, 2): held by a, but b's context saw it and b's store dropped it
    // (seen-and-dropped), so the merge honors the drop: superseded.
    assert!(!support.contains(&d(1, 2)));
    // (1, 3): held by a, b never saw it, survives.
    assert!(support.contains(&d(1, 3)));
    // The skeleton is the union: every woven dot persists, including the
    // superseded (1, 2) as an order tombstone.
    assert!(merged.locus(d(1, 1)).is_some());
    assert!(merged.locus(d(1, 2)).is_some());
    assert!(merged.locus(d(1, 3)).is_some());
}

#[test]
fn test_conformance_merge_is_a_semilattice_join() {
    let a = sample(1, &[1, 2], &[3]);
    let b = sample(1, &[1], &[2]);
    let c = sample(2, &[1, 2], &[]);
    let (actx, bctx, cctx) = (covered(&a), covered(&b), covered(&c));

    // Commutative.
    let ab = a.causal_merge(&actx, &b, &bctx);
    let ba = b.causal_merge(&bctx, &a, &actx);
    assert_eq!(ab, ba);

    // Associative.
    let bc = b.causal_merge(&bctx, &c, &cctx);
    let bc_ctx = bctx.merge(&cctx);
    let left = a.causal_merge(&actx, &bc, &bc_ctx);
    let ab_ctx = actx.merge(&bctx);
    let right = ab.causal_merge(&ab_ctx, &c, &cctx);
    assert_eq!(left, right);

    // Idempotent.
    assert_eq!(a.causal_merge(&actx, &a, &actx), a);

    // Bottom identity.
    let bottom = Rhapsody::new();
    let empty = DotSet::new();
    assert_eq!(a.causal_merge(&actx, &bottom, &empty), a);
    assert_eq!(bottom.causal_merge(&empty, &a, &actx), a);
}

#[test]
fn test_conformance_restriction_is_fiber_selection() {
    // Two stations; restricting to one keeps exactly that station's dots on
    // both coordinates, and commutes with the merge.
    let a = {
        let mut w = sample(1, &[1, 2], &[]);
        let extra = sample(2, &[1], &[]);
        // Fold station 2 in by merging (disjoint stations).
        let actx = covered(&w);
        let ectx = covered(&extra);
        w = w.causal_merge(&actx, &extra, &ectx);
        w
    };
    let b = sample(2, &[1, 2], &[]);
    let roster = [1u32];

    // Fiber selection on both coordinates.
    let kept = a.restrict(roster);
    let support: Vec<Dot> = kept.dots().collect();
    assert!(support.iter().all(|dot| dot.station() == 1));
    assert!(kept.locus(d(2, 1)).is_none());

    // Commutes with the merge.
    let actx = covered(&a);
    let bctx = covered(&b);
    let merged = a.causal_merge(&actx, &b, &bctx);
    let restrict_then_merge = a.restrict(roster).causal_merge(
        &actx.restrict(roster),
        &b.restrict(roster),
        &bctx.restrict(roster),
    );
    assert_eq!(merged.restrict(roster), restrict_then_merge);
}

#[test]
fn test_conformance_novel_to_selects_uncovered_dots() {
    let a = sample(1, &[1, 2, 3], &[]);
    // A peer context that has seen (1, 1) and (1, 2).
    let mut peer = DotSet::new();
    assert!(peer.insert(d(1, 1)));
    assert!(peer.insert(d(1, 2)));
    let novel = a.novel_to(&peer);
    // Only (1, 3) is novel on the SUPPORT coordinate (the trait law), but
    // the skeleton ships whole: coverage proves supersession, never locus
    // possession, so recording state has no sound sub-selection (S190; the
    // outrun-heal example in `core/construction.rs` is the counterexample
    // the old covered-loci filter failed).
    let support: Vec<Dot> = novel.dots().collect();
    assert_eq!(support, [d(1, 3)]);
    assert!(novel.locus(d(1, 3)).is_some());
    assert!(novel.locus(d(1, 1)).is_some());
    assert!(novel.locus(d(1, 2)).is_some());
}