The Performance of Multimessage Algebraic Gossip in a Random Geometric Graph

Gossip algorithm has been widely regarded as a simple and efficient method to improve quality of service (QoS) in large-scale network which requires rapid information dissemination. In this paper, information dissemination based on algebraic gossip in a random geometric graph (RGG) is considered. The n nodes only have knowledge about their own contents. In every time slot, each node communicates with a neighbor partner chosen randomly. The goal is to disseminate all of the messages rapidly among the nodes. We show that the gain of the convergence time is O n1/2 log ε-1/ log1/2 n with network coding. Simulation results show that these bounds are valid for the random geometric graph and demonstrate that network coding significantly improves the bounds with the number of users increasing. © 2013 Gang Wang et al.