Documentation

RumorSpread.PullModel

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:

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 #

def RumorPush.pullStep {n : ℕ} (I : Finset (Fin n)) (r : Tgt n) :

One PULL round [KSSV00, §1.2 and §2]: every node v calls r v, and an uninformed caller becomes informed if its callee is informed.

Equations
Instances For
    def RumorPush.pullRun {n : ℕ} (I : Finset (Fin n)) (l : List (Tgt n)) :

    The informed set after consuming the list l of PULL rounds (head first), starting from the informed set I.

    Equations
    Instances For
      def RumorPush.pushPullStep {n : ℕ} (I : Finset (Fin n)) (r : Tgt n) :

      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
      Instances For
        def RumorPush.pushPullRun {n : ℕ} (I : Finset (Fin n)) (l : List (Tgt n)) :

        The informed set after consuming the list l of PUSH–PULL rounds (head first), starting from the informed set I.

        Equations
        Instances For
          noncomputable def RumorPush.prPullNotAllInformed (n : ℕ) (v₀ : Fin n) (T : ℕ) :

          Probability that not all nodes are informed after T rounds of PULL, starting from the single informed node v₀.

          Equations
          Instances For
            noncomputable def RumorPush.prPushPullNotAllInformed (n : ℕ) (v₀ : Fin n) (T : ℕ) :

            Probability that not all nodes are informed after T rounds of PUSH–PULL, starting from the single informed node v₀.

            Equations
            Instances For

              Basic properties of the steps #

              theorem RumorPush.mem_pullStep {n : ℕ} {I : Finset (Fin n)} {r : Tgt n} {v : Fin n} :
              v ∈ pullStep I r ↔ v ∈ I ∨ ↑(r v) ∈ I
              theorem RumorPush.mem_pushPullStep {n : ℕ} {I : Finset (Fin n)} {r : Tgt n} {v : Fin n} :
              theorem RumorPush.subset_pullStep {n : ℕ} (I : Finset (Fin n)) (r : Tgt n) :
              I ⊆ pullStep I r
              theorem RumorPush.step_subset_pushPullStep {n : ℕ} (I : Finset (Fin n)) (r : Tgt n) :
              step I r ⊆ pushPullStep I r
              theorem RumorPush.subset_pushPullStep {n : ℕ} (I : Finset (Fin n)) (r : Tgt n) :
              I ⊆ pushPullStep I r
              theorem RumorPush.step_mono {n : ℕ} (r : Tgt n) :
              Monotone fun (I : Finset (Fin n)) => step I r
              theorem RumorPush.pullStep_mono {n : ℕ} (r : Tgt n) :
              Monotone fun (I : Finset (Fin n)) => pullStep I r
              theorem RumorPush.pushPullStep_mono {n : ℕ} (r : Tgt n) :
              Monotone fun (I : Finset (Fin n)) => pushPullStep I r
              theorem RumorPush.run_eq_foldl {n : ℕ} (I : Finset (Fin n)) (l : List (Tgt n)) :

              The PUSH trajectory run is the List.foldl of step.

              theorem RumorPush.run_subset_pushPullRun {n : ℕ} (I : Finset (Fin n)) (l : List (Tgt n)) :
              run I l ⊆ pushPullRun I l

              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.

              theorem RumorPush.pullRun_subset_pushPullRun {n : ℕ} (I : Finset (Fin n)) (l : List (Tgt n)) :
              pullRun I l ⊆ pushPullRun I l

              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.