Research On Gossip Algorithms Based On Exponential Backoff

Gossip algorithm is widely used in many scenarios because of its simplicity,efficiency,robustness,scalability and anti-jamming ability.At first,Gossip algorithm is only one of the important methods of information dissemination in the field of communication,but with the development of decentralized network,the application of Gossip algorithm is expanding.At present,the application of Gossip algorithm includes database replication,aggregate computing,network topology construction,fault detection,network monitoring,routing technology and so on.In addition,Gossip algorithm is one of the underlying protocols of block chain technology.In this thesis,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.The theoretical analysis and simulation results show that the method can effectively reduce the amount of information dissemination in the network.Experiments show that the Gossip algorithm with exponential backoff has the problem of edge nodes,and the information can not be disseminated to all nodes in the network in a limited period.Therefore,this thesis uses two different ways to optimize the Gossip algorithm of binary exponential backoff.These two approaches can deal with different application scenarios respectively.In the first way,we introduce the concept of "Pull".Nodes that do not receive information actively send request information to other nodes in the network until it receives update information.The simulation results show that compared with Gossip algorithm,when the network size is 10,000 nodes,the first method reduces the network load by about 36%.In the second way,the node receiving the message first sends information to the former node,which will send information randomly to other nodes in the network after the completion of the transmission.The simulation results show that compared with Gossip algorithm,the second method reduces the network load by about 37% when the network size is 10,000 nodes.This thesis also implements the asynchronous scheme of this algorithm,and compares the synchronous and asynchronous algorithms.Experiments show that the proposed methods can effectively improve the performance of Gossip algorithm and reduce the amount of information in the network.