Proposition 1 — at most one order of a node set is traversed with positive probability
ProvedRoutingBC.Chaining.order_uniqueLet be a loop-free routing scheme on a finite node set (nonnegative, total forwarding probability one at every non-target node, the target forwarding nothing), whose decisions may depend on both the source and the target . Fix , a set of nodes , and two orderings and of (each lists every element of exactly once). If
then . Here is the probability that a packet from to passes through the nodes of in the order of .
In words: a packet from to can traverse a given set of nodes in at most one order with positive probability. The paper uses this to make the order of well defined in the proof of Lemma 1.
Formalization Note. The set and its two permutations are encoded as two repetition-free lists that are permutations of each other. The sentence before the proposition (p. 14) says ""; the proposition itself has , which is what is stated. Source-obliviousness is not assumed. Total forwarding probability one and the silent target are the mission's standing assumptions (see the definitions file).
import Mathlib import Definitions.Def_RoutingBC_Chaining_Routing
namespace RoutingBC.Chaining
theorem order_unique {V : Type*} [Fintype V] [DecidableEq V]
(R : V → V → V → V → ℝ) (hR : IsRoutingScheme R) (s t : V) (L₁ L₂ : List V)
(h₁ : L₁.Nodup) (h₂ : L₂.Nodup) (hperm : L₁.Perm L₂)
(hpos₁ : 0 < seqDelta R s t L₁) (hpos₂ : 0 < seqDelta R s t L₂) :
L₁ = L₂ := by sorry
end RoutingBC.Chaining
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.