Version classiqueVersion mobile

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

 | 
Rachid Guerraoui

Préface

Gérard Berry

Texte intégral

1C’est pour moi un grand plaisir d’introduire Rachid Guerraoui, professeur à l’École polytechnique fédérale de Lausanne, la fameuse EPFL, que le Collège de France a invité sur cette dixième édition de la chaire Informatique et sciences numériques. Il est l’un des plus grands experts mondiaux de l’algorithmique répartie, sujet majeur mais encore peu abordé au Collège de France. Sur cette même chaire, nous avons eu dans le passé trois cours sur divers aspects de l’algorithmique, avec Bernard Chazelle en 2010-2011 pour les algorithmes naturels, Jean-Daniel Boissonnat en 2016-2017 pour les algorithmes géométriques, et Claire Mathieu en 2017-2018 pour des algorithmes travaillant sur de très grandes structures de données. Nous y avons vu l’impact devenu déterminant de la randomisation, c’est-à-dire du tirage au hasard pour augmenter les performances en moyenne des algorithmes.

  • 1 Les enregistrements audio et vidéo sont accessibles sur le site internet du Collège de France : ht (...)

2Mais les programmes implémentant les algorithmes précités travaillaient en général sur un seul ordinateur avec des données localisées sur cet ordinateur. Dans son enseignement, Rachid Guerraoui va nous présenter une algorithmique d’un genre très différent, l’algorithmique parallèle et distribuée. Ici, données et programmes sont répartis dans différents ordinateurs connectés en réseau, potentiellement en grand nombre et à grande distance, calculant en parallèle chacun à son rythme, et communiquant entre eux par envoi de messages asynchrones. L’asynchronisme signifie que le moment où un message est reçu est strictement et arbitrairement postérieur à celui de son envoi, à moins que ce message ne se soit perdu en route. C’est le cas sur Internet, exactement comme pour le courrier postal, à l’efficacité près bien sûr. Ce n’est pas la seule forme de communication entre systèmes parallèles : ceux que j’ai enseignés dans mes propres cours sont au contraire fondés sur les communications synchrones, c’est-à-dire en temps conceptuellement nul, ou encore vibratoires, c’est-à-dire en temps physiquement prévisible. Leurs modèles sont pertinents pour les circuits électroniques et les programmes temps réels, mais pas pour les algorithmes distribués à grande échelle. Certains algorithmes distribués ont cependant été présentés lors de séminaires de mon cours, par exemple par Michel Raynal, Anne-Marie Kermarrec et Laurent Massoulié1.

3Le parallélisme distribué change complètement la vision des algorithmes. Intuitivement, les algorithmes séquentiels classiques peuvent être réalisés en bougeant un doigt dans le programme, à la façon du calcul d’un mathématicien avec son crayon ou sa craie. Les algorithmes répartis coordonnent les calculs de plusieurs doigts parcourant plusieurs programmes exécutés par un nombre arbitraire d’ordinateurs répartis n’importe où dans le monde ou dans l’espace, et même apparaissant ou disparaissant à n’importe quel moment. Les applications sont très nombreuses, avec souvent de fortes contraintes de sûreté ou de sécurité : bases de données distribuées, diffusion efficace en pair-à-pair de vidéos où votre ordinateur sert à la fois de client et de serveur dans un grand réseau virtuel, stockage et calcul dans le nuage (cloud computing en anglais), chaînes de blocs (blockchains) pour les transactions sécurisées, etc. Vous en verrez bien d’autres dans cette leçon et dans le cours2.

4Cette nouvelle algorithmique, dont l’explosion a suivi celle des dispositifs de calcul et des réseaux, s’avère tout à fait fascinante. Elle pose à la fois de nouvelles questions théoriques, quant aux notions de calculabilité et de tolérance aux pannes, et des problèmes redoutables de mise en place pratique, car la programmation y est souvent très subtile et difficile à vérifier ou à prouver mathématiquement correcte. Partons donc avec Rachid Guerraoui à la recherche de la calculabilité perdue et de nouveaux algorithmes répartis, une espèce qui n’est pas du tout en voie de disparition.

Notes

1 Les enregistrements audio et vidéo sont accessibles sur le site internet du Collège de France : http://www.college-de-france.fr/site/gerard-berry/_course.htm.

2 Idem : http://www.college-de-france.fr/site/rachid-guerraoui/_course.htm.

Auteur

Professeur émérite du Collège de France titulaire de la chaire Algorithmes, machines et langages de 2007 à 2019 ; auparavant professeur invité sur les chaires annuelles Innovation technologique Liliane Bettencourt (2007-2008) et Informatique et sciences numériques (2009-2010).

Le texte et les autres éléments (illustrations, fichiers annexes importés) sont sous Licence OpenEdition Books, sauf mention contraire.

Rechercher dans OpenEdition Search

Vous allez être redirigé vers OpenEdition Search