quepaxa 0.3.4

QuePaxa consensus for state machine replication: a sans-IO, no_std replicated log that, unlike Raft or Multi-Paxos, never stalls on election timeouts
Documentation
//! Interval summary register: the recorder's per-slot state (paper Alg. 3).

use crate::proposal::Proposal;
use crate::types::Step;

/// Recorder state for one slot. `None` is the paper's nil.
#[derive(Clone, Debug, Default, PartialEq, Eq)]
#[cfg_attr(feature = "model", derive(Hash))]
pub(crate) struct Register {
    /// Current step `S`.
    pub step: Step,
    /// First value recorded in the current step (`Fc`).
    pub first: Option<Proposal>,
    /// Maximum value recorded in the current step (`Ac`).
    pub agg: Option<Proposal>,
    /// Maximum value recorded in the previous step (`Ap`).
    pub prev_agg: Option<Proposal>,
}

/// What a recorder reports back: `(S, Fc, Ap)`.
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) struct Summary {
    pub step: Step,
    pub first: Option<Proposal>,
    pub prev_agg: Option<Proposal>,
}

impl Register {
    /// Applies `record(s, v)`; returns whether the register changed (and so must be persisted).
    pub fn record(&mut self, s: Step, v: Proposal) -> bool {
        if s == self.step {
            if self.agg.as_ref().is_some_and(|a| *a >= v) {
                return false;
            }
            self.agg = Some(v);
            true
        } else if s > self.step {
            self.prev_agg = if self.step.checked_add(1) == Some(s) { self.agg.take() } else { None };
            self.step = s;
            self.first = Some(v.clone());
            self.agg = Some(v);
            true
        } else {
            false
        }
    }

    pub fn summary(&self) -> Summary {
        Summary { step: self.step, first: self.first.clone(), prev_agg: self.prev_agg.clone() }
    }
}

/// Exhaustive versions of the property test below: every step, register state and value.
#[cfg(kani)]
mod proofs {
    use super::*;
    use crate::proposal::ValueKey;
    use crate::types::NodeId;

    /// Payloads are distinct per proposal: equality ignores them, so the proof compares
    /// them separately to catch a value recorded with the wrong bytes.
    fn any_proposal() -> Proposal {
        let key = ValueKey { origin: NodeId(kani::any()), incarnation: kani::any(), seq: kani::any() };
        let value: &'static [u8] = match kani::any::<u8>() % 3 {
            0 => b"",
            1 => b"a",
            _ => b"b",
        };
        Proposal { priority: kani::any(), key, value: bytes::Bytes::from_static(value) }
    }

    fn any_option() -> Option<Proposal> {
        if kani::any() { Some(any_proposal()) } else { None }
    }

    /// Equal, and with the same bytes (the payloads are distinct static slices and clones
    /// share them, so the same slice means the same bytes).
    fn same(a: &Option<Proposal>, b: &Option<Proposal>) -> bool {
        match (a, b) {
            (Some(a), Some(b)) => {
                a == b && a.value.as_ptr() == b.value.as_ptr() && a.value.len() == b.value.len()
            }
            (None, None) => true,
            _ => false,
        }
    }

    /// Paper invariants R1–R6 for one `record` from any register state.
    #[kani::proof]
    fn record_upholds_recorder_invariants() {
        let mut r =
            Register { step: kani::any(), first: any_option(), agg: any_option(), prev_agg: any_option() };
        let before = r.clone();
        let (s, v): (Step, Proposal) = (kani::any(), any_proposal());
        let changed = r.record(s, v.clone());
        let new = Some(v.clone());
        assert!(r.step >= before.step, "R1 step monotonic");
        assert!(
            changed
                == !(r.step == before.step
                    && same(&r.first, &before.first)
                    && same(&r.agg, &before.agg)
                    && same(&r.prev_agg, &before.prev_agg)),
            "changed exactly when it must be persisted"
        );
        if s < before.step {
            assert!(
                same(&r.first, &before.first)
                    && same(&r.agg, &before.agg)
                    && same(&r.prev_agg, &before.prev_agg),
                "R5 stale discard"
            );
        } else if s == before.step {
            assert!(same(&r.first, &before.first), "R2 first write-once");
            let raised = before.agg.as_ref().is_none_or(|a| v > *a);
            assert!(same(&r.agg, if raised { &new } else { &before.agg }), "R3 aggregate is the maximum");
            assert!(same(&r.prev_agg, &before.prev_agg));
        } else {
            let expect = if before.step.checked_add(1) == Some(s) { before.agg.clone() } else { None };
            assert!(same(&r.prev_agg, &expect), "R4 prior aggregate");
            assert!(r.step == s && same(&r.first, &new) && same(&r.agg, &new), "new step");
        }
        let sum = r.summary();
        assert!(sum.step == r.step && same(&sum.first, &r.first) && same(&sum.prev_agg, &r.prev_agg), "R6");
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::proposal::tests::prop;
    use proptest::prelude::*;

    fn summary(step: Step, first: Option<Proposal>, prev_agg: Option<Proposal>) -> Summary {
        Summary { step, first, prev_agg }
    }

    #[test]
    fn first_record_sets_step_and_first_value_with_nil_prior() {
        let mut r = Register::default();
        assert!(r.record(4, prop(3, 1, 0)));
        assert_eq!(r.summary(), summary(4, Some(prop(3, 1, 0)), None));
    }

    #[test]
    fn same_step_higher_value_raises_aggregate_but_keeps_first() {
        let mut r = Register::default();
        r.record(4, prop(3, 1, 0));
        assert!(r.record(4, prop(7, 2, 0)));
        assert_eq!(r.agg, Some(prop(7, 2, 0)));
        assert_eq!(r.first, Some(prop(3, 1, 0)));
    }

    #[test]
    fn same_step_lower_or_equal_value_changes_nothing() {
        let mut r = Register::default();
        r.record(4, prop(7, 2, 0));
        let before = r.clone();
        assert!(!r.record(4, prop(3, 1, 0)));
        assert!(!r.record(4, prop(7, 2, 0)));
        assert_eq!(r, before);
    }

    #[test]
    fn next_step_moves_aggregate_to_prior() {
        let mut r = Register::default();
        r.record(4, prop(3, 1, 0));
        r.record(4, prop(7, 2, 0));
        r.record(5, prop(1, 3, 0));
        assert_eq!(r.summary(), summary(5, Some(prop(1, 3, 0)), Some(prop(7, 2, 0))));
    }

    #[test]
    fn skipping_a_step_clears_prior_aggregate() {
        let mut r = Register::default();
        r.record(4, prop(7, 2, 0));
        r.record(6, prop(1, 3, 0));
        assert_eq!(r.summary(), summary(6, Some(prop(1, 3, 0)), None));
    }

    #[test]
    fn stale_step_is_discarded_and_reports_current_state() {
        let mut r = Register::default();
        r.record(4, prop(7, 2, 0));
        r.record(5, prop(1, 3, 0));
        let before = r.clone();
        assert!(!r.record(4, prop(9, 9, 0)));
        assert_eq!(r, before);
        assert_eq!(r.summary(), summary(5, Some(prop(1, 3, 0)), Some(prop(7, 2, 0))));
    }

    fn arb_input() -> impl Strategy<Value = (Step, Proposal)> {
        (4u32..12, 0u64..6, 0u32..3).prop_map(|(s, p, o)| (s, prop(p, o, 0)))
    }

    proptest! {
        // Paper invariants R1–R6 (map ticket "QuePaxa protocol, precisely", §10).
        #[test]
        fn register_upholds_recorder_invariants(inputs in proptest::collection::vec(arb_input(), 1..40)) {
            let mut r = Register::default();
            for (s, v) in inputs {
                let before = r.clone();
                let changed = r.record(s, v.clone());
                prop_assert!(r.step >= before.step, "R1 step monotonic");
                prop_assert_eq!(changed, r != before);
                if s < before.step {
                    prop_assert_eq!(&r, &before, "R5 stale discard");
                } else if s == before.step {
                    prop_assert_eq!(&r.first, &before.first, "R2 first write-once");
                    prop_assert_eq!(&r.agg, &core::cmp::max(before.agg.clone(), Some(v)), "R3");
                } else {
                    let expect = if s == before.step + 1 { before.agg.clone() } else { None };
                    prop_assert_eq!(&r.prev_agg, &expect, "R4 prior aggregate");
                    prop_assert_eq!(&r.first, &Some(v), "first value of new step");
                }
                prop_assert_eq!(r.summary(), Summary { step: r.step, first: r.first.clone(), prev_agg: r.prev_agg.clone() }, "R6");
            }
        }
    }
}