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.
Push: the informed nodes S send the rumor to the nodes they call.
Equations
- Epidemics.Revisited.pushRound S c = S ∪ Finset.image c S
Instances For
The push protocol on the complete graph K_n (with self-calls).
Equations
- Epidemics.Revisited.push n = { K := fun (S : Finset (Fin n)) => (Epidemics.Revisited.calls n).map (Epidemics.Revisited.pushRound S), mono := ⋯ }
Instances For
The pull protocol on the complete graph K_n (with self-calls).
Equations
- Epidemics.Revisited.pull n = { K := fun (S : Finset (Fin n)) => (Epidemics.Revisited.calls n).map (Epidemics.Revisited.pullRound S), mono := ⋯ }
Instances For
The push–pull protocol on the complete graph K_n (with self-calls).
Equations
- Epidemics.Revisited.pushPull n = { K := fun (S : Finset (Fin n)) => (Epidemics.Revisited.calls n).map (Epidemics.Revisited.pushPullRound S), mono := ⋯ }