NOV 3 1971, NOV 4 1971; Computer programmers Mary Dick and David Stern super-¡vise computer operations directed by Ian Stewart, right. ©Getty - Photo By Bill Johnson/The Denver Post via Getty Images)
NOV 3 1971, NOV 4 1971; Computer programmers Mary Dick and David Stern super-¡vise computer operations directed by Ian Stewart, right. ©Getty - Photo By Bill Johnson/The Denver Post via Getty Images)
NOV 3 1971, NOV 4 1971; Computer programmers Mary Dick and David Stern super-¡vise computer operations directed by Ian Stewart, right. ©Getty - Photo By Bill Johnson/The Denver Post via Getty Images)
Publicité
Résumé

Comment vérifier que les algorithmes ne font pas n’importe quoi? Qu’est-ce que l'algorithmique répartie? Rachid Guerraoui, qui nous introduit au fonctionnement des réseaux d'ordinateurs, revient sur l’hypothèse que l’ordinateur obéit au modèle universel du mathématicien-informaticien Alan Turing.

avec :

Rachid Guerraoui (Informaticien, spécialiste mondial de l’algorithmique répartie, Directeur du laboratoire de calcul distribué à l’Ecole polytechnique fédérale de Lausanne (EPFL)).

En savoir plus

Comment Alan Turing a-t-il dessiné "le modèle d’un ordinateur qui pouvait exécuter tous les algorithmes possibles et imaginables"? demande Rachid Guerraoui. Concernant les ordinateurs, pourquoi l’universalité a-t-elle été perdue et qu’est-ce que cela veut dire vraiment? Enfin, comment interviennent dans cette histoire de la science informatique et la guerre froide et le réchauffement climatique? 

Alan Turing, portrait (au fond) et sculpture , composée d’environ un demi-million de pièces en ardoise du Pays de Galles, oeuvre de Stephen Kettle sur une commande de Sidney Frank
Alan Turing, portrait (au fond) et sculpture , composée d’environ un demi-million de pièces en ardoise du Pays de Galles, oeuvre de Stephen Kettle sur une commande de Sidney Frank
- Jon Callas / Alan Turing / Wikicommons

La science algorithmique répartie 

Rachid Guerraoui, qui a été professeur invité au MIT et qui a « exercé au sein des prestigieux laboratoires Hewlett Packard de Paolo Alto » est Professeur à l’Ecole polytechnique fédérale de Lausanne (EPFL). Pour l’année académique 2018- 2019, il est professeur invité au Collège de France, titulaire de la chaire annuelle, Informatique et sciences numériques, en partenariat avec l’INRIA. Ce chercheur passionné, qui a reçu en 2013 le prestigieux Google Focus Award pour son projet sur le Web Alter ego,  nous initie, aujourd’hui, dans le cadre de sa leçon inaugurale aux problèmes et aux enjeux de l’algorithmique répartie, 

Publicité

"discipline scientifique qui étudie les réseaux d’ordinateurs". 

Dans la présentation de sa chaire, il est rappelé :

« Jusqu’à une date récente, les fondamentaux de l’informatique supposaient pour la plupart qu’un algorithme s’exécute sur un seul ordinateur en tant que séquence d’opérations élémentaires. Mais, avec l’accroissement constant de la puissance de calcul des ordinateurs et du débit de transmission de données par les réseaux, les applications informatiques modernes deviennent de plus en plus souvent réparties sur plusieurs ordinateurs calculant en même temps et communiquant constamment. Cela demande une évolution profonde de la théorie et de la pratique des algorithmes pour les rendre parallèles et géographiquement distribués. »

Une histoire des algorithmes

Alors bienvenus dans la machine, dans ses réseaux et dans la science du calcul,  pour accomplir ce fascinant voyage dans l’histoire des algorithmes , des premiers calculs humains aux super ordinateurs ultra-rapides et dans les problèmes que posent la « science algorithmique répartie ». Nous y croiserons quelques grands "mathématiciens altruistes », selon la formule de Rachid Guerraoui, Euclide, Al-Khwarizmi (latinisé en Algoritmi), Pascal… et longuement, le fondamental Alan Turing, pour les débuts de la science informatique et son modèle de machine universelle. 

Nous allons découvrir avec l’évolution vers l’atomicité et des machines plus robustes et efficaces, les "théorèmes d’universalité et d’impossibilité du consensus" (comme les hommes, il n’est pas aisé de mettre d’accord les machines!), et nous découvrirons « les hypothèses permettant de contourner cette impossibilité ainsi que les algorithmes associés »…

Alors quelle est l'origine de la notion d’algorithme? Quelle est l'histoire de la discipline appelée « l'algorithmique répartie »? Quels sont les résultats fondamentaux de cette discipline qui peuvent expliquer la perte de l’universalité ? Et comment retrouver aujourd’hui cette universalité, au moins, sous une forme restreinte? 

Qu’est-ce qu’un  "adversaire malicieux qui introduit des valeurs extravagantes"?

Nous gagnons l’amphithéâtre du Collège de France, le 25 octobre2018 pour la leçon inaugurale de Rachid Guerraoui, intitulée « Algorithmes : à la recherche de l'universalité perdue »

Archive INA : reportage de Pierre CRENESSE chez IBM à New York, sur l'ordinateur, "cerveau électronique" en 1950