Gossiping in distributed systems

Abstract

Exchange of information between various nodes in a distributed network can be useful to utilize the available resources effectively. Gossiping algorithms can be used for this purpose. We begin with a survey of various gossiping schemes for different types of network topologies. Two types of gossiping techniques have traditionally been studied and used: (i) schemes in which there is an initiator to start the algorithm and (ii) sch emes without an initiator. These are again sub-divided into two classes: (i) each node knowing the entire graph of the network and (ii) each node knowing only its neighbors. In the schemes with an initiator, the leader initiates the algorithm and subsequently other nodes in the system participate in the algorithm when they are told to do so by a node which already participates in the algorithm. Assuming that each node knows only its neighbors, we propose and implement a gossiping scheme which can compromise message complexity with the time taken to reach consensus. This scheme assumes that one of the nodes is the initiator. We also propose a method for gossiping in an arbitrary graph without an initiator where nodes communicate asynchronously using timeouts.