tawasuyu/hifas

1//! `fencing` — la frontera del clon (T11c, §D): lo que NINGÚN sistema
2//! coordination-free puede cerrar.
3//!
4//! F2 (réplica-por-dispositivo, T11a) resuelve *dos dispositivos distintos*.
5//! Queda el caso duro: **una celda con dos escritores vivos** — un dispositivo
6//! restaurado a dos copias (VM snapshot, proceso duplicado) que comparten
7//! `device_id` y celda y **no se comunican**. Cada clon puede gastar la celda
8//! entera → doble gasto.
9//!
10//! **Teorema de imposibilidad (`BOUNDARY.md`).** Ningún mecanismo local detecta un
11//! clon silencioso antes de que los clones se comuniquen. Es el mismo CAP que el
12//! sobregiro particionado, ahora dentro de una celda.
13//!
14//! **Lo mejor posible — fencing por época, enforced en el merge:** cada arranque
15//! de un dispositivo incrementa una **época** monótona **device-local** (evita
16//! consenso). El gasto se indexa por `(device_id, epoch)`. Al fusionar, dos épocas
17//! para un mismo `device_id` delatan un clon: la de época menor es obsoleta. No se
18//! **previene** el doble gasto (imposible), se **acota** (a una celda por clon no
19//! detectado) y se **detecta** al reconectar: de "silencioso e ilimitado" a
20//! "acotado y delatado".
21
22use std::collections::BTreeMap;
23
24/// Identidad de un dispositivo (una celda de presupuesto).
25pub type DeviceId = u64;
26
27/// Resultado de fusionar dos vistas de una misma celda-dispositivo.
28#[derive(Debug, Clone, PartialEq, Eq)]
29pub enum MergeOutcome {
30    /// Un único linaje: fusión limpia.
31    Ok,
32    /// Dos linajes con el mismo `device_id`: clon detectado. La época menor es el
33    /// clon obsoleto; sus gastos post-bifurcación quedan aislados.
34    CloneDetected {
35        /// El dispositivo bifurcado.
36        device_id: DeviceId,
37        /// Época obsoleta (el clon).
38        stale_epoch: u64,
39        /// Época viva (el linaje que continúa).
40        live_epoch: u64,
41    },
42}
43
44/// El gasto de una celda-dispositivo, indexado por época (fencing).
45#[derive(Debug, Clone, PartialEq, Eq)]
46pub struct FencedCell {
47    /// El dispositivo dueño de la celda.
48    pub device_id: DeviceId,
49    /// Presupuesto de la celda (`b0`).
50    pub budget: i64,
51    /// Época viva actual (monótona, device-local, persistida al arrancar).
52    pub epoch: u64,
53    /// Gasto por época: `epoch -> spent`. Cada época solo crece (CRDT por época).
54    pub spent: BTreeMap<u64, i64>,
55}
56
57impl FencedCell {
58    /// Celda nueva en la época 0, sin gasto.
59    pub fn new(device_id: DeviceId, budget: i64) -> Self {
60        Self {
61            device_id,
62            budget,
63            epoch: 0,
64            spent: BTreeMap::new(),
65        }
66    }
67
68    /// Arranque del dispositivo: incrementa y persiste la época (device-local).
69    pub fn boot(&mut self) -> u64 {
70        self.epoch += 1;
71        self.epoch
72    }
73
74    /// Gasta `amount` (≥0) en la época viva actual.
75    pub fn spend(&mut self, amount: i64) {
76        debug_assert!(amount >= 0);
77        *self.spent.entry(self.epoch).or_insert(0) += amount;
78    }
79
80    /// Épocas con gasto no nulo (los linajes presentes).
81    fn linajes(&self) -> Vec<u64> {
82        self.spent.iter().filter(|(_, &s)| s > 0).map(|(&e, _)| e).collect()
83    }
84
85    /// Gasto total reclamado por TODOS los linajes (incluye el doble gasto de un
86    /// clon; puede exceder el presupuesto).
87    pub fn total_claimed(&self) -> i64 {
88        self.spent.values().sum()
89    }
90
91    /// Gasto del linaje **vivo** (la época mayor): lo que se propaga como legítimo
92    /// hacia el resto de la malla. Aísla los linajes obsoletos.
93    pub fn reconciled_spent(&self) -> i64 {
94        self.spent.iter().next_back().map(|(_, &s)| s).unwrap_or(0)
95    }
96
97    /// Daño acotado: el sobregiro de la celda por el clon, `max(0, total − budget)`.
98    /// Por el fencing está acotado a **una celda** (cada clon gasta ≤ su presupuesto).
99    pub fn overspend(&self) -> i64 {
100        (self.total_claimed() - self.budget).max(0)
101    }
102
103    /// **Fusión con enforcement de fencing (§D).** Une los gastos por época
104    /// (máximo, monótono por época) y, si aparecen dos linajes, delata el clon.
105    pub fn merge(&mut self, other: &FencedCell) -> MergeOutcome {
106        debug_assert_eq!(self.device_id, other.device_id, "mismo dispositivo");
107        self.budget = self.budget.max(other.budget);
108        for (&e, &s) in &other.spent {
109            let cur = self.spent.entry(e).or_insert(0);
110            *cur = (*cur).max(s);
111        }
112        let linajes = self.linajes();
113        if linajes.len() >= 2 {
114            MergeOutcome::CloneDetected {
115                device_id: self.device_id,
116                stale_epoch: linajes[0],                 // BTreeMap ordenado: menor
117                live_epoch: *linajes.last().unwrap(),    // mayor
118            }
119        } else {
120            MergeOutcome::Ok
121        }
122    }
123}
124
125#[cfg(test)]
126mod tests {
127    use super::*;
128    use proptest::prelude::*;
129
130    /// §G.3 — detección de clon. Un `device_id` se bifurca en dos épocas; cada
131    /// clon gasta su celda entera aislado; al reconectar (merge) se delata,
132    /// el daño está acotado a una celda, y el linaje vivo no propaga el doble gasto.
133    #[test]
134    fn clon_detectado_acotado_y_delatado() {
135        // Celda de 50. Clon A (época 1) gasta 50; clon B (época 2) gasta 50.
136        let mut a = FencedCell::new(7, 50);
137        a.epoch = 1;
138        a.spend(50);
139        let mut b = FencedCell::new(7, 50);
140        b.epoch = 2;
141        b.spend(50);
142
143        let outcome = a.merge(&b);
144        assert_eq!(
145            outcome,
146            MergeOutcome::CloneDetected { device_id: 7, stale_epoch: 1, live_epoch: 2 },
147            "el clon se delata al reconectar, no pasa silencioso"
148        );
149        // El doble gasto ocurrió (100 reclamado de una celda de 50)...
150        assert_eq!(a.total_claimed(), 100);
151        // ...pero está ACOTADO a una celda: sobregiro = 50 = un presupuesto.
152        assert_eq!(a.overspend(), 50);
153        assert!(a.overspend() <= a.budget, "daño acotado a una celda");
154        // El linaje vivo (época 2) es lo único que se propaga como legítimo.
155        assert_eq!(a.reconciled_spent(), 50);
156    }
157
158    /// Testigo impreso de `CloneDetected`: las dos épocas, el gasto aislado y el
159    /// daño acotado a una celda. (`cargo test -- --nocapture` para verlo.)
160    #[test]
161    fn witness_clone_detected_impreso() {
162        let mut a = FencedCell::new(7, 50);
163        a.epoch = 1;
164        a.spend(50); // clon A gasta su celda entera
165        let mut b = FencedCell::new(7, 50);
166        b.epoch = 2;
167        b.spend(50); // clon B (rebooteado a época 2) gasta la misma celda
168
169        let outcome = a.merge(&b);
170        println!("TESTIGO CloneDetected:");
171        println!("  outcome            = {outcome:?}");
172        println!("  épocas presentes   = {:?}", a.spent.keys().collect::<Vec<_>>());
173        println!("  total_claimed      = {} (de una celda de {})", a.total_claimed(), a.budget);
174        println!("  reconciled (vivo)  = {} (época mayor; lo único propagado)", a.reconciled_spent());
175        println!("  gasto aislado      = {} (época menor, el clon obsoleto)", a.spent[&1]);
176        println!("  overspend (daño)   = {} <= budget {} ⟹ acotado a UNA celda", a.overspend(), a.budget);
177
178        assert_eq!(
179            outcome,
180            MergeOutcome::CloneDetected { device_id: 7, stale_epoch: 1, live_epoch: 2 }
181        );
182        assert_eq!(a.overspend(), 50);
183    }
184
185    /// §G.4 — fuente monótona (una sola época): merge limpio, comportamiento max.
186    #[test]
187    fn fuente_monotona_una_epoca_es_ok() {
188        let mut a = FencedCell::new(7, 50);
189        a.boot(); // época 1
190        a.spend(30);
191        let mut b = a.clone();
192        b.spend(40); // misma época, crece (monótono)
193
194        assert_eq!(a.merge(&b), MergeOutcome::Ok);
195        assert_eq!(a.reconciled_spent(), 70, "max por época: 30 y 40 se suman en el linaje");
196        assert_eq!(a.overspend(), 20, "70 − 50; no es un clon, es gasto real de la celda");
197    }
198
199    /// §G.4 (dientes) — el clon **falla ruidosamente**: nunca es un `Ok` silencioso.
200    #[test]
201    fn el_clon_nunca_pasa_como_ok() {
202        let mut c = FencedCell::new(9, 100);
203        c.epoch = 3;
204        c.spend(60);
205        let mut d = FencedCell::new(9, 100);
206        d.epoch = 5;
207        d.spend(80);
208        assert!(matches!(c.merge(&d), MergeOutcome::CloneDetected { .. }));
209    }
210
211    proptest! {
212        /// El daño de un clon está SIEMPRE acotado a una celda: dos clones, cada
213        /// uno gastando ≤ su presupuesto, dan un sobregiro ≤ una celda, y el clon
214        /// se detecta si ambos gastaron.
215        #[test]
216        fn dano_de_clon_acotado_a_una_celda(
217            budget in 1i64..200,
218            ea in 1u64..10,
219            eb in 1u64..10,
220            sa in 0i64..200,
221            sb in 0i64..200,
222        ) {
223            prop_assume!(ea != eb); // dos épocas distintas = clon potencial
224            let (sa, sb) = (sa.min(budget), sb.min(budget)); // cada clon ≤ su celda
225            let mut a = FencedCell::new(1, budget);
226            a.epoch = ea;
227            a.spend(sa);
228            let mut b = FencedCell::new(1, budget);
229            b.epoch = eb;
230            b.spend(sb);
231
232            let outcome = a.merge(&b);
233            let es_clon = matches!(outcome, MergeOutcome::CloneDetected { .. });
234            if sa > 0 && sb > 0 {
235                prop_assert!(es_clon, "dos linajes con gasto deben delatar el clon");
236            }
237            prop_assert!(a.overspend() <= budget, "daño acotado a una celda");
238        }
239    }
240}