The Heard-Of Model: Unifying all Benign Failures

<P>Problems in fault-tolerant distributed computing have been studied in a variety of models. These models are structured around two central ideas: </P> <P>1. Degree of synchrony and failure model are two independent parameters that determine a particular type of system. </P> <P>2. Failure and faulty component (i.e., the component responsible for the failure) are necessary and indissociable notions for the analysis of system behaviors. </P> <P>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 depends only on the notion of transmission failure. </P> <P>In this model, computations evolve in rounds, and messages missed at a round are 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.</P> <P> 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 in general, Consensus cannot be solved without an implicit and permanent 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.</P>


Year:
2006
Keywords:
Laboratories:




 Record created 2006-07-21, last modified 2018-10-01

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)