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

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

/// The scalar per-source FIFO gate: the *degenerate* [`Gate`] (PRD 0009).
///
/// It orders each source's events but imposes *no* cross-source order, so an event is
/// deliverable as soon as it is the next one from its own sender, whatever else is
/// outstanding. Its dependency is a bare `u64` sequence number, not a [`VersionVector`], so
/// a [`Fifo`] [`Event`](crate::metis::Event) is `Event<T, u64>`, which is the proof the data axis genuinely
/// varies independent of the gate.
///
/// This is the rule a per-source replication watermark wants (FIFO delivery per station,
/// convergence without happens-before). Contrast [`Causal`](crate::metis::Causal), which
/// additionally requires cross-source completeness.
#[derive(Debug, Clone, Copy, Default)]
pub struct Fifo;

impl Gate for Fifo {
    /// The event's own per-sender sequence number (`>= 1`); no cross-source dependencies.
    type Dep = u64;
    /// Per-sender delivered counts, a [`VersionVector`] reused as a `u32 -> u64` watermark
    /// map; only the sender's own entry is consulted.
    type Progress = VersionVector;

    /// Contiguity alone: the next sequence number from this sender. No completeness clause,
    /// so cross-source dependencies are irrelevant.
    fn deliverable(delivered: &VersionVector, sender: u32, seq: &u64) -> bool {
        *seq == delivered.get(sender).saturating_add(1)
    }

    /// Raise the sender's watermark to the released sequence number; contiguity makes this a
    /// bump of exactly one.
    fn advance(delivered: &mut VersionVector, sender: u32, seq: &u64) {
        delivered.observe(sender, *seq);
    }

    /// The sequence number is not ahead of the sender's watermark: a duplicate or replay.
    /// Load-bearing exactly as in [`Causal`](crate::metis::Causal), since `deliverable` is an equality.
    fn stale(delivered: &VersionVector, sender: u32, seq: &u64) -> bool {
        *seq <= delivered.get(sender)
    }
}

impl ReleaseDrivenGate for Fifo {}