PULL and PUSH–PULL rumor spreading on the complete graph #
The random phone call model of Karp, Schindelhauer, Shenker and Vöcking [KSSV00, §1.2]: in
every round each node v calls a random partner r v, and the rumor may travel along the call
in either direction. We reuse the round configurations Tgt n of the PUSH development
(Model.lean: every node calls a uniformly random other node, whereas [KSSV00] and [FG85]
allow self-calls), so that the three protocols are driven by the same random calls:
- PUSH (
step, inModel.lean): an informed caller informs its callee; - PULL (
pullStep): an uninformed caller learns the rumor if its callee is informed; - PUSH–PULL (
pushPullStep): the rumor is sent in both directions along every call [KSSV00, §2].
pullRun and pushPullRun consume a list of rounds head first (as run does), and
prPullNotAllInformed, prPushPullNotAllInformed are the probabilities that some node is still
uninformed after T i.i.d. uniform rounds started from a single informed node, in the same
expList form as prNotAllInformed for PUSH.
Because the three steps read the same calls, PUSH–PULL dominates PUSH and PULL pathwise
(run_subset_pushPullRun, pullRun_subset_pushPullRun).
References #
- [KSSV00] R. Karp, C. Schindelhauer, S. Shenker, B. Vöcking, Randomized rumor spreading, FOCS 2000.
- [FG85] A. M. Frieze, G. R. Grimmett, The shortest-path problem for graphs with random arc-lengths, Discrete Appl. Math. 10 (1985).
The informed set after consuming the list l of PULL rounds (head first), starting from
the informed set I.
Equations
Instances For
One PUSH–PULL round [KSSV00, §2]: along every call v → r v the rumor is transmitted in
both directions, so the new informed set is the union of the PUSH round step and the PULL
round pullStep driven by the same calls.
Equations
- RumorPush.pushPullStep I r = RumorPush.step I r ∪ RumorPush.pullStep I r
Instances For
The informed set after consuming the list l of PUSH–PULL rounds (head first), starting
from the informed set I.
Equations
Instances For
Probability that not all nodes are informed after T rounds of PULL, starting from the
single informed node v₀.
Equations
- RumorPush.prPullNotAllInformed n v₀ T = Dynamics.expList (RumorPush.Tgt n) T fun (l : List (RumorPush.Tgt n)) => if RumorPush.pullRun {v₀} l = Finset.univ then 0 else 1
Instances For
Probability that not all nodes are informed after T rounds of PUSH–PULL, starting from
the single informed node v₀.
Equations
- RumorPush.prPushPullNotAllInformed n v₀ T = Dynamics.expList (RumorPush.Tgt n) T fun (l : List (RumorPush.Tgt n)) => if RumorPush.pushPullRun {v₀} l = Finset.univ then 0 else 1
Instances For
Basic properties of the steps #
The PUSH trajectory run is the List.foldl of step.
PUSH–PULL dominates PUSH pathwise: driven by the same calls, PUSH–PULL has informed at least the nodes informed by PUSH after every prefix of rounds.
PUSH–PULL dominates PULL pathwise: driven by the same calls, PUSH–PULL has informed at least the nodes informed by PULL after every prefix of rounds.