Note publique d'information : La dissémination d'informations (broadcast) est essentielle pour de nombreuses applications
réparties. Celle-ci doit être efficace, c'est à dire limiter la redondance des messages,
et assurer forte fiabilité et faible latence. Nous considérons ici les algorithmes
répartis profitant des propriétés des topologies sous-jacentes. Cependant, ces propriétés
et les paramètres dans les algorithmes sont hétérogènes. Ainsi, nous devons trouver
une manière pour les comparer équitablement. D'abord, nous étudions les protocoles
probabilistes de dissémination d’informations (gossip) exécutées sur trois graphes
aléatoires. Les trois graphes représentent les topologies typiques des réseaux à grande-échelle
: le graphe de Bernoulli, le graphe géométrique aléatoire et le graphe scale-free.
Afin de comparer équitablement leurs performances, nous proposons un nouveau paramètre
générique : le fanout effectif. Pour une topologie et un algorithme donnés, le fanout
effectif caractérise la puissance moyenne de la dissémination des sites infectés.
De plus, il simplifie la comparaison théorique des différents algorithmes sur une
topologie. Après avoir compris l’impact des topologies et les algorithmes sur les
performances , nous proposons un algorithme fiable et efficace pour la topologie scale-free.
Note publique d'information : Information dissemination (broadcast) is essential for numerous distributed applications.
This must be efficient, which limits the message redundancy, and ensures high reliability
as well as low latency. We consider here the distributed algorithms that benefitting
from the properties of the underlying topologies. Nonetheless, these properties and
the parameters in the algorithms are heterogeneous. Thus, we should find a method
to fairly compare them. First of all, we study the probabilistic protocols for information
dissemination (gossip) executed over three random graphs. The three graphs represent
the typical topologies of large-scale topologies: Bernoulli graph, the random geometric
graph, and scale-free graph. In order to fairly compare their performance, we propose
a new generic parameter: effectual fanout. For a given topology and algorithm, the
effectual fanout characterizes the mean dissemination power of infected sites. Furthermore,
it simplifies the theoretical comparison of different algorithms over one topology.
After having understood the impact of topologies and algorithms on the performance,
we propose an efficient reliable algorithm for scale-free topologies
paprika.idref.fr
data.idref.fr
Documentation
