Minimum-cost First-Push-Then-Pull gossip algorithm

In this paper, we 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. We analyze the effect of transition round from push to pull on the communication cost of gossip algorithm. We 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. We then present our First-Push-Then-Pull (FPTP) gossip algorithm and obtain the optimum round to transition from push to pull. We show that, in a fully connected network, normalized communication cost is minimized to approximately a constant (≈2.6 transmissions/message/node) when the transition round is Round(log N). Furthermore, we extend our results to networks with limited connectivity/cooperation and show that although the communication overhead increases moderately as a function of connection probability, it still remains approximately constant. To validate our results we test our algorithm in mobile ad-hoc network (MANET) environment using random-waypoint mobility model and show that the simulation results closely follow our analysis.