Gossip Algorithms over Different Network Topologies
A brief description of three different gossip algorithms (probabilistic broadcast, probabilistic edge and fixed fanout) with detailed examples on how do they work over different network topologies (Erdős–Rényi, random geometric graph and scale free).
June 20, 2017—Daniele Baschieri
Random Graph
Gossip algorithms are a system of machine-to-machine communication whose goal is to minimize channel usage and maximize the coverage of a network. The network can be seen as graph of nodes. Nodes represent computers, and edges represent connections.
An example of a random graph:
In[]:=
randomGraph=RandomGraph[{8,20}]
Out[]=
A pure broadcast mechanism sends the message to all the other nodes connected with the source. This method leads to a complete coverage of the message in the graph, but on the other hand causes saturation of the channel.
The source of the message is in red, with mail on the involved edges: