An Adaptive Algorithm for Efficient Message Diffusion in Unreliable EnvironmentsReportar como inadecuado

An Adaptive Algorithm for Efficient Message Diffusion in Unreliable Environments - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Publication date: 2004

In this paper, we propose a novel approach for solving the reliable broadcast problem in a probabilistic model, i.e., where links lose messages and where processes crash and recover probabilistically. Our approach consists in first defining the optimality of probabilistic reliable broadcast algorithms and the adaptiveness of algorithms that aim at converging toward such optimality. Then, we propose an algorithm that precisely converges toward the optimal behavior, thanks to an adaptive strategy based on Bayesian statistical inference. Our adaptive algorithm is modular and consists of two activities. The first activity is responsible for solving the reliable broadcast, given information about the failure probability of each link and of each process. This activity relies on the notion of Maximum Reliability Tree, which we derive from the notion of Maximum Spanning Tree. The other activity is responsible for approximating failure probabilities of links and processes, using Bayesian networks. We compare the performance of our algorithm with that of a typical gossip algorithm through simulation. Our results show, for example, that our adaptive algorithm quickly converges toward such exact knowledge.

Keywords: adaptive protocols ; large-scale systems ; probabilistic protocols ; reliable broadcast ; optimal message diffusion Reference LABOS-REPORT-2004-002

Autor: Garbinato, Benoit; Pedone, Fernando; Schmidt, Rodrigo


Documentos relacionados