Minimum-Cost First-Push-Then-Pull Gossip Algorithm
In this paper, the authors study the communication overhead of gossip-based information dissemination algorithms. Among basic variants of gossip algorithm push is most efficient in the early rounds while, in contrast, pull becomes more efficient in the later rounds. Therefore, a cost-efficient gossip algorithm needs to combine the advantages of push and pull algorithms. One possible approach is to begin with push algorithm and then at some point switch to pull algorithm. They analyze the effect of transition round from push to pull on the communication cost of gossip algorithm. They use simple deterministic difference equations to approximately model the message propagation throughout the network for both push and pull algorithms and derive closed form solution for pull model.