Algorithmique et techniques de base des systèmes répartis

La conception et la réalisation des systèmes et applications répartis s'appuient sur un ensemble de principes de base régissant la communication, la gestion de l'information, le partage de ressources, la tolérance aux fautes. L'objectif de ce module est de présenter ces principes en les illustrant par des exemples concrets d'application.

Les aspects suivants sont examinés :

• Temps et état dans un système réparti. Application : datation, observation, mise au point, synchronisation.
• Algorithmes de base des systèmes répartis (élection, terminaison, etc.). Applications : calcul réparti.
• Tolérance aux fautes, diffusion fiable, gestion de groupes. Applications : serveurs disponibles, gestion de copies multiples.
• Consensus et validation. Applications : service de consensus, transactions réparties.
• Désignation répartie. Applications : services de noms, gestion de la mobilité
• Gestion répartie de l'information. Accès, propagation de modifications, cohérence, recherche. Applications : fichiers répartis, systèmes P2P

L'accent est mis sur les aspects fondamentaux. Pour chaque classe de méthodes, on indique schématiquement son utilisation dans la conception de systèmes réels.

1. Temps et état dans un système réparti.

   1. Causalité et ordonnancement des événements dans un système réparti
   2. État global d'un système réparti ; coupures cohérentes
   3. Algorithmes de sauvegarde-reprise, détection de propriétés stables Ordonnancement global par horloges logiques
   4. Exclusion mutuelle, files d'attente réparties Ordonnancement causal par horloges vectorielles
   5. Observation, mise au point Synchronisation d'horloges physiques

2. Coopération de processus répartis

   1. Anneau virtuel, protocoles d'insertion, retrait, gestion des défaillances.
   2. Algorithmes d'élection
   3. Gestion de groupes Algorithmes de détection de terminaison
   4. Ramasse-miettes réparti

3. Tolérance aux fautes

   1. Hypothèses de pannes
   2. Spécification de la cohérence : linéarisabilité, cohérence séquentielle, cohérence causale
   3. Copie primaire et duplication active

   4. Algorithmes de diffusion fiable et gestion de groupes de processus

      1. diffusion fiable, causale, atomique
      2. gestion de groupes, vues synchrones
   5. Serveurs fiables, gestion de copies multiples, mémoire virtuelle répartie

4. Consensus et validation

   1. Classes de détecteurs de défaillances
   2. Problème du consensus
   3. Quelques cas particuliers (omission synchrone, byzantin synchrone ou non) Protocoles de décision : validation à 2 ou 3 phases
   4. Gestion répartie de transactions

5. Désignation dans les systèmes répartis

   1. Rappel des principes de la désignation : noms, liaison
   2. Problèmes de la désignation dans les systèmes répartis : capacité de croissance, mobilité, défaillances
   3. Techniques pour la désignation répartie : serveurs de domaines, liens de poursuite, caches d'indicateurs.
   4. Illustration sur des études de cas : DNS, caches de préfixes, gestion de la mobilité, objets et agents mobiles

6. Gestion répartie de l'information

   1. Principes de la gestion d'objets répartis
   2. Mise en œuvre : mémoire virtuelle, objets répartis
   3. Gestion de caches, cohérence
   4. Études de cas sur mémoire virtuelle répartie, objets sur le Web, caches d'objets Java répartis, etc.

L'auteur Sacha Krakowiak est enseignant-chercheur dans le domaine de l'informatique distribuée à l'Université de Grenoble (France). Pour plus d'informations, rendez-vous sur sa page personnelle.