Distributed systems

This course is an introduction to distributed algorithms. It begins with a presentation of distributed systems and the different problems that need to be solved depending on the type of system: large networks, local networks, multi-processor machines or a single machine housing several processes. Local computations, and in particular graph rewritings, are the main formalism used to express and prove the distributed algorithms seen in the course. The various problems addressed are: the computation of a spanning tree, the problem of recognition, election, detection of termination and, more generally, the detection of stable properties, computation of a global state, probabilistic distributed algorithms, resistance to failure: self-stabilizing algorithms. For each of these problems, we'll show the importance of the assumptions made about the network or the knowledge we have of it. We'll study where the boundary lies between what we can do and what we can't do. We'll also show how problems with no deterministic solution can be very easily and efficiently solved by probabilistic algorithms.

1. Introduction , Overview of the different models
2. Calculating a spanning tree
3. Election
4. Recognition
5. Termination detection
6. Probabilistic algorithms
7. Self-stabilizing algorithms
8. Fault detection and tolerance

C. Lavault Evaluation des algorithmes distribués 1995 Hermes /

G. Tel Introduction to distributed algorithms 2000 Cambridge University Press