A Synchronous Gossip Algorithm with Exponential Backoff

In large-scale distributed systems, gossip protocols are often used to disseminate information. In this paper, an improved Gossip algorithm that integrates binary exponential backoff used in computer network into the classic Gossip algorithm is proposed to reduce the network load in the process of information dissemination. The improved Gossip algorithm applies an exponential backoff messaging strategy to spread information among nodes, i.e. the more often a node receives a certain information, the less likely it is to spread information in the following rounds. The Markov chain is used to analyze this model. We analyze the performance of this proposed algorithm both analytically and by simulations and show how it reduces network load compared to the classic Gossip algorithm. Our method reduces the network load by 28% compared to the classic algorithm on 10,000 nodes.