The uniform push protocol on the complete graph #
Tgt n— a round configuration: every node ofFin npicks a target different from itself (uniformly at random, in the probabilistic layer).step I r— one push round: the informed setItogether with the targets of its members.run I l— the informed set after consuming the listlof rounds.goodRound I r— the round at least multiplies the informed set by9/8, or the informed set already exceedsn/2.goodCount I l— number of good rounds along a trajectory.
The deterministic heart of the growth phase is
pow_goodCount_mul_card_le_card_run: as long as the final informed set is
still at most n/2, the informed count is at least (9/8) ^ (good rounds).
@[implicit_reducible]
Equations
- RumorPush.instFintypeTgt n = { elems := RumorPush.instFintypeTgt._aux_1 n, complete := ⋯ }
One push round: every informed node pushes the rumor to its target.
Equations
- RumorPush.step I r = I ∪ Finset.image (fun (v : Fin n) => ↑(r v)) I
Instances For
The informed set after consuming a list of rounds.
Equations
- RumorPush.run I [] = I
- RumorPush.run I (r :: l) = RumorPush.run (RumorPush.step I r) l
Instances For
@[implicit_reducible]
Equations
The number of good rounds along a trajectory.
Equations
- RumorPush.goodCount I [] = 0
- RumorPush.goodCount I (r :: l) = (if RumorPush.goodRound I r then 1 else 0) + RumorPush.goodCount (RumorPush.step I r) l
Instances For
theorem
RumorPush.pow_goodCount_mul_card_le_card_run
{n : ℕ}
(I : Finset (Fin n))
(l : List (Tgt n))
(h : 2 * (run I l).card ≤ n)
:
Deterministic growth: if the informed set never exceeded n/2 (which by
monotonicity is implied by the final informed set being ≤ n/2), each good
round multiplied its size by 9/8.