Evènement pour le groupe Algorithmique Distribuée


Date 2013-06-10  14:00-15:00
TitreThe Heard-Of model: computing in distributed systems with benign failures 
RésuméProblems in fault-tolerant distributed computing have been studied in a va- riety of system models. These models are all based on the principle that it is usefull and even necessary to specify why and by whom errors occur. In this talk, we question this principle, and present a general computational model, called the Heard-Of model, suitable for describing any type of system, be it message passing, shared memory, synchronous, or asynchronous. In this model, computations evolve in rounds, and communication missed at a round is definitely lost. Only information transmission is represented: for each round r and each process p, our model specifies 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. Thus the Heard-Of model allows us to handle all types of benign failures, static or dynamic, permanent or transient, in a unified framework. Moreover, it unifies the most seemingly unrelated notions in distributing computing, namely synchrony and asynchrony. We further demonstrate how this unifying framework leads to new results and insights in fault-tolerant distributed computing. In particular, we show that some fundamental results for asynchronous systems can be advantageously transferred to synchronous systems. We also examine Consensus algorithms in the Heard-Of model: we show how our approach allows us to devise new solutions and to give simple correctness proofs of existing algorithms like Paxos. Joint work with André Schiper (EPFL) 
LieuSalle 178 
OrateurBernadette Charron-Bost (CNRS, Ecole polytechnique, Paris) 
UrlCNRS, Ecole polytechnique, France 



Aucun document lié à cet événement.

Retour
Retour à l'index