An algorithmic approach to distributed systems

Responsable / In charge of : Baude Françoise (

Résumé / Abstract :
We address the problems of coordination of a set of asynchronous and distributed processes, requiring the representation of time and its use in a distributed framework. The problems solved are typically: election of a process, group communication, detection of global properties (absence of deadlock, termination), consensus, detection and failure recovery, mutual exclusion.

Prérequis / Prerequisite :
Management of competition between processes (centralized framework) Algorithmic (basic)

Objectifs / Objectives :
Be able to understand the problems that arise in the context of distributed systems, such as posed by the asynchrony between the processes executing without assuming the existence of a global memory space and therefore communicating by sending messages
• Moreover, these problems are approached by considering or not hypotheses of breakdowns. In this context, the objective is to design algorithms, even simple

Contenu / Contents :

  • Introduction, hypotheses. Election of a process
  • Time in distributed systems, cut and consistent state
  •  Failure recovery by saving state and logging messages
  •  Group communication
  •  Fault finding and Consensus (application to transactions)
  •  Mutual exclusion
  •  Detection of global states: termination, deadlock

Références / References :
• Distributed Algorithms for Message-Passing Systems by M. Raynal, Springer 2013
• Distributed Systems : An Algorithmic Approach by Sukumar,
• Distributed systems, Principles and Paradigms, A. Tanenbaum, M. Van Steen, 2nd edition

Acquis / Knowledge :

  • Understanding of typical problems present in distributed systems and middleware
  • Knowledge of classic approaches to solving these problems
  • Evaluation / Assessment :

Each session gives rise to Exercises in the form of Homework, to be returned for the following week. The set of 7 scores obtained makes it possible to achieve an average which counts for 50% of the overall score. An individual assignment on the table, lasting 3 hours, counts for 50% of the overall mark.