Sequence RBC = Σ_t δ_{•,t}(s_1)ρ_{s_1}·∏ δ_{s_i,t}(s_{i+1})ρ_{s_{i+1}} (Section 5.2, Algorithm 6)
ProvedRoutingBC.Chaining.sequence_rbc_eq_sum_chained_dependenciesLet be a loop-free, source-oblivious routing scheme on a finite node set in which every node other than the target forwards with total probability one and the target forwards nothing. Let be a traffic matrix, sampling rates, and , , a sequence of distinct nodes. Then the routing betweenness centrality of the sequence,
equals
where is the target dependency and the pairwise dependency.
The left side is the expected number of packets sampled by all monitors of in order (Eq. (4)); the right side is the value returned by Algorithm 6, which needs only the precomputed target dependencies of and pairwise dependencies between consecutive members of . The sum on the left runs over all pairs , endpoints included.
Formalization Note. Algorithm 6 indexes the sequence from (); here it is as in Lemma 1, and the product runs over the consecutive pairs of . Distinctness of is the paper's assumption for Eq. (4). The running time is not formalized; only the identity is. No sign condition on is assumed; the bounds are the page's.
import Mathlib import Definitions.Def_RoutingBC_Chaining_Routing
namespace RoutingBC.Chaining
theorem sequence_rbc_eq_sum_chained_dependencies {V : Type*} [Fintype V] [DecidableEq V]
(R : V → V → V → V → ℝ) (hR : IsRoutingScheme R) (hobl : IsSourceOblivious R)
(T : V → V → ℝ) (ρ : V → ℝ) (hρ : ∀ v, 0 ≤ ρ v ∧ ρ v ≤ 1)
(s₁ : V) (rest : List V) (hS : (s₁ :: rest).Nodup) :
seqRBC R T ρ (s₁ :: rest) =
∑ t, targetDelta R T t s₁ * ρ s₁ *
(((s₁ :: rest).zip rest).map (fun ab => delta R ab.1 t ab.2 * ρ ab.2)).prod := by sorry
end RoutingBC.Chaining
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.