tawasuyu/hifas

1//! `escrow` — evitación de coordinación por presupuestos (T9, §B).
2//!
3//! Método de escrow (O'Neil 1986) como Bounded Counter CRDT (Balegas et al.,
4//! SRDS 2015). Para un invariante global `valor ≥ K`:
5//!
6//! 1. El *slack* `S = valor − K` es lo gastable sin romper `I`.
7//! 2. Se **reparte** `S` en presupuestos por réplica `b_i` con `Σ b_i ≤ S`.
8//! 3. Mientras `r_i` tenga presupuesto, **gasta localmente sin coordinar** — y es
9//!    correcto **incluso particionada**, porque `b_i` es suyo.
10//! 4. La única coordinación es el **rebalanceo edge-local** al agotar `b_i` (T9b).
11//!
12//! **El certificado.** Si `spent_i ≤ b_i` en cada réplica, entonces
13//! `valor = inicial − Σ spent_i ≥ inicial − Σ b_i ≥ inicial − S = K`, para **toda
14//! ejecución, orden y partición**. No se descubre tarde: se garantiza por
15//! construcción. Eso es evitación real, no la detección reactiva de T8 (§A).
16//!
17//! **Honestidad (§B):** escrow no vence a CALM; *transforma* la operación
18//! ("retirar sin límite" → "retirar dentro de presupuesto") para que sea
19//! I-confluente, al costo de un rebalanceo ocasional.
20
21use crate::invariant::GlobalInvariant;
22
23/// El resultado de intentar gastar localmente.
24#[derive(Debug, Clone, Copy, PartialEq, Eq)]
25pub enum SpendResult {
26    /// Dentro de presupuesto: gasto local, **cero coordinación**.
27    Local,
28    /// Presupuesto agotado: hace falta rebalanceo edge-local (T9b).
29    NeedsRebalance {
30        /// Cuánto falta para cubrir el gasto pedido.
31        deficit: i64,
32    },
33}
34
35/// El presupuesto repartido: la 0-cocadena `b` sobre las réplicas.
36#[derive(Debug, Clone, PartialEq, Eq)]
37pub struct Budget {
38    /// Presupuesto restante por réplica.
39    pub per_replica: Vec<i64>,
40}
41
42impl Budget {
43    /// Presupuesto a partir de un reparto explícito.
44    pub fn new(per_replica: Vec<i64>) -> Self {
45        Self { per_replica }
46    }
47
48    /// Reparte el `slack` en `n` presupuestos proporcionales a `weights`, con
49    /// división entera para garantizar `Σ b_i ≤ slack` (reparto siempre válido).
50    pub fn split(inv: &GlobalInvariant, weights: &[u64]) -> Self {
51        let s = inv.slack().max(0) as u128;
52        let total: u128 = weights.iter().map(|&w| w as u128).sum();
53        let per_replica = if total == 0 {
54            vec![0; weights.len()]
55        } else {
56            // ⌊w_i · S / total⌋ ⟹ la suma nunca excede S.
57            weights.iter().map(|&w| ((w as u128 * s) / total) as i64).collect()
58        };
59        Self { per_replica }
60    }
61
62    /// El certificado del reparto (§B): `Σ b_i ≤ slack` y todo `b_i ≥ 0`.
63    pub fn is_valid_split(&self, inv: &GlobalInvariant) -> bool {
64        self.per_replica.iter().all(|&b| b >= 0)
65            && self.per_replica.iter().sum::<i64>() <= inv.slack()
66    }
67
68    /// Presupuesto restante de la réplica `r`.
69    pub fn remaining(&self, r: usize) -> i64 {
70        self.per_replica[r]
71    }
72
73    /// Gasto local de `amount` (≥ 0) en la réplica `r`. Si cabe, descuenta y
74    /// devuelve `Local`; si no, **no gasta** y devuelve `NeedsRebalance` con el
75    /// déficit. Nunca declara "libre global" a ciegas.
76    pub fn try_spend(&mut self, r: usize, amount: i64) -> SpendResult {
77        debug_assert!(amount >= 0, "los gastos son no negativos");
78        if amount <= self.per_replica[r] {
79            self.per_replica[r] -= amount;
80            SpendResult::Local
81        } else {
82            SpendResult::NeedsRebalance {
83                deficit: amount - self.per_replica[r],
84            }
85        }
86    }
87
88    /// El valor del recurso implicado por unos gastos `spent_i` (para el
89    /// certificado): `inicial − Σ spent_i`.
90    pub fn value_after(inv: &GlobalInvariant, spent: &[i64]) -> i64 {
91        inv.initial - spent.iter().sum::<i64>()
92    }
93}
94
95/// **Presupuesto con procedencia** (T10, §C.1 — la vía Balegas): todo es monótono
96/// creciente, así que la fusión es un CRDT y **no hay carreras**. Sustituye al
97/// `Budget` mutable de T9 (`b_i` leído-y-escrito), que era seguro solo en
98/// snapshots congelados y secuenciales.
99///
100/// El presupuesto disponible es una **función derivada** de dos historiales que
101/// solo crecen: `granted[from][to]` (derechos cedidos) y `spent[i]` (gasto).
102///
103/// **El teorema (§C):** `Σ avail = Σ b0 − Σ spent`, invariante bajo cualquier
104/// entrelazado, porque cada `granted[j][i]` entra `+` en `i` y `−` en `j` y se
105/// cancela. Imposible fabricar presupuesto por fusión; imposible perderlo por un
106/// crash a medio propagar (un `grant` vive entero en `granted[from][to]`: al
107/// re-fusionar, o llegó completo o no llegó).
108#[derive(Debug, Clone, PartialEq, Eq)]
109pub struct EscrowState {
110    /// Reparto inicial (constante); `Σ b0 ≤ slack`.
111    pub b0: Vec<i64>,
112    /// `granted[from][to]`: derechos transferidos, solo crece. Fila `from`
113    /// escrita solo por la réplica `from` (single-writer ⟹ sin conflicto).
114    pub granted: Vec<Vec<i64>>,
115    /// `spent[i]`: gasto de la réplica `i`, solo crece.
116    pub spent: Vec<i64>,
117}
118
119impl EscrowState {
120    /// Estado inicial a partir de un reparto `b0` (sin transferencias ni gasto).
121    pub fn new(b0: Vec<i64>) -> Self {
122        let n = b0.len();
123        Self {
124            b0,
125            granted: vec![vec![0; n]; n],
126            spent: vec![0; n],
127        }
128    }
129
130    /// Número de réplicas.
131    pub fn replicas(&self) -> usize {
132        self.b0.len()
133    }
134
135    /// Presupuesto disponible de `i` = inicial + recibido − cedido − gastado.
136    pub fn avail(&self, i: usize) -> i64 {
137        let recibido: i64 = (0..self.replicas()).map(|j| self.granted[j][i]).sum();
138        let cedido: i64 = self.granted[i].iter().sum();
139        self.b0[i] + recibido - cedido - self.spent[i]
140    }
141
142    /// Presupuesto total disponible. Por el teorema de §C es exactamente
143    /// `Σ b0 − Σ spent` — los `granted` se cancelan y **no cambian el total**.
144    pub fn total_avail(&self) -> i64 {
145        self.b0.iter().sum::<i64>() - self.spent.iter().sum::<i64>()
146    }
147
148    /// La otra vía de calcular el total (sumando cada `avail`), que DEBE coincidir
149    /// con `total_avail`: la prueba de la cancelación de `granted`.
150    pub fn sum_avail(&self) -> i64 {
151        (0..self.replicas()).map(|i| self.avail(i)).sum()
152    }
153
154    /// La réplica `from` cede `amount` (≥0) a `to`. Guardado por su `avail` local
155    /// (single-writer): nunca cede más de lo que tiene ⟹ imposible fabricar en el
156    /// origen. Devuelve `false` si no le alcanza.
157    pub fn grant(&mut self, from: usize, to: usize, amount: i64) -> bool {
158        debug_assert!(amount >= 0);
159        if amount <= self.avail(from) {
160            self.granted[from][to] += amount;
161            true
162        } else {
163            false
164        }
165    }
166
167    /// La réplica `i` gasta `amount` (≥0) si le queda `avail`. Monótono.
168    pub fn spend(&mut self, i: usize, amount: i64) -> bool {
169        debug_assert!(amount >= 0);
170        if amount <= self.avail(i) {
171            self.spent[i] += amount;
172            true
173        } else {
174            false
175        }
176    }
177
178    /// **Fusión CRDT**: máximo componente a componente en `granted` y `spent`
179    /// (los historiales solo crecen). Conmutativa, asociativa, idempotente. No
180    /// puede subir `total_avail`: `Σ spent` solo crece ⟹ el total solo baja.
181    pub fn merge(&mut self, other: &EscrowState) {
182        debug_assert_eq!(self.b0, other.b0, "mismo reparto inicial");
183        let n = self.replicas();
184        for i in 0..n {
185            self.spent[i] = self.spent[i].max(other.spent[i]);
186            for j in 0..n {
187                self.granted[i][j] = self.granted[i][j].max(other.granted[i][j]);
188            }
189        }
190    }
191}
192
193#[cfg(test)]
194mod tests {
195    use super::*;
196    use crate::verdict::Verdict;
197    use proptest::prelude::*;
198
199    /// El caso 60/60 de T8, ahora bien tratado (§F): con presupuestos [50,50]
200    /// (reparto válido de S=100), una réplica **particionada** que intenta retirar
201    /// 60 recibe `NeedsRebalance`, NO `Local`. Muere el falso-verde del detector.
202    #[test]
203    fn t9_particionado_60_es_bloqueado_no_libre() {
204        let inv = GlobalInvariant::new(100, 0); // saldo ≥ 0, slack 100
205        let mut budget = Budget::new(vec![50, 50]);
206        assert!(budget.is_valid_split(&inv));
207
208        // La réplica 0, aislada, intenta retirar 60 (> su presupuesto de 50).
209        let res = budget.try_spend(0, 60);
210        assert_eq!(res, SpendResult::NeedsRebalance { deficit: 10 });
211        // El veredicto de escrow NO es "libre": pide rebalanceo (localizado).
212        assert!(matches!(Verdict::via_escrow(0, &res), Verdict::NeedsCoordination { .. }));
213        // Y no gastó: el presupuesto sigue intacto (el gasto queda pendiente).
214        assert_eq!(budget.remaining(0), 50);
215    }
216
217    /// Gasto dentro de presupuesto: local y descuenta.
218    #[test]
219    fn gasto_dentro_de_presupuesto_es_local() {
220        let mut budget = Budget::new(vec![50, 50]);
221        assert_eq!(budget.try_spend(0, 30), SpendResult::Local);
222        assert_eq!(budget.remaining(0), 20);
223        assert!(matches!(Verdict::via_escrow(0, &SpendResult::Local), Verdict::RunsFree));
224    }
225
226    fn split_valido(inv: &GlobalInvariant, raw: &[u64]) -> Budget {
227        let b = Budget::split(inv, raw);
228        assert!(b.is_valid_split(inv), "split debe ser válido por construcción");
229        b
230    }
231
232    proptest! {
233        /// **EL CERTIFICADO (§F, el corazón de T9a).** Para todo reparto válido y
234        /// TODA combinación de gastos dentro de presupuesto —incluidas particiones
235        /// arbitrarias y todas las réplicas gastando su máximo a la vez— el
236        /// invariante global `valor ≥ K` se preserva. Se cuantifica sobre todos
237        /// los estados alcanzables, no sobre un merge concreto.
238        #[test]
239        fn certificado_valor_nunca_baja_del_piso(
240            initial in 0i64..500,
241            floor in -100i64..100,
242            pesos in prop::collection::vec(0u64..50, 1..6),
243            gasto_raw in prop::collection::vec(0u64..600, 1..6),
244        ) {
245            prop_assume!(initial >= floor);              // slack ≥ 0
246            let inv = GlobalInvariant::new(initial, floor);
247            let budget = split_valido(&inv, &pesos);
248
249            // Gastos arbitrarios pero acotados por el presupuesto de cada réplica.
250            let spent: Vec<i64> = budget
251                .per_replica
252                .iter()
253                .zip(gasto_raw.iter().chain(std::iter::repeat(&0)))
254                .map(|(&b, &g)| (g as i64).min(b))       // spent_i ≤ b_i
255                .collect();
256
257            // El certificado: valor = inicial − Σ spent ≥ floor. Para cualquier
258            // subconjunto que sincronice (partición) el valor es aún mayor.
259            let valor = Budget::value_after(&inv, &spent);
260            prop_assert!(inv.holds(valor), "valor {} < piso {}", valor, inv.floor);
261        }
262    }
263
264    // ---- T10a: presupuesto con procedencia (EscrowState) ----
265
266    /// **El modo de fallo de §B, PREVENIDO en el origen.** `B` tiene 30. Cede 20 a
267    /// `A`; el segundo intento de ceder 20 a `C` **falla** (solo le quedan 10),
268    /// porque `grant` está guardado por el `avail` local. Nada de fabricar 20 por
269    /// una lectura-y-escritura descuidada. `Σ avail` se conserva en 30.
270    #[test]
271    fn grant_guardado_previene_la_fabricacion() {
272        let mut s = EscrowState::new(vec![0, 30, 0]);
273        assert!(s.grant(1, 0, 20), "B cede 20 a A");
274        assert!(!s.grant(1, 2, 20), "B ya no puede ceder otros 20 (solo le quedan 10)");
275        assert!(s.grant(1, 2, 10), "pero sí los 10 restantes");
276        assert_eq!(s.avail(0), 20);
277        assert_eq!(s.avail(1), 0);
278        assert_eq!(s.avail(2), 10);
279        assert_eq!(s.total_avail(), 30, "Σ avail conservado: cero fabricación");
280    }
281
282    /// Crash a mitad de transferencia: un `grant` aplicado en una copia y no
283    /// propagado, al re-fusionar tarde da el mismo estado. Ni fabrica ni pierde.
284    #[test]
285    fn crash_a_mitad_de_transferencia_es_seguro() {
286        let base = EscrowState::new(vec![30, 0]);
287        // Copia 1: B0 concede 20 a la réplica 1 (el "grant en tránsito").
288        let mut c1 = base.clone();
289        assert!(c1.grant(0, 1, 20));
290        // Copia 2 (crashea sin ver el grant): fusiona el resto tal cual.
291        let mut c2 = base.clone();
292        c2.merge(&base);
293        // El grant llega tarde: c2 re-fusiona con c1.
294        c2.merge(&c1);
295        assert_eq!(c2, c1, "el grant llega entero o no llega; nunca a medias");
296        assert_eq!(c2.total_avail(), 30);
297    }
298
299    fn escrow_st() -> impl Strategy<Value = EscrowState> {
300        (1usize..=4).prop_flat_map(|n| {
301            let b0 = prop::collection::vec(0i64..50, n);
302            let granted = prop::collection::vec(prop::collection::vec(0i64..30, n), n);
303            let spent = prop::collection::vec(0i64..30, n);
304            (b0, granted, spent).prop_map(|(b0, granted, spent)| EscrowState { b0, granted, spent })
305        })
306    }
307
308    /// Dos estados con el mismo reparto inicial (para poder fusionarlos).
309    fn par_de_escrow() -> impl Strategy<Value = (EscrowState, EscrowState)> {
310        escrow_st().prop_flat_map(|a| {
311            let n = a.replicas();
312            let granted = prop::collection::vec(prop::collection::vec(0i64..30, n), n);
313            let spent = prop::collection::vec(0i64..30, n);
314            let b0 = a.b0.clone();
315            (Just(a), (granted, spent)).prop_map(move |(a, (g, s))| {
316                let b = EscrowState { b0: b0.clone(), granted: g, spent: s };
317                (a, b)
318            })
319        })
320    }
321
322    proptest! {
323        /// **§F.1 — el total no se puede fabricar.** `Σ avail` (sumando cada réplica)
324        /// SIEMPRE es igual a `Σ b0 − Σ spent`: los `granted` se cancelan, pase lo
325        /// que pase con las transferencias. Este es el teorema que mata el §B.
326        #[test]
327        fn total_avail_es_invariante_a_los_granted(s in escrow_st()) {
328            prop_assert_eq!(s.sum_avail(), s.total_avail());
329            prop_assert_eq!(s.total_avail(), s.b0.iter().sum::<i64>() - s.spent.iter().sum::<i64>());
330        }
331
332        /// **§F.2 — `merge` es un CRDT:** conmutativo e idempotente.
333        #[test]
334        fn merge_conmutativo_e_idempotente((a, b) in par_de_escrow()) {
335            let mut ab = a.clone(); ab.merge(&b);
336            let mut ba = b.clone(); ba.merge(&a);
337            prop_assert_eq!(&ab, &ba, "merge conmutativo");
338            let mut abb = ab.clone(); abb.merge(&b);
339            prop_assert_eq!(&abb, &ab, "merge idempotente");
340        }
341
342        /// **§F.1 (fusión) — `merge` nunca sube el total.** `Σ spent` solo crece por
343        /// max ⟹ `total_avail` solo puede bajar. Imposible fabricar por fusión.
344        #[test]
345        fn merge_nunca_fabrica_presupuesto((a, b) in par_de_escrow()) {
346            let mut m = a.clone(); m.merge(&b);
347            prop_assert!(m.total_avail() <= a.total_avail());
348            prop_assert!(m.total_avail() <= b.total_avail());
349        }
350    }
351}