Séminaire REGAL


The Iconoclastic Heard-Of Model: Unifying all Benign Failures

Friday, October 13, 2006
Speaker(s) : Bernadette Charron-Bost CNRS, Ecole polytechnique, France

Problems in fault-tolerant distributed computing have been studied in a variety of models. These models are structured around two central dogmas:
1. Degree of synchrony and failure model are two independent parameters that determine a particular type of system. 2. Failure and faulty component (i.e., the component responsible for the failure) are necessary and indissociable notions for the analysis of system behaviors.
In this work, we question these two dogmas and present a general computational model, suitable for describing any type of system with benign failures, that hinges only on the notion of transmission failure. In this model, computations evolve in rounds, and communication missed at a round is lost. Only information transmission is represented: for each round r and each process p, our model provides the set of processes that p "hears of" at round r (heard-of set) namely the processes from which p receives some message at round r. The features of a specific system are thus captured as a whole, just by a predicate over the collection of heard-of sets. We show that our model handles all types of benign failures, to be static or dynamic, permanent or transient, in a unified framework. Using this new approach, we are able to give shorter and simpler proofs of important results (non-solvability, lower bounds). In particular, we prove that Consensus cannot be solved without an implicit consensus on heard-of sets. We also examine Consensus algorithms in our model. In light of this specific agreement problem, we show how our approach allows us to devise new interesting solutions.

Marc.Shapiro (at) nulllip6.fr