|
Minimum-Cost First-Push-Then-Pull Gossip Algorithm
November 2011
Ali Saidi, Advanced Infrastructure Design
Mojdeh Mohtashemi, The MITRE Corporation
ABSTRACT
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 derive 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.
Additional Search Keywords
Gossip algorithms, Push, Pull, Mobile networks
|
