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

use super::{Gate, ReleaseDrivenGate};
use crate::metis::VersionVector;

/// The causal happens-before gate, the canonical [`Gate`].
///
/// Releases an event once its full dependency [`VersionVector`] is delivered
/// (Birman-Schiper-Stephenson causal broadcast). The rule the buffer hard-wired before
/// PRD 0009; [`CausalIdeal`](crate::metis::CausalIdeal) is the buffer over it.
#[derive(Debug, Clone, Copy, Default)]
pub struct Causal;

impl Gate for Causal {
    type Dep = VersionVector;
    type Progress = VersionVector;

    /// Contiguity (`deps[sender] == D[sender] + 1`, the very next event from the sender)
    /// and causal completeness (`deps[k] <= D[k]` for every other `k`, everything the sender
    /// had seen is already released here).
    fn deliverable(delivered: &VersionVector, sender: u32, deps: &VersionVector) -> bool {
        if deps.get(sender) != delivered.get(sender).saturating_add(1) {
            return false;
        }
        deps.iter()
            .all(|(station, count)| station == sender || count <= delivered.get(station))
    }

    /// The lattice join `D := D.merge(&deps)`. Given the two `deliverable` conditions the
    /// merge bumps only the sender's entry by one.
    fn advance(delivered: &mut VersionVector, _sender: u32, deps: &VersionVector) {
        *delivered = delivered.merge(deps);
    }

    /// The event's own dot is not ahead of what the sender has had released here: a
    /// duplicate or stale replay, including a malformed self-dot of `0`.
    fn stale(delivered: &VersionVector, sender: u32, deps: &VersionVector) -> bool {
        deps.get(sender) <= delivered.get(sender)
    }
}

impl ReleaseDrivenGate for Causal {}