Télécom ParisTech

Actualité

Illustration de l'actualité : PhD defense Thibault Rieutord : Combinatorial Characterization of Asynchronous Distributed Computability

PhD defense Thibault Rieutord : Combinatorial Characterization of Asynchronous Distributed Computability

jeudi
25
octobre
2018

PhD Comics : I'm defending my thesis, Mom !

15:00, B310

Jury

  • M. Petr KUZNETSOV, Télécom ParisTech, Directeur de thèse
  • M. Maurice HERLIHY, Brown University, Rapporteur
  • M. Emmanuel GODARD, Université d'Aix-Marseille, Rapporteur
  • Mme Carole DELPORTE-GALLET, Université Paris-Diderot, Examinateur
  • Mme Maria POTOP-BUTUCARU, Sorbonne Université, Examinateur
  • M. Joffroy BEAUQUIER, Université Paris-Sud, Examinateur

Abstract

Modern computing systems are distributed, ranging from single-chip multi-processors to large-scale internet systems. In this thesis, we study computability and complexity issues raising in asynchronous crash-prone shared memory systems. The major part of this thesis is devoted to characterizing the power of a shared memory model to solve distributed tasks. Our first contribution is a refined and extended agreement-based simulation technique that allows us to reason about the relative task  computability of shared-memory models. Using this simulation technique, we show that the task computability of a shared-memory adversarial model is grasped by its ability to solve specific agreement tasks.