tawasuyu/hifas

1//! `router` — ruteo de presupuesto por el grafo (T9b, §C).
2//!
3//! Cierre de arco honesto: el Laplaciano lineal que en el MVP era un **detector
4//! con falso-positivo** (`H¹ = β₁`) reaparece aquí como un **ruteador de
5//! presupuesto legítimo**. Misma máquina, problema correcto — no detectar
6//! conflictos post-hoc, sino repartir derechos proactivamente sobre el grafo.
7//!
8//! - **Presupuesto** = una 0-cocadena `b` sobre los vértices, con `Σ b_i ≤ S`.
9//! - **Rebalanceo** = un flujo (1-cocadena) que mueve presupuesto por las aristas
10//!   **conservando el total** (`Σ b` invariante ⟹ el certificado se preserva).
11//! - **El Laplaciano rutea**: `diffuse` suaviza el presupuesto (paso de calor,
12//!   reduce la varianza); `rebalance_to` localiza el flujo mínimo que repone a
13//!   una réplica seca desde vecinos con excedente — edge-local, no consenso global.
14//!
15//! Para presupuesto **escalar** basta el Laplaciano de grafo ordinario. El
16//! Laplaciano de haces (Hansen–Ghrist) solo hace falta si los presupuestos son
17//! vectoriales (multi-recurso) — ver TODO en `diffuse` y §H de `T9.md`.
18
19use crate::escrow::Budget;
20use crate::nerve::Nerve;
21
22/// Resultado de un intento de rebalanceo (T10b, §D).
23#[derive(Debug, Clone, PartialEq, Eq)]
24pub enum RebalanceResult {
25    /// Se repuso el déficit; flujo edge-local usado `(desde, hacia, monto)`.
26    Routed {
27        /// Los movimientos aplicados (conservan `Σ b`).
28        edges: Vec<(usize, usize, i64)>,
29    },
30    /// Sin ruta a excedente (partición): **no se movió nada**. Fail-safe arriba.
31    Unreachable,
32}
33
34/// Resultado de un gasto guardado por el presupuesto (T10b, §D/§F.4).
35#[derive(Debug, Clone, Copy, PartialEq, Eq)]
36pub enum SpendOutcome {
37    /// Se gastó el monto pedido (local, o tras un rebalanceo exitoso).
38    Spent,
39    /// Sin ruta al presupuesto: **rechazado, fail-safe**. La réplica puede gastar
40    /// como mucho `spendable` (su presupuesto local) sin sobregirar ni colgarse.
41    Rejected {
42        /// Lo máximo que la réplica puede gastar localmente ahora.
43        spendable: i64,
44    },
45}
46
47/// Rutea un presupuesto mutable sobre el grafo del nervio.
48pub struct BudgetRouter<'a> {
49    nerve: &'a Nerve,
50    budget: &'a mut Budget,
51}
52
53impl<'a> BudgetRouter<'a> {
54    /// Envuelve un nervio y un presupuesto para rutearlo.
55    pub fn new(nerve: &'a Nerve, budget: &'a mut Budget) -> Self {
56        Self { nerve, budget }
57    }
58
59    /// Total de presupuesto `Σ b` (la cantidad conservada; el certificado de §B).
60    pub fn total(&self) -> i64 {
61        self.budget.per_replica.iter().sum()
62    }
63
64    /// Flujo **mínimo** que repone `deficit` a la réplica `r` desde sus vecinas
65    /// con excedente. **Transaccional** (T10b): si las vecinas directas cubren el
66    /// déficit, aplica el flujo y devuelve `Routed`; si no lo cubren (partición),
67    /// **no mueve nada** y devuelve `Unreachable` — nunca deja un estado a medias
68    /// ni bloquea. Conserva `Σ b` y solo toca aristas **adyacentes a `r`**.
69    ///
70    /// Limitación honesta (§D): es edge-local a las vecinas directas. Un nodo cuyo
71    /// componente tiene excedente pero no en sus vecinas inmediatas recibe
72    /// `Unreachable`; `diffuse` lo mitiga repartiendo antes, no lo elimina.
73    pub fn rebalance_to(&mut self, r: usize, deficit: i64) -> RebalanceResult {
74        let need = deficit.max(0);
75        if need == 0 {
76            return RebalanceResult::Routed { edges: Vec::new() };
77        }
78        let neighbors = self.nerve.neighbors(r);
79        let surplus: i64 = neighbors.iter().map(|&j| self.budget.per_replica[j].max(0)).sum();
80        if surplus < need {
81            return RebalanceResult::Unreachable; // fail-safe: no aplica nada
82        }
83
84        let mut moves = Vec::new();
85        let mut rem = need;
86        for j in neighbors {
87            if rem == 0 {
88                break;
89            }
90            let avail = self.budget.per_replica[j].max(0);
91            let amount = avail.min(rem);
92            if amount > 0 {
93                self.budget.per_replica[j] -= amount;
94                self.budget.per_replica[r] += amount;
95                moves.push((j, r, amount));
96                rem -= amount;
97            }
98        }
99        RebalanceResult::Routed { edges: moves }
100    }
101
102    /// Gasto guardado por el presupuesto, con rebalanceo y **fail-safe** (§D/§F.4):
103    /// si cabe local, gasta; si no, intenta reponer desde vecinas; si no hay ruta
104    /// (`Unreachable`), **rechaza** y reporta cuánto puede gastar localmente. Nunca
105    /// sobregira ni cuelga.
106    pub fn spend_with_rebalance(&mut self, r: usize, amount: i64) -> SpendOutcome {
107        let local = self.budget.per_replica[r];
108        if amount <= local {
109            self.budget.per_replica[r] -= amount;
110            return SpendOutcome::Spent;
111        }
112        match self.rebalance_to(r, amount - local) {
113            RebalanceResult::Routed { .. } => {
114                self.budget.per_replica[r] -= amount; // el rebalanceo dejó lo justo
115                SpendOutcome::Spent
116            }
117            RebalanceResult::Unreachable => SpendOutcome::Rejected {
118                spendable: self.budget.per_replica[r].max(0),
119            },
120        }
121    }
122
123    /// Un paso de difusión de Laplaciano que **suaviza** el presupuesto
124    /// conservando `Σ b`. Por cada arista mueve la mitad (entera) de la diferencia
125    /// del extremo alto al bajo: un promediado por pares que nunca aumenta la
126    /// varianza y mantiene los presupuestos no negativos.
127    ///
128    /// TODO(multi-recurso): para presupuestos vectoriales, sustituir este paso
129    /// escalar por el Laplaciano de haces (§C, §H de `T9.md`).
130    pub fn diffuse(&mut self) {
131        for (a, b) in self.nerve.edges() {
132            let d = self.budget.per_replica[a] - self.budget.per_replica[b];
133            let m = d / 2; // trunca hacia cero; mueve del alto al bajo en ambos signos
134            self.budget.per_replica[a] -= m;
135            self.budget.per_replica[b] += m;
136        }
137    }
138}
139
140#[cfg(test)]
141mod tests {
142    use super::*;
143    use proptest::prelude::*;
144
145    fn suma(b: &Budget) -> i64 {
146        b.per_replica.iter().sum()
147    }
148
149    /// Σ b² es un proxy de la varianza cuando `Σ b` está fijo: menor Σ b² ⟺ menor
150    /// varianza. Lo usamos para comprobar que `diffuse` no la aumenta.
151    fn suma_de_cuadrados(b: &Budget) -> i128 {
152        b.per_replica.iter().map(|&x| (x as i128) * (x as i128)).sum()
153    }
154
155    /// Extrae las aristas de un `Routed`, o falla si fue `Unreachable`.
156    fn routed(res: RebalanceResult) -> Vec<(usize, usize, i64)> {
157        match res {
158            RebalanceResult::Routed { edges } => edges,
159            RebalanceResult::Unreachable => panic!("debía rutear, no Unreachable"),
160        }
161    }
162
163    #[test]
164    fn rebalanceo_conserva_el_total_y_repone() {
165        // Camino 0—1—2; la réplica 1 está seca y pide 8.
166        let nerve = Nerve::from_edges(3, &[(0, 1), (1, 2)]);
167        let mut budget = Budget::new(vec![5, 0, 5]);
168        let antes = suma(&budget);
169
170        let moves = routed(BudgetRouter::new(&nerve, &mut budget).rebalance_to(1, 8));
171        assert_eq!(suma(&budget), antes, "el rebalanceo conserva Σ b");
172        assert_eq!(budget.remaining(1), 8, "la réplica seca queda repuesta");
173        // Solo movió desde vecinas de 1 (0 y 2), nunca desde una no vecina.
174        for (from, to, _) in &moves {
175            assert_eq!(*to, 1);
176            assert!(nerve.neighbors(1).contains(from), "movió desde una no vecina");
177        }
178    }
179
180    #[test]
181    fn rebalanceo_solo_toca_vecinas() {
182        // Estrella: centro 0 con hojas 1,2,3. La hoja 3 NO es vecina de 1.
183        let nerve = Nerve::from_edges(4, &[(0, 1), (0, 2), (0, 3)]);
184        let mut budget = Budget::new(vec![10, 0, 0, 0]);
185        let moves = routed(BudgetRouter::new(&nerve, &mut budget).rebalance_to(1, 5));
186        // La única vecina de 1 es 0; el flujo viene solo de ahí.
187        for (from, _, _) in &moves {
188            assert_eq!(*from, 0, "una hoja no puede reponer a otra hoja directamente");
189        }
190        assert_eq!(budget.remaining(1), 5);
191        assert_eq!(budget.remaining(0), 5);
192    }
193
194    /// **§F.4 — partición sin ruta ⟹ fail-safe.** El 60/60 particionado con
195    /// `[50,50]`: la réplica 0 aislada intenta retirar 60 → `rebalance_to` da
196    /// `Unreachable` (no mueve nada), el gasto se **rechaza** y a lo sumo puede
197    /// gastar sus 50 locales. Nunca sobregira, nunca cuelga.
198    #[test]
199    fn particion_sin_ruta_es_fail_safe() {
200        let nerve = Nerve::from_edges(2, &[]); // sin aristas: partición total
201        let mut budget = Budget::new(vec![50, 50]);
202        let antes = suma(&budget);
203        let mut router = BudgetRouter::new(&nerve, &mut budget);
204
205        // El rebalanceo no tiene ruta y no mueve nada.
206        assert_eq!(router.rebalance_to(0, 10), RebalanceResult::Unreachable);
207        // El gasto de 60 se rechaza; puede gastar hasta 50.
208        assert_eq!(router.spend_with_rebalance(0, 60), SpendOutcome::Rejected { spendable: 50 });
209        assert_eq!(suma(&budget), antes, "un rechazo no toca el presupuesto");
210
211        // Gastar los 50 locales sí es seguro (valor = 100 − 50 = 50 ≥ 0).
212        assert_eq!(
213            BudgetRouter::new(&nerve, &mut budget).spend_with_rebalance(0, 50),
214            SpendOutcome::Spent
215        );
216        assert_eq!(budget.remaining(0), 0);
217    }
218
219    /// Con ruta, el gasto que excede lo local se cubre por rebalanceo y procede.
220    #[test]
221    fn gasto_con_ruta_se_cubre_por_rebalanceo() {
222        let nerve = Nerve::from_edges(2, &[(0, 1)]);
223        let mut budget = Budget::new(vec![50, 50]);
224        // La réplica 0 retira 60: 50 locales + 10 repuestos desde 1.
225        assert_eq!(
226            BudgetRouter::new(&nerve, &mut budget).spend_with_rebalance(0, 60),
227            SpendOutcome::Spent
228        );
229        assert_eq!(budget.remaining(0), 0);
230        assert_eq!(budget.remaining(1), 40);
231        assert_eq!(suma(&budget), 40, "gastó 60 de los 100: Σ b = 40");
232    }
233
234    #[test]
235    fn diffuse_no_aumenta_varianza_y_conserva_total() {
236        let nerve = Nerve::from_edges(4, &[(0, 1), (1, 2), (2, 3), (3, 0)]);
237        let mut budget = Budget::new(vec![100, 0, 0, 0]);
238        let antes_sum = suma(&budget);
239        let antes_var = suma_de_cuadrados(&budget);
240
241        BudgetRouter::new(&nerve, &mut budget).diffuse();
242        assert_eq!(suma(&budget), antes_sum, "diffuse conserva Σ b");
243        assert!(suma_de_cuadrados(&budget) <= antes_var, "diffuse no aumenta la varianza");
244        assert!(budget.per_replica.iter().all(|&b| b >= 0), "sigue no negativo");
245    }
246
247    fn nerve_y_budget() -> impl Strategy<Value = (usize, Vec<(usize, usize)>, Vec<i64>)> {
248        (2usize..=6).prop_flat_map(|n| {
249            let arista = (0..n, 0..n).prop_filter("sin lazos", |(a, b)| a != b);
250            let edges = prop::collection::vec(arista, 0..10);
251            let presupuestos = prop::collection::vec(0i64..100, n);
252            (Just(n), edges, presupuestos)
253        })
254    }
255
256    proptest! {
257        /// Conservación e idempotencia del certificado: ni `rebalance_to` ni
258        /// `diffuse` cambian `Σ b`, y `diffuse` nunca aumenta la varianza.
259        #[test]
260        fn ruteo_conserva_total((n, edges, pres) in nerve_y_budget(), objetivo in 0usize..6) {
261            let nerve = Nerve::from_edges(n, &edges);
262            let mut budget = Budget::new(pres);
263            let total = budget.per_replica.iter().sum::<i64>();
264
265            let r = objetivo % n;
266            let res = BudgetRouter::new(&nerve, &mut budget).rebalance_to(r, 30);
267            // Conserva Σ b tanto si rutea (mueve dentro) como si es Unreachable (no mueve).
268            prop_assert_eq!(budget.per_replica.iter().sum::<i64>(), total, "rebalance conserva");
269            if let RebalanceResult::Routed { edges } = res {
270                // Localización: todo movimiento entra a r desde una vecina suya.
271                for (from, to, amount) in &edges {
272                    prop_assert_eq!(*to, r);
273                    prop_assert!(*amount > 0);
274                    prop_assert!(nerve.neighbors(r).contains(from));
275                }
276            }
277
278            let var_antes = suma_de_cuadrados(&budget);
279            BudgetRouter::new(&nerve, &mut budget).diffuse();
280            prop_assert_eq!(budget.per_replica.iter().sum::<i64>(), total, "diffuse conserva");
281            prop_assert!(suma_de_cuadrados(&budget) <= var_antes, "diffuse no aumenta varianza");
282            prop_assert!(budget.per_replica.iter().all(|&b| b >= 0));
283        }
284    }
285}