Projet Rubens, ENS Lyon, CC BY
Rachid Guerraoui, EPFL- École Polytechnique Fédérale de Lausanne – Swiss Federal Institute of Technology in Lausanne
Rachid Guerraoui est professeur à l’École Polytechnique Fédérale de Lausanne où il dirige le Laboratoire de calcul distribué. Il est le tout nouveau titulaire de la Chaire « Informatique et sciences numériques » du Collège de France où il présente un cours intitulé « Algorithmes : à la recherche de l’universalité perdue » (leçon inaugurale le 24 octobre 2018). L’informatique est efficace et robuste parce qu’on sait « répartir » un calcul entre plein de processeurs. Rachid Guerraoui est un des meilleurs spécialistes mondiaux en informatique répartie, le sujet de son cours. Rachid a aussi participé aux lancements des plates-formes d’enseignement en ligne Wandida et Zetabytes, et il écrit régulièrement pour Binaire. Cet article est publié en collaboration avec le blog Binaire.
Nous sommes en 2018. Les humains sont contrôlés par des algorithmes. Tous les humains ? Tous. Aucun village d’irréductibles ne résiste encore et toujours aux algorithmes ? Aucun.
Est-ce grave ? Question de perspective. Les algorithmes ne boivent pas, ne s’énervent pas et s’endorment pas. Pourquoi ne pas les laisser conduire nos voitures ? Nous accusons la voiture d’être le moyen de transport le plus dangereux quand nous devrions plutôt accuser le chauffard, lui qui boit, s’énerve ou s’endort. Et si nous avions pu envoyer des algorithmes pilotant des robots au fond d’une mine, nous aurions raté de grands livres, certes, mais nous aurions sauvé nombre de vies humaines. À ce propos justement, des algorithmes sont souvent plus efficaces que les médecins lorsqu’il s’agit de détecter certaines maladies à partir d’une radiographie.
Les algorithmes sont efficaces car ils s’exécutent sur des systèmes informatiques extrêmement robustes et rapides. La robustesse vient de la répartition globale du système informatique sur plusieurs sites, parfois disposés aux quatre coins du monde et tolérant donc la panne de certains de ces sites. La rapidité vient de la répartition locale du calcul car, au cœur même de chaque ordinateur, cohabitent aujourd’hui un grand nombre de processeurs.
Faire transcrire par des informaticiens chevronnés les savoirs d’une équipe médicale dans un algorithme ne peut être intrinsèquement mauvais, puisque l’on décuplera la force des médecins. Vive donc les algorithmes et nous avec !
Les bêtises des algorithmes
Nous pourrions nous arrêter sur cette note positive. Seulement voilà, les algorithmes peuvent aussi parfois dire n’importe quoi. Nous le constatons régulièrement. Ils peuvent même raconter des bêtises énormes. Et certaines bêtises peuvent être dangereuses car amplifiées par la puissance du système informatique exécutant l’algorithme.
Le grand danger n’est pas l’intelligence artificielle des algorithmes, mais leur bêtise naturelle. Ce danger est concret, réel, palpable. Il n’est pas du registre de la science-fiction comme la prétendue super intelligence des algorithmes, trop souvent médiatisée. Plus nous dépendons des algorithmes, plus nous sommes vulnérables à leur bêtise.
Mais ne pouvons-nous rien contre cette bêtise ? Les informaticiens n’ont-ils pas développé, depuis près d’un siècle, des techniques de preuves théoriques et de tests empiriques qui devraient nous permettre de réduire la probabilité de mauvaises surprises ? Oui. Mais ces techniques reposent sur une hypothèse fondamentale : l’universalité de Turing.
En effet, Alan Turing a fait de l’informatique une science en créant un modèle d’ordinateur universel, la machine de Turing. Tout ce qui peut être calculé par un algorithme le peut par cette machine. Depuis un demi-siècle, les ordinateurs sont construits suivant ce modèle universel. Cela permet, tout en profitant de la puissance d’un ordinateur, de s’affranchir des détails technologiques de son architecture pour apprivoiser les algorithmes. Ces algorithmes peuvent ainsi être conçus et analysés à partir de principes abstraits rigoureux, puis testés concrètement sur n’importe quelle machine universelle donnée, avant d’être déployés sur une autre. Cette universalité nous a permis d’espérer un monde algorithmique sans erreurs.
Malheureusement, cette universalité a été perdue dans une large mesure. Elle a été perdue sans parfois qu’on ne le réalise, lorsque l’on a voulu répartir les systèmes informatiques pour en faire des machines super-robustes et super-efficaces. En cherchant la robustesse et l’efficacité, nous avons perdu l’universalité. Alors qu’une seule machine de Turing permet d’exécuter n’importe quel algorithme, un réseau de machines ne le peut plus.
La perte de l’universalité de Turing implique que l’on ne peut pas déployer sur un réseau de machines, un algorithme conçu à partir de principes abstraits issus de l’algorithmique classique, centralisée, ou testé sur d’autres machines, et s’attendre à ce que l’algorithme fonctionne de la même manière. Les détails technologiques du réseau entrent en jeu : l’abstraction et la rigueur en pâtissent.
Informatique répartie
La discipline scientifique qui étudie les algorithmes déployés sur des systèmes informatiques répartis s’appelle l’algorithmique répartie. Elle étudie aussi bien les algorithmes déployés sur un ensemble d’ordinateurs géographiquement distants et communiquant par envois de messages, que les algorithmes déployés sur plusieurs processeurs au cœur du même ordinateur. On parle aussi parfois dans ce dernier cas d’algorithmes concurrents car partageant la même mémoire.
L’un des objectifs principaux de l’algorithmique répartie est d’identifier les conditions nécessaires et suffisantes sur les réseaux, grands ou petits, permettant de retrouver l’universalité de Turing. Lorsque ces conditions ne sont pas satisfaites, il s’agît de définir les formes d’universalités restreintes que l’on peut réaliser.
Un résultat fondamental en algorithmique répartie stipule que la perte de l’universalité de Turing est intimement liée à l’impossibilité pour des machines connectées par un réseau asynchrone (dans lequel on ne fait pas d’hypothèse sur les temps de communication) d’atteindre un consensus. Intuitivement, cette impossibilité signifie que lorsque l’on déploie un algorithme sur un réseau de machines, elles ne peuvent pas se mettre d’accord sur l’ordre d’exécution des instructions de l’algorithme. D’autres résultats d’algorithmique répartie, plus positifs, définissent des conditions permettant de contourner l’impossibilité du consensus et d’obtenir une nouvelle forme d’universalité, certes restreinte, mais suffisante pour de nombreuses applications et réseaux.
En informatique répartie, les algorithmes sont constitués, en plus des instructions élémentaires des algorithmes classiques centralisés, d’instructions permettant de faire communiquer plusieurs machines, comme des envois de messages ou des accès à des variables partagées. Ces instructions de communication ont un impact fondamental sur la nature des algorithmes. Leur complexité s’en trouve profondément affectée et de nouvelles métriques sont nécessaires pour mesurer leur efficacité, basées par exemple sur le nombre de messages envoyés en fonction du nombre d’ordinateurs connectés. Ces métriques permettent d’étudier le compromis entre les super pouvoirs de la machine répartie obtenue : robustesse et efficacité. Les algorithmes d’apprentissage sous-jacents à l’intelligence artificielle moderne illustrent ce compromis. Du fait de la grande quantité de données disponible, l’apprentissage est réparti sur plusieurs machines. Une moyenne des analyses obtenues est alors effectuée. Mais une seule machine donnant des valeurs extravagantes conduit à la défaillance du tout.
Jens Petersen/Wikipedia, CC BY
Au-delà des considérations technologiques qui motivent l’étude de l’algorithmique répartie pour mieux appréhender les inventions humaines que sont les ordinateurs et les réseaux, cette étude est tout aussi fondamentale à la compréhension de phénomènes naturels. Lorsque l’on s’intéresse à modéliser la synchronisation du clignotement des lucioles, les mouvements coordonnés d’un banc de poissons, les formes géométriques dessinées par une nuée d’oiseaux, ou le comportement collaboratif d’un réseau de neurones, on retrouve des algorithmes répartis.
L’informatique est désormais fondamentalement répartie sur des réseaux, grands ou petits. Cette répartition décuple la puissance des ordinateurs et les rend souvent plus forts et plus efficaces. Mais elle les rend parfois incontrôlables. Apprivoiser cette informatique passe par l’étude de la discipline scientifique sous-jacente : l’algorithmique répartie. Cette discipline est tout aussi nécessaire à la compréhension de nombreux phénomènes naturels. La leçon inaugurale du cours du Collège de France racontera l’histoire de la quête d’universalité dans le contexte réparti en soulignant quelques résultats clés et quelques problèmes ouverts.
Rachid Guerraoui, Professeur à l’École Polytechnique Fédérale de Lausanne, Chaire « Informatique et sciences numériques » du Collège de France, EPFL- École Polytechnique Fédérale de Lausanne – Swiss Federal Institute of Technology in Lausanne
La version originale de cet article a été publiée sur The Conversation.
