Table des matières

Gérard Berry

Préface

Rachid Guerraoui

L’algorithmique répartie : à la recherche de l’universalité perdue

Leçon inaugurale prononcée au Collège de France le jeudi 25 octobre 2018

• 1. Une brève histoire de l’universalité informatique
• Algorithmique des anciens temps
• Des machines et des hommes
• Universalité de Turing
• Naissance d’une discipline scientifique et d’un outil magique
• 2. Informatique répartie : l’infiniment grand
• Ordinateurs et réseaux
• Propriétés d’une machine répartie
• Algorithmique répartie et adversaire
• Une première difficulté : le compromis entre robustesse et atomicité
• Une deuxième difficulté : le compromis avec la complexité
• Troisième difficulté : les mises à jour concurrentes
• 3. Informatique répartie : l’infiniment petit
• Révolution parallèle
• Retour aux nombres premiers : comment les trouver efficacement ?
• Synchronisation : un compteur partagé
• Mise en œuvre du compteur partagé
• Asynchronisme
• Atomicité et robustesse
• 4. Universalités
• Le double rôle du consensus
• Au cœur du consensus
• Théorème d’impossibilité du consensus : le cas de l’envoi de messages
• Théorème d’impossibilité du consensus : le cas de la mémoire partagée
• Résolution du consensus : hypothèses sur le temps
• Résolution du consensus : hypothèses sur le matériel
• 5. Universalités restreintes
• Consensus-K
• K-consensus
• Anonymat et malice
• Conclusion