Documentation

Epidemics.Revisited.ProtocolsDefs

The push, pull and push–pull protocols on the complete graph (EPI-8, definitions) #

In one round every node calls a node chosen uniformly at random among all n nodes, independently; following the convention of Doerr and Kostrygin for complete graphs, a node may call itself. The calls of a round are a uniform function c : Fin n → Fin n (calls n), and each protocol is the image of calls n under a deterministic round map.

noncomputable def Epidemics.Revisited.calls (n : ℕ) :

The calls of one round: a uniform function Fin n → Fin n (node v calls c v). The function type is nonempty for every n (it contains the identity).

Equations
Instances For
    def Epidemics.Revisited.pushRound {n : ℕ} (S : Finset (Fin n)) (c : Fin n → Fin n) :

    Push: the informed nodes S send the rumor to the nodes they call.

    Equations
    Instances For
      def Epidemics.Revisited.pullRound {n : ℕ} (S : Finset (Fin n)) (c : Fin n → Fin n) :

      Pull: the nodes that call an informed node become informed.

      Equations
      Instances For
        def Epidemics.Revisited.pushPullRound {n : ℕ} (S : Finset (Fin n)) (c : Fin n → Fin n) :

        Push–pull: a node becomes informed if it calls an informed node or is called by one.

        Equations
        Instances For
          noncomputable def Epidemics.Revisited.push (n : ℕ) :

          The push protocol on the complete graph K_n (with self-calls).

          Equations
          Instances For
            noncomputable def Epidemics.Revisited.pull (n : ℕ) :

            The pull protocol on the complete graph K_n (with self-calls).

            Equations
            Instances For
              noncomputable def Epidemics.Revisited.pushPull (n : ℕ) :

              The push–pull protocol on the complete graph K_n (with self-calls).

              Equations
              Instances For