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

use crate::kairos::Kairos;
use crate::metis::{CausalIdeal, Event, VersionVector};

#[test]
fn test_chain_across_two_stations() {
    // Insert effect before cause; the buffer must still release cause then effect.
    let mut s1 = VersionVector::new();
    let _ = s1.increment(1);
    let a = Event {
        stamp: Kairos::new(10, 0, 1, 0u16),
        deps: s1.clone(),
        payload: 0u32,
    };
    let mut s2 = s1;
    let _ = s2.increment(2);
    let b = Event {
        stamp: Kairos::new(20, 0, 2, 0u16),
        deps: s2,
        payload: 1u32,
    };

    let mut buf = CausalIdeal::new();
    buf.insert(b);
    assert_eq!(buf.pop_ready(), None);
    buf.insert(a);
    assert_eq!(buf.pop_ready(), Some(0));
    assert_eq!(buf.pop_ready(), Some(1));
    assert_eq!(buf.pop_ready(), None);
    assert_eq!(buf.pending_len(), 0);
}

#[test]
fn test_concurrent_pair_released_in_kairos_order() {
    let mut s1 = VersionVector::new();
    let _ = s1.increment(1);
    let mut s2 = VersionVector::new();
    let _ = s2.increment(2);
    let high = Event {
        stamp: Kairos::new(50, 0, 1, 0u16),
        deps: s1,
        payload: 1u32,
    };
    let low = Event {
        stamp: Kairos::new(40, 0, 2, 0u16),
        deps: s2,
        payload: 2u32,
    };

    let mut buf = CausalIdeal::new();
    buf.insert(high);
    buf.insert(low);
    assert_eq!(buf.pop_ready(), Some(2));
    assert_eq!(buf.pop_ready(), Some(1));
    assert_eq!(buf.pop_ready(), None);
}

#[test]
fn test_gap_blocks_then_fills() {
    let mut v = VersionVector::new();
    let _ = v.increment(1);
    let first = Event {
        stamp: Kairos::new(10, 0, 1, 0u16),
        deps: v.clone(),
        payload: 0u32,
    };
    let _ = v.increment(1);
    let second = Event {
        stamp: Kairos::new(11, 0, 1, 0u16),
        deps: v,
        payload: 1u32,
    };

    let mut buf = CausalIdeal::new();
    buf.insert(second);
    assert_eq!(buf.pop_ready(), None);
    assert_eq!(buf.pending_len(), 1);
    buf.insert(first);
    assert_eq!(buf.pop_ready(), Some(0));
    assert_eq!(buf.pop_ready(), Some(1));
    assert_eq!(buf.pop_ready(), None);
}

#[test]
fn test_stale_replay_dropped() {
    let mut v = VersionVector::new();
    let _ = v.increment(1);
    let event = Event {
        stamp: Kairos::new(10, 0, 1, 0u16),
        deps: v,
        payload: 0u32,
    };

    let mut buf = CausalIdeal::new();
    buf.insert(event.clone());
    assert_eq!(buf.pop_ready(), Some(0));
    buf.insert(event);
    assert_eq!(buf.pending_len(), 0);
    assert_eq!(buf.pop_ready(), None);
}