A theoretical framework for analysis of communication pathways in random networks

Gossip algorithms are used to distribute packets in different networks such as P2P networks, wireless ad-hoc networks and sensor networks. These algorithms are more applicable when little information is available about the structure of the network. In this paper we present a strategy based on gossip algorithm to maximize the aggregate throughput in an all to all communication network. All of the nodes in this design, attempt to send a packet to other nodes. We present the aggregate throughput as a function of basic parameters in gossip algorithms by setting up a connection between the gossip algorithm and percolation theory. Then we apply this function to optimize the main parameters of the algorithm. We report simulation results for a simplified model of gossip algorithm using an exponential random network.