000052622 001__ 52622
000052622 005__ 20180317094354.0
000052622 037__ $$aREP_WORK
000052622 245__ $$aAn Adaptive Algorithm for Efficient Message Diffusion in Unreliable Environments
000052622 269__ $$a2004
000052622 260__ $$c2004
000052622 336__ $$aReports
000052622 520__ $$aIn 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.
000052622 6531_ $$aadaptive protocols
000052622 6531_ $$alarge-scale systems
000052622 6531_ $$aprobabilistic protocols
000052622 6531_ $$areliable broadcast
000052622 6531_ $$aoptimal message diffusion
000052622 700__ $$aGarbinato, Benoit
000052622 700__ $$aPedone, Fernando
000052622 700__ $$aSchmidt, Rodrigo
000052622 8564_ $$s285122$$uhttps://infoscience.epfl.ch/record/52622/files/IC_TECH_REPORT_200430.pdf$$zn/a
000052622 909CO $$ooai:infoscience.tind.io:52622$$preport$$pIC
000052622 909C0 $$0252226$$pLABOS$$xU10700
000052622 937__ $$aLABOS-REPORT-2004-002
000052622 970__ $$a200430/IC
000052622 973__ $$aEPFL$$sPUBLISHED
000052622 980__ $$aREPORT