Diffusion décentralisée d'information dans les systèmes distribués
Institution:
Paris 7Disciplines:
Directors:
Abstract EN:
This thesis focuses on the broadcast of information in a network. Broadcasting is the disse¬mination of information from a source node to ail other nodes. It is very present in information technology, both to transmit content over the Internet and for distributed or parallel Computing. In the protocols we consider, each informed node take part in the dissemination of information : in flooding, an informed node disseminate the information to ail its neighbours in one time step, and in gossip (1-PORT) broadcasting each informed node communicates, at each time step, only with one of its neighbours. Our first contribution is the study of the worst broadcast time of a gossip protocol where a node does not call a neighbour he knows to be informed. We study three variants, in the first one, a node knows that a neighbour is informed only if it has sent it the information, in the second one, the neighbours a node knows to be informed are ail those with whom it has exchanged information (in one way or the other), and in the third one, each node knows exactly which of its neighbours are informed. We mainly show that in the first variant, it is possible to compute in polynomial time the worst broadcast time and a worse broadcast scheme. For the other two variants, we show that this calculation is NP-hard and even inapproximable in polynomial time. Our second contribution is the study of diffusion in dynamic networks modeled by edge-Markovian evolving graphs. We give a reduction technique that allows the computation of the time taken by the flooding to inform ail nodes of an edge-Markovian evolving graph to be reduced to the computation of the diameter of a static weighted random graph. We also compute the broadcast time of a random gossip protocol in some particular edge-Markovian evolving graphs. Our last contribution relates to spatial gossip where ail nodes can communicate with each other. The performances of spatial gossip protocols are measured in function of the targets' relative distance to the source. We describe a general random spatial gossip protocol, I. E. , valid for any metric. We analyze its propagation speed on graph metrics and on metrics of uniform density.
Abstract FR:
Cette thèse porte sur la diffusion d'informations dans les réseaux. La diffusion consiste à transmettre une information à partir d'un nœud source vers tous les autres nœuds. Elle est très présente en informatique, aussi bien pour transmettre du contenu par internet que pour le calcul distribué ou parallèle. Dans les protocoles que nous considérons, chaque nœud informé participe à la diffusion d'information : dans l'inondation, un nœud informé transmet l'information à tous ses voisins en une seule étape de temps, et dans la diffusion 1-PORT chaque nœud informé communique, à chaque étape, avec un unique voisin. Notre première contribution porte sur l'étude du pire temps de diffusion 1-PoRT où un nœud n'appelle pas un voisin qu'il sait être informé. Nous étudions trois variantes. Dans la première, un nœud ne rappelle simplement pas un voisin auquel il a déjà envoyé l'information ; dans la deuxième, les voisins qu'un nœud sait être informés sont tous ceux avec lesquels il a déjà échangé de l'information (dans un sens ou dans l'autre) ; dans la troisième, chaque nœud sait exactement quels sont ses voisins informés. Nous montrons principalement que dans la première variante, il est possible de calculer en temps polynomial le pire temps de diffusion et un pire schéma correspondant. Pour les deux autres variantes, nous montrons que ce calcul est NP-difficile, en fait inapproximable en temps polynomial. Notre deuxième contribution concerne l'étude de la diffusion dans des réseaux dynamiques modélisés par des graphes à évolution arête-markovienne. Nous proposons une technique de réduction permettant de ramener le calcul du temps d'inondation au calcul du diamètre d'un graphe pondéré statique tiré aléatoirement. Cette technique nous permet de calculer le temps de diffusion par inondation dans les graphes dynamiques arête-markoviens. Nous avons également calculé le temps de diffusion probabiliste 1-PORT dans certains graphes à évolution arête-markovienne. Notre dernière contribution porte sur la diffusion spatiale où tous les nœuds peuvent communiquer les uns avec les autres. Les performances des protocoles de diffusion spatiale sont mesurées en fonction de l'éloignement des destinataires par rapport à la source. Nous décrivons un protocole de diffusion spatiale probabiliste généraliste, c'est-à-dire, valable pour toute métrique. Nous analysons sa vitesse de propagation dans les métriques de graphes et dans les métriques à densité uniforme.