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

use super::super::super::support::dot;
use super::{Doc, add, dots, remove_observed};
use crate::metis::{DotMap, DotSet, DotStore, Dotted, UncoveredDot};

#[test]
fn test_try_new_refuses_the_uncovered_pair() {
    // A pair whose store carries a dot its context disowns lies about its
    // own past; the boundary constructor refuses with the first witness.
    let store = DotMap::singleton(7u8, dots(&[(1, 1), (1, 3)]));
    let context = dots(&[(1, 1)]);
    let refusal = Dotted::try_new(store.clone(), context).unwrap_err();
    assert_eq!(refusal, UncoveredDot { dot: dot(1, 3) });
    // The covering context assembles fine, and reads back intact.
    let pair = Dotted::try_new(store.clone(), dots(&[(1, 1), (1, 2), (1, 3)])).unwrap();
    assert_eq!(pair.store(), &store);
}

#[test]
fn test_trimmed_context_would_lose_the_removal() {
    // The delta_for design decision, pinned: the context ships whole because
    // a trimmed context loses removals. This side saw dot (1, 1) and dropped
    // it; the peer also saw (1, 1) but still holds it. The dot is in both
    // contexts, so a trimmed delta context would omit it and the peer would
    // keep it alive: resurrection.
    //
    // This side: wrote (1, 1) under key 7, then removed it. Store bottom,
    // context still holds (1, 1).
    let mut me = Doc::new();
    let _ = add(&mut me, 1, 7);
    let _ = remove_observed(&mut me, 7);
    assert!(me.store().is_bottom());
    assert!(me.context().contains(dot(1, 1)));

    // The peer: saw (1, 1) under key 7 and still holds it.
    let mut peer = Doc::new();
    let _ = add(&mut peer, 1, 7);
    assert!(
        peer.store()
            .get(&7)
            .is_some_and(|held| held.contains(dot(1, 1)))
    );

    // The correct delta: full context. Merging it propagates the removal.
    let correct = me.delta_for(peer.context());
    let after_correct = peer.merge(&correct);
    assert!(after_correct.store().get(&7).is_none());
    // It is exactly as good as merging the whole state: the theorem.
    assert_eq!(after_correct, peer.merge(&me));

    // The naive trimmed delta, built by hand: context = me \ peer, store =
    // the same novelty. Merging it resurrects the dot.
    let mut trimmed_context = DotSet::new();
    for owed in me.context().difference(peer.context()) {
        assert!(trimmed_context.insert(owed));
    }
    let trimmed = Dotted::try_new(correct.store().clone(), trimmed_context).unwrap();
    let after_trimmed = peer.merge(&trimmed);
    assert!(
        after_trimmed
            .store()
            .get(&7)
            .is_some_and(|held| held.contains(dot(1, 1)))
    );
}

#[test]
fn test_dot_set_intersect_names_the_common_dots() {
    // The audit read: exactly the dots both replicas received.
    let a = dots(&[(1, 1), (1, 2), (1, 5), (2, 1)]);
    let b = dots(&[(1, 2), (1, 5), (1, 6), (3, 1)]);
    let both = a.intersect(&b);
    assert!(both.contains(dot(1, 2)) && both.contains(dot(1, 5)));
    assert!(!both.contains(dot(1, 1)) && !both.contains(dot(1, 6)));
    assert!(!both.contains(dot(2, 1)) && !both.contains(dot(3, 1)));
    assert_eq!(a.intersect(&a), a); // idempotent, canonical round-trip
}