Faculté informatique et communications IC, Section des systèmes de communication, Institut d'informatique fondamentale IIF (Laboratoire de programmation distribuée LPD)

Synchronization using failure detectors

Kouznetsov, Petr ; Guerraoui, Rachid (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2005 ; no 3262.

Add to personal list
    Summary
    Many important synchronization problems in distributed computing are impossible to solve (in a fault-tolerant manner) in purely asynchronous systems, where message transmission delays and relative processor speeds are unbounded. It is then natural to seek for the minimal synchrony assumptions that are sufficient to solve a given synchronization problem. A convenient way to describe synchrony assumptions is using the failure detector abstraction. In this thesis, we determine the weakest failure detectors for several fundamental problems in distributed computing: solving fault-tolerant mutual exclusion, solving non-blocking atomic commit, and boosting the synchronization power of atomic objects. We conclude the thesis by a perspective on the very definition of failure detectors.
    Résumé
    De nombreux problèmes importants en informatique répartie sont impossibles à résoudre (de manière tolérante aux défaillances) au sein des systèmes purement asynchrones, dans lesquels le temps pour transmetre un message et les vitesses relatives des processeurs sont illimitées. Il est naturel de chercher les conditions minimales de synchronisme qui sont suffisantes pour résoudre un problème reparti donné. Une manière commode de décrire ces conditions consiste à utiliser l'abstraction de détecteur de fautes. Cette thèse détermine les détecteurs de fautes les plus faibles pour plusieurs problèmes fondamentaux de l'informatique répartie: résoudre l'exclusion mutuelle de manière tolérante aux fautes, résoudre la validation atomique de manière non-bloquante, et amplifier la puissance de synchronisation des objets atomiques. Nous concluons la thèse par une perspective sur la définition même de la notion de détecteurs de fautes.