Calculabilité et conditions de progression des objets partagés en présence de défaillances
Directeur de Thèse :
– Michel Raynal, professeur Université de Rennes 1
Rapporteurs:
- Dominique Mery, Professeur Loria
- Franck Petit, Professeur Lip6
Examinateurs :
- Carole Deplorte, Professeur Paris Diderot
- Petr Kuznetsov, Chercheur TU Berlin
- Rachid Guerraoui, Professeur EPFL Lausanne
- Panagiota Fatourou, Assistant Professeur, University of Crete
Dans un système distribué, différents processus communiquent et se synchronisent pour résoudre un calcul global. La difficulté vient du fait qu’un processus ne connait pas les entrées des autres. Nous considérons ici un système asynchrone: on ne fait aucune hypothèses sur les vitesses d’exécution relatives des différents processus. De plus, pour modéliser les pannes, nous considérons que les processus peuvent crasher: ils peuvent arrêter leur exécution à n’importe quel endroit de leur programme.
Dans l’étude théorique des systèmes distribués, les problèmes doivent être considérés selon deux aspects: la sûreté et la progression. La sûreté définit quand une valeur de sortie est correcte. La progression définit dans quelles conditions un processus doit terminer une opération, indépendamment de la valeur qu’il choisit comme sortie.
Cette thèse se concentre sur les liens entre calculabilité et conditions de progression des objets distribués. Dans un premier temps, nous introduisons et étudions la notion de conditions de progression asymétriques: des conditions de progression qui peuvent être différentes pour différents processus du système. Nous étudions ensuite la possibilité de
fournir des abstractions dans un système donné. La question de l’équivalence de modèles de systèmes est ensuite abordée, en particulier dans le cas où les processus ont accès à des objets puissants. Pour finir, la thèse traite le sujet des tâches colorées en fournissant un algorithme de renommage adapté au cas où la concurrence est réduite. Une nouvelle classe de tâches colorées est enfin introduite qui englobe, sous un formalisme unique, plusieurs problèmes considérés jusqu’ici comme indépendants.
Calculability and progress conditions of shared objects when facing crashes
In a distributed system, different processes synchronize in order to solve a global computation. The difficulty comes from the fact that a process does not know the other inputs. We consider here asynchronous systems: no assumption can be made regarding the relative speeds of processes. We also consider that processes can crash, i.e. stop their execution at an arbitrary point of their code.
In the theoretical study of distributed systems, problems have to be considered according to two aspects: safety and progress. Safety defines whether a given value can be output. Progress defines under which conditions a process is required to terminate its operation, regardless of the value it outputs.
This thesis is about the links between calculability and progress conditions of shared objects. We start by introducing and studying the notion of asymmetric progress conditions: progress conditions that don’t necessarily impose the same requirements for different processes. We then study the possibility of supplying processes with abstractions in a given model. The issue of the equivalence of system models is then raised, especially when processes have access to strong objects. Finally, the thesis studies colored tasks. It presents a renaming algorithm that terminates if contention gets below a given threshold. It then introduces a new class of colored tasks that allows to unify in a single framework different problems which were previously studied independently.