%0 Journal Article %1 bernadette2009heardof %A Charron-Bost, Bernadette %A Schiper, André %D 2009 %J Distributed Computing %K algorithms consensus distributed faulttolerant %N 1 %P 49--71 %T The Heard-Of model: computing in distributed systems with benign faults %U http://dx.doi.org/10.1007/s00446-009-0084-6 %V 22 %X Abstract  Problems in fault-tolerant distributed computing have been studied in a variety of models. These models are structured around two central ideas: (1) degree of synchrony and failure model are two independent parameters that determine a particular type of system, (2) the notion of faulty component is helpful and even necessary for the analysis of distributed computations when faults occur. In this work, we question thesetwo basic principles of fault-tolerant distributed computing, and show that it is both possible and worthy to renounce themin the context of benign faults: we present a computational model based only on the notion of transmission faults. In this model, computations evolve in rounds, and messages missed in a round are lost. Only information transmission isrepresented: 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 benign failures, be they static or dynamic, permanent or transient, in a unified framework.We demonstrate how this approach leads to shorter and simpler proofs of important results (non-solvability, lower bounds).In particular, we prove that the Consensus problem cannot be generally solved without an implicit and permanent consensuson heard-of sets. We also examine Consensus algorithms in our model. In light of this specific agreement problem, we showhow our approach allows us to devise new interesting solutions.

@article{bernadette2009heardof, abstract = {Abstract  Problems in fault-tolerant distributed computing have been studied in a variety of models. These models are structured around two central ideas: (1) degree of synchrony and failure model are two independent parameters that determine a particular type of system, (2) the notion of faulty component is helpful and even necessary for the analysis of distributed computations when faults occur. In this work, we question thesetwo basic principles of fault-tolerant distributed computing, and show that it is both possible and worthy to renounce themin the context of benign faults: we present a computational model based only on the notion of transmission faults. In this model, computations evolve in rounds, and messages missed in a round are lost. Only information transmission isrepresented: 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 benign failures, be they static or dynamic, permanent or transient, in a unified framework.We demonstrate how this approach leads to shorter and simpler proofs of important results (non-solvability, lower bounds).In particular, we prove that the Consensus problem cannot be generally solved without an implicit and permanent consensuson heard-of sets. We also examine Consensus algorithms in our model. In light of this specific agreement problem, we showhow our approach allows us to devise new interesting solutions.}, added-at = {2010-01-12T15:48:29.000+0100}, author = {Charron-Bost, Bernadette and Schiper, André}, biburl = {https://www.bibsonomy.org/bibtex/2f7f390766a94d565833011580d46c909/signof}, description = {The Heard-Of model: computing in distributed systems with benign faults}, interhash = {390adf60ba7d1e46035b7e0d98e1ea2c}, intrahash = {f7f390766a94d565833011580d46c909}, journal = {Distributed Computing}, keywords = {algorithms consensus distributed faulttolerant}, month = {#apr#}, number = 1, pages = {49--71}, timestamp = {2010-01-12T15:48:31.000+0100}, title = {The Heard-Of model: computing in distributed systems with benign faults}, url = {http://dx.doi.org/10.1007/s00446-009-0084-6}, volume = 22, year = 2009 }