Fair Comparison of Gossip Algorithms over Large-Scale Random Topologies

We present a thorough performance comparison of three widely used probabilistic gossip algorithms over well-known random graphs. These graphs represent some large-scale network topologies: Bernoulli (or Erdos-Rényi) graph, random geometric graph, and scale-free graph. In order to conduct such a fai...

Full description

Saved in:
Bibliographic Details
Main Authors: Ruijing Hu, Sopena, J., Arantes, L., Sens, P., Demeure, I.
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Complexity theory
Distributed Algorithms
Gossip Algorithms
Message Complexity
Network topology
Performance Evaluation
Probabilistic logic
Protocols
Random Topologies
Reliability
Topology
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present a thorough performance comparison of three widely used probabilistic gossip algorithms over well-known random graphs. These graphs represent some large-scale network topologies: Bernoulli (or Erdos-Rényi) graph, random geometric graph, and scale-free graph. In order to conduct such a fair comparison, particularly in terms of reliability, we propose a new parameter, called effectual fan out. For a given topology and gossip algorithm, the effectual fan out characterizes the mean dissemination power of infected sites. For large-scale networks, the effectual fan out has thus a strong linear correlation with message complexity. It enables to make an accurate analysis of the behavior of a gossip algorithm over a topology. Furthermore, it simplifies the theoretical comparison of different gossip algorithms on the topology. Based on extensive experiments on top of OMNet++ simulator, which make use of the effectual fan out, we discuss the impact of topologies and gossip algorithms on performance, and how to combine them to have the best gain in terms of reliability.
ISSN:1060-9857
2575-8462
DOI:10.1109/SRDS.2012.28