Lemma 1 (Dependency chaining) — δ̃_{s,t}((s_1,…,s_k)) = δ_{s,t}(s_1)·δ̃_{s_1,t}((s_2,…,s_k))
ProvedRoutingBC.Chaining.dependency_chainingLet 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 nodes and , , an ordered sequence of nodes. Then the probability that a packet sent from to passes through all nodes of in the given order factors as
Here is the probability that a packet from to passes through , and is the sequence dependency for packets with source .
The lemma says that once a packet has reached , its further path does not depend on where it came from. Iterating it gives the product formula (16) and, after summing over sources, the target dependency chain (17).
Formalization Note. For the right-hand side is , where the dependency on the empty sequence is the total route probability. No distinctness of the is assumed, as on the page; consecutive repetitions are collapsed by the definition of . The hypothesis that non-target nodes forward with total probability one is implicit in the paper and is needed: if packets could be dropped after , the left side would not count them while would. Source-obliviousness is the paper's standing assumption of Section 5.
import Mathlib import Definitions.Def_RoutingBC_Chaining_Routing
namespace RoutingBC.Chaining
theorem dependency_chaining {V : Type*} [Fintype V] [DecidableEq V]
(R : V → V → V → V → ℝ) (hR : IsRoutingScheme R) (hobl : IsSourceOblivious R)
(s t : V) (hst : s ≠ t) (s₁ : V) (rest : List V) :
seqDelta R s t (s₁ :: rest) = delta R s t s₁ * seqDelta R s₁ t rest := by sorry
end RoutingBC.Chaining
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.