Algorithmique distribuée / Distributed algorithms

Diplômes intégrant cet élément pédagogique :

Descriptif

Ce module a 3 objectifs principaux :

1) Savoir écrire des algorithmes distribués tolérant aux fautes : être capable de spécifier formellement un problème et à  partir d'un ensemble d'hypothèse sur le système (topologie, pannes etc) être capable d'écrire un algorithme distribué réalisant la spécification.
2) Savoir prouver et analyser la complexité d'algorithmes distribués tolérant aux fautes.
3) Savoir déployer sur un simulateur les algorithmes vus en cours et TD. Pour cela, nous utiliserons le simulateur évènementiel SINALGO.

I. Introduction aux systèmes distribués
II. Algorithmique non tolérante aux fautes
III. Algorithmique tolérante aux fautes
    1) Introduction
    2) Bit alterné
    3) Impossibilité de Fischer, Lynch et Paterson
    4) Algorithmes de consensus : 4 moyens contournés l'impossibilité de Fischer, Lynch et Paterson
    5) Auto-stabilisation

 

This module has 3 main objectives:

1) Knowing how to write fault tolerant distributed algorithms: ability to formally specify a problem and to write a distributed algorithm realizing the specification of the system (topology, failures etc).
2) Ability to prove and analyze the complexity of fault-tolerant distributed algorithms.
3) Ability to deploy on a simulator the algorithms seen in class and TD. For this, we will use the simulator SINALGO event.

I. Introduction to distributed systems
II. Non Fault-Tolerant Algorithms
III. Fault-Tolerance
    1) Introduction
    2) Alternating Bit Protocol
    3) Impossibility result of Fischer, Lynch, and Paterson
    4) Consensus Algorithms: 4 ways to circumvent FLP85
    5) Self-Stabilization

Pré-requis

Aucun

 

None

Bibliographie

- G. Tel. Introduction to distributed algorithms. Cambridge University. 2000
- N. Lynch. Distributed Algorithms. Morgan Kaufmann. 1997

Informations complémentaires

Lieu(x) : Grenoble - Saint-Martin d'Hères
Langue(s) : Francais