Documentation

RumorSpread.Model

The uniform push protocol on the complete graph #

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).

A round configuration: every node picks a target different from itself.

Equations
Instances For
    @[implicit_reducible]
    Equations
    theorem RumorPush.tgt_nonempty {n : ℕ} (hn : 2 ≤ n) :
    def RumorPush.step {n : ℕ} (I : Finset (Fin n)) (r : Tgt n) :

    One push round: every informed node pushes the rumor to its target.

    Equations
    Instances For
      theorem RumorPush.subset_step {n : ℕ} (I : Finset (Fin n)) (r : Tgt n) :
      I ⊆ step I r
      theorem RumorPush.card_le_card_step {n : ℕ} (I : Finset (Fin n)) (r : Tgt n) :
      I.card ≤ (step I r).card
      theorem RumorPush.card_step_le {n : ℕ} (I : Finset (Fin n)) (r : Tgt n) :
      (step I r).card ≤ 2 * I.card
      theorem RumorPush.mem_step {n : ℕ} {I : Finset (Fin n)} {r : Tgt n} {u : Fin n} :
      u ∈ step I r ↔ u ∈ I ∨ ∃ v ∈ I, ↑(r v) = u
      def RumorPush.run {n : ℕ} (I : Finset (Fin n)) :
      List (Tgt n) → Finset (Fin n)

      The informed set after consuming a list of rounds.

      Equations
      Instances For
        @[simp]
        theorem RumorPush.run_nil {n : ℕ} (I : Finset (Fin n)) :
        run I [] = I
        @[simp]
        theorem RumorPush.run_cons {n : ℕ} (I : Finset (Fin n)) (r : Tgt n) (l : List (Tgt n)) :
        run I (r :: l) = run (step I r) l
        theorem RumorPush.subset_run {n : ℕ} (I : Finset (Fin n)) (l : List (Tgt n)) :
        I ⊆ run I l
        theorem RumorPush.run_append {n : ℕ} (I : Finset (Fin n)) (l₁ l₂ : List (Tgt n)) :
        run I (l₁ ++ l₂) = run (run I l₁) l₂
        def RumorPush.goodRound {n : ℕ} (I : Finset (Fin n)) (r : Tgt n) :

        A round is good if it grows the informed set by a factor ≥ 9/8, or if the informed set already exceeds n/2.

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

          The number of good rounds along a trajectory.

          Equations
          Instances For
            @[simp]
            theorem RumorPush.goodCount_nil {n : ℕ} (I : Finset (Fin n)) :
            theorem RumorPush.goodCount_cons {n : ℕ} (I : Finset (Fin n)) (r : Tgt n) (l : List (Tgt n)) :
            goodCount I (r :: l) = (if goodRound I r then 1 else 0) + goodCount (step I r) l
            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) :
            (9 / 8) ^ goodCount I l * ↑I.card ≤ ↑(run I l).card

            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.