Efficient Distributed Algorithms Suited for Uncertain Context

PhD Thesis defended by Anaïs Durand (Verimag Lab)

On September 1st 2017 (09:30)
Auditorium (bât IMAG, UGA, Campus Saint-Martin d’Hères)

Abstract: Distributed systems become increasingly wide and complex, while their usage extends to various domains (e.g., communication, home automation, monitoring, cloud computing). Thus, distributed systems are executed in diverse contexts. In this thesis, we focus on uncertain contexts, i.e., the context is not completely known a priori or is unsettled. More precisely, we consider two main kinds of uncertainty: processes that are not completely identified and the presence of faults. The absence of identification is frequent in large networks composed of massively produced and deployed devices. In addition, anonymity is often required for security and privacy. Similarly, large networks are exposed to faults (e.g., process crashes, wireless connection drop), but the service must remain available.

This thesis is composed of four main contributions. First, we study the leader election problem in unidirectional rings of homonym processes, i.e., processes are identified but their ID is not necessarily unique. Then, we propose a silent self-stabilizing leader election algorithm for arbitrary connected network. This is the first algorithm under such conditions that stabilizes in a polynomial number of steps. The third contribution is a new stabilizing property designed for dynamic networks that ensures fast and gradual convergences after topological changes. We illustrate this property with a clock synchronizing algorithm. Finally, we consider the issue of concurrency in resource allocation problems. In particular, we study the level of concurrency that can be achieved in a wide class of resource allocation problem, i.e. , the local resource allocation.

Jury:

  • Karine Altisen, Mcf, Grenoble INP/VERIMAG (directrice)
  • Stéphane Devismes, Mcf UGA/VERIMAG (encadrant)
  • Paola Flocchini, Pr, Univ. Ottawa (examinatrice)
  • Pierre Fraigniaud, DR, CNRS/IRIF (examinateur)
  • Colette Johnen, Pr, Univ. Bordeaux/LabRI (examinatrice)
  • Christian Scheideler, Pr, Univ Paderborn (rapporteur)
  • Michel Raynal, Pr, Univ. Rennes/IRISA (examinateur)
  • Sébastien Tixeuil, Pr, UPMC/LIP6 (rapporteur)