Publié le

Des consensus tout sauf mous

Michel Raynal
Michel Raynal

Michel Raynal, Professeur à l’Université de Rennes 1  et membre senior de l’Institut Universitaire de France est un passionné. Il aime les voyages, adore la littérature, ne se lasse pas des côtes bretonnes (malgré ses origines du Sud-Ouest), encore moins du rugby (probablement en raison de ces mêmes origines).  Michel aurait pu devenir un grand scientifique dans bien des domaines. C’est dans l’informatique qu’il est tombé, et plus particulièrement dans cette même région de l’Ouest où d’autres se sont retrouvés dans une marmite de potion magique. Michel Raynal est le lauréat du SIROCCO Innovation Award 2015 pour ses travaux en informatique distribuée. C’est l’occasion de découvrir ce domaine passionnant.

Un système distribué est un système composé de plusieurs entités (téléphone, capteur, ordinateur par exemple), connectées par un réseau de communication, c’est-à-dire qui peuvent communiquer  (en filaire, par wifi, etc.) et qui, ensemble,  s’attaquent à un problème comme de réaliser un calcul ou chercher de l’information. Nous vivons aujourd’hui dans un monde où la majorité des systèmes est distribuée. Par exemple, les données relatives aux comptes Facebook d’un ensemble d’amis sont dispersées aux quatre coins du monde ; pourtant lorsqu’un utilisateur met à jour son statut, tous ses amis doivent être notifiés, qu’ils soient connectés depuis le Maroc ou la Chine et que leurs données soient hébergées en Inde ou dans la Silicon Valley.  Nos données, comme celles des entreprises, sont distribuées sur des serveurs ; on parle du cloud. La même donnée peut être répliquée sur plusieurs serveurs pour des raisons de fiabilité notamment.

Turing s’est un jour posé la question de ce que sa machine universelle était capable de calculer. Malheureusement, son formalisme ne s’applique pas aux systèmes distribués. Évidemment, les experts se sont posés la question de savoir ce qu’il est possible de calculer dans un système distribué, notamment le problème du consensus qui a été particulièrement étudié. Le problème est le suivant : chaque entité propose une valeur et à la fin du calcul toutes doivent s’être mises d’accord sur l’une de ces valeurs. C’est le type de fonctionnalité dont on a besoin, par exemple, pour assurer la cohérence de données répliquées dans le Cloud. Pour illustrer le besoin de consensus, prenons l’exemple de données bancaires répliquées sur les machines A en France et B aux États-Unis. Ces données sont répliquées pour des raisons de tolérance aux pannes, de sorte que si une machine contenant ces données tombe en panne, l’autre continue de fonctionner. Ceci permet en outre aussi aux utilisateurs des États-Unis d’avoir un accès rapide depuis la machine B et aux utilisateurs européens d’avoir un accès rapide depuis la machine A. Considérons maintenant la situation suivante : Alice effectue un débit de 100$ depuis la France (sur la machine A) de son compte, dont le solde est de 1000$. L’ordre de débit est envoyé à la machine A mais aussi à la machine B pour assurer que les comptes soient cohérents. Le banquier, depuis la machine B, lui décide de verser des intérêts de 10% sur ce compte. Cet ordre de calcul d’intérêt est aussi envoyé aux deux machines. La communication prend du temps pour traverser l’Atlantique, si bien que la machine A reçoit d’abord l’ordre de débit puis celui des intérêts, appliquant donc 10% à un solde de 900$, le solde résultant est alors 990$, alors que la machine B, applique les intérêts, puis le débit, le solde étant alors de 1000$. Pour assurer un bon fonctionnement il est essentiel que les deux machines exécutent les instructions dans le même ordre et pour ce faire doivent atteindre un consensus.

Fisher, Lynch et Patterson [FLP85] ont montré en 1985 que le consensus était impossible dans un système réparti asynchrone* dans lequel les machines peuvent tomber en panne. La preuve est longue et intriquée et il faudrait demander à Michel Raynal de nous l’expliquer. Pour faire court, dans un système asynchrone, si une entité ne répond pas, on ne sait pas différencier si c’est une question de lenteur, ou si c’est une défaillance de l’entité. Et on peut soit attendre éternellement  le message alors que l’entité est défaillante ou alors prendre une décision et voir le message arriver trop tard et contredire notre décision. Michel Raynal a reçu le Sirocco Innovation Award en particulier pour ses travaux relatifs à ce problème de consensus, développant de nouveaux résultats à partir du théorème d’impossibilité de Fisher, Lynch et Patterson.

Que peut faire un chercheur en algorithmique distribuée quand un problème est impossible à résoudre ? Il étudie les hypothèses à relâcher pour que le problème devienne résoluble. Par exemple, pour le problème du consensus, on peut décider de prendre l’hypothèse que les messages entre les entités prennent un temps borné. Le consensus devient alors possible. Que peut-il faire quand on sait résoudre le problème ? Il peut chercher un algorithme plus efficace, par exemple plus rapide, demandant moins de messages, moins de calcul. Afin de  contourner l’impossibilité du consensus en asynchrone, Michel Raynal  avec ses collègues Achour Mostéfaoui et Sergio Rajsbaum ont par exemple proposé une nouvelle méthode à base de conditions [2]. L’idée est de dénombrer les « conditions », c’est à dire les configurations pour lesquelles on sait comment obtenir un consensus. Michel a alors conçu des algorithmes qui permettaient de s’adapter à ces conditions, rendant ainsi l’obtention d’un consensus possible [3].

Le prix de Michel Raynal reconnait ses contributions scientifiques. Pour conclure, on pourrait souligner que Michel assure la relève formant des jeunes chercheurs, et en leur  transmettant son enthousiasme et sa passion.

Anne-Marie Kermarrec, Inria Rennes

(*) Dans un système synchrone, les opérations sont coordonnées sous un contrôle centralisé basé sur les signaux d’une horloge. Par opposition, un système asynchrone, en revanche, n’a pas d’horloge globale. Les différentes entités doivent utiliser des communications pour coordonner leurs tâches.

Références

[1] Michael J. Fisher, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the Association for Computing Machinery, 32(2) :374–382, april 1985.

[2] Achour Mostéfaoui, Sergio Rajsbaum, Michel Raynal: Conditions on input vectors for consensus solvability in asynchronous distributed systems. J. ACM 50(6): 922-954 (2003)

[3] Achour Mostéfaoui, Sergio Rajsbaum, Michel Raynal. Efficient Condition-Based Consensus. SIROCCO 2001.

Publié le

L’informatique privée d’ordinateur

« L’informatique sans ordinateur », c’est le titre d’un article de Baptiste Mélès que je vous encourage à lire, dans Images des Mathématiques, une revue du CNRS. Et Baptiste d’enfoncer le clou dès l’incipit : « L’informatique a la fâcheuse réputation d’être la science des ordinateurs. » Il y aurait une informatique sans ordinateur ? Pire, les ordinateurs lui feraient-ils de l’ombre ?

Baptiste raconte l’informatique sans ordinateur à travers trois exemples :

  • Internet par pigeons voyageurs. Baptiste nous explique comment Internet fonctionne. Surtout, il nous explique que ce fonctionnement est indépendant de l’ordinateur et pourrait être réalisé… avec un dispositif de papier, d’encre et de pigeons.
  • La recherche d’un mot dans un dictionnaire. Il nous présente un algorithme « diviser pour conquérir », qu’un humain peut réaliser tout autant qu’un ordinateur.
  • La programmation sur papier. Il nous montre comment écrire des programmes en UML, un langage qui n’exige aucun ordinateur, qui permet à des êtres humains de spécifier des algorithmes, de collaborer entre eux, d’échanger des idées, même s’ils vont utiliser au final des logiciels très différents.

L’article de Baptiste est important parce qu’il s’attaque à la confusion que beaucoup font entre ordinateur et informatique.

Le mot « informatique » est tellement plus juste que computer science – la science des ordinateurs ! Reprenons la définition du texte de la Société Informatique de France :

L’informatique est la science et la technique de la représentation de l’information d’origine artificielle ou naturelle, ainsi que des processus algorithmiques de collecte, stockage, analyse, transformation, communication et exploitation de cette information, exprimés dans des langages formels ou des langues naturelles et effectués par des machines ou des êtres humains, seuls ou collectivement. L’informatique : la science au cœur du numérique

L’informatique n’est pas juste la science des ordinateurs. Depuis Turing, des chercheurs en informatique le montrent dans des résultats éblouissants aux frontières des mathématiques. Les enseignants le découvrent également aussi, notamment en primaire, à travers « l’informatique débranchée » (CS unplugged) Les élèves apprennent loin de tout ordinateur, autour de jeux, les notions au cœur de l’informatique, comme l’information et sa communication, les algorithmes et les ressources qu’ils demandent.

Et pour conclure, j’emprunterai une phrase de Baptiste : « Si l’ordinateur est l’objet informatique par excellence, c’est simplement parce que les concepts et méthodes informatiques y sont mobilisés de façon massive — mais non de façon exclusive. »

Serge Abiteboul,  Inria

En savoir plus ? Beaucoup d’activités débranchées sont présentées sur pixees.fr :

Introduire la notion de complexité pour classer les problèmes, et la recherche de solution optimale ou approchée ? Il suffit de trouver le plus court chemin avec une … planche à clou ! En savoir plus.
©Inria et pixees.fr
Faire découvrir la cryptographie sous forme de jeux aux plus petits ? Il suffit de deviner comment passer un message secret avec une clé secrète alors que … tout le monde voit tout ! Essayer de trouver vous aussi. En savoir plus.
©Image des maths. Le vidéo est une coproduction Tralalère, XD Production et Universcience.
Publié le

Attaque à l’italienne

Cet article fait suite à la série de billets sur le vote (Qu’est ce qu’un bon système de vote,  Le vote papier est il plus sûr que l’électronique, Les bonnes propriétés d’un système de vote électronique). Cette fois, il ne s’agit pas de discuter des différents systèmes propres à assurer la sécurité et la vérifiabilité d’une élection mais de relever des faiblesses propres à tous les systèmes.

Parmi ces faiblesses, une attaque amusante mais peu connue est « l’attaque à l’italienne ». Cette attaque est possible dès que l’espace des votes est important. Qu’est-ce que l’espace des votes ? En France, les élections sont en général « simples »: il s’agit de choisir un candidat (ou une liste) parmi une dizaine tout au plus. La situation est très différente dans d’autres pays. Prenons le cas de l’Allemagne. Lors de l’élection de la chambre d’un Lander (par exemple celui de la Hesse), les électeurs ont la liberté de composer la chambre de leur choix. Chaque parti politique propose une liste composée des candidats, dont le nombre est variable selon les partis. Un électeur peut choisir une liste et sélectionner ainsi tous les candidats de cette liste. Mais il peut également ajouter des voix à certains candidats, rayer certains candidats et ajouter des candidats d’autres listes. Un règlement complexe a été mis en place pour lever les éventuelles ambiguïtés et éviter un trop grand nombre de bulletins invalides. J’invite le lecteur curieux à lire l’article wikipedia (en allemand) pour une explication détaillée et illustrée des différentes règles, ou bien à utiliser l’interface mise en place pour explorer les différentes manières de remplir correctement un bulletin.

En quoi ce type d’élections peut-il être exploité pour mener une attaque ? La clef de l’attaque est la taille de l’espace des votes. Considérons ainsi le cas extrême du bulletin de vote utilisé lors d’une élection au sein de la commune de Francfort en 2011, où plus de 861 candidats étaient proposés pour un total de 93 sièges. Sans même calculer toutes les possibilités, un rapide calcul indique qu’il y a plus 93 choix parmi 861 soit plus de 10^126 façons différentes de remplir un bulletin. Si, de plus, on tient compte de la position des croix (1ère, 2ème ou 3ème colonne), on arrive alors à plus de 10^172 possibilités.
Un attaquant peut utiliser ce large choix pour « signer » un bulletin. Considérons le cas simplifié où les électeurs disposent de seulement 15 voix chacun et supposons que Charlie souhaite forcer Alice à voter pour le parti politique C sur le bulletin affiché ci-dessous. Il exige alors qu’elle remplisse le bulletin de la manière suivante:

  • 2 croix devant chaque candidat de la liste C (soit 8 voix au total)
  • 7 croix placées selon une combinaison particulière choisie par Charlie.
Bulletin rempli d'après une image de Sven Teschke (Licence : CC-BY-SA-2.0-DE)
Bulletin rempli d’après une image de Sven Teschke (Licence : CC-BY-SA-2.0-DE)

Lors du dépouillement, Charlie s’assurera qu’un tel bulletin est bien présent dans l’urne. Comme il est très improbable qu’un autre électeur ait choisi exactement la même combinaison des votes (notamment pour la partie affichée en rouge sur la figure), Alice est obligée d’obéir à Charlie sous peine de représailles après le dépouillement.

En France, ce type de scénarios est improbable car le nombre de choix est très limité. Cependant, c’est exactement pour cette raison qu’il est interdit d’apposer un signe distinctif sur un bulletin, que ce soit un symbole ou un mot particulier, ou bien un pliage original (un bulletin en forme de girafe par exemple). Notons tout de même que malgré cette interdiction, Charlie a encore la possibilité de forcer Alice à s’abstenir, ou plus précisément, de la forcer à voter nul. Il suffit en effet que Charlie demande à Alice de plier son bulletin en forme de girafe (ou tout autre signe distinctif convenu à l’avance). Un tel bulletin sera comptabilisé comme un vote nul et Charlie pourra s’assurer qu’Alice a bien suivi sa consigne en assistant au dépouillement.

Véronique Cortier, CNRS – Nancy

À la suite de la publication de ce billet, Roberto Di Cosmo m’a signalé que les attaques à l’italienne sont encore très vivaces dans la mémoire des Italiens. Ainsi, un film, « Le porteur de Serviette » avec Nanni Moretti, de 1991, fait de ce type d’attaque un élément de son histoire (voir l’extrait en italien). Une pétition (en italien) rappelle l’usage massif fait dans le passé de l’attaque à l’italienne sur les élections à choix multiples, qui ont été remplacées par d’autres schéma de votes. Cette pétition dévoile de nouvelles méthodes utilisées par la Mafia, signale qu’un vote peut se vendre 50 Euros au marché noir, et demande de nouveaux changements des règles électorales.

Publié le

La fable de l’écolier, de l’hôtelier et de l’informaticien,

GillesDowekUne interview de Gilles Dowek, auteur de la rubrique Homo sapiens informaticus dans Pour la Science.

Dans le numéro de Pour la Science de septembre, qui sort ce 19 août, la chronique Homo sapiens informaticus nous parle d’écoliers, d’hôteliers et d’informaticiens. Quelle est l’origine de cette chronique ?

G.D. L’idée de cette chronique m’est venue en lisant, dans la presse, à la fois des articles hostiles à l’enseignement de l’informatique, selon lesquels il est aussi utile de savoir programmer que de savoir changer les segments de pistons du moteur de sa voiture, et d’autres consacrés à l’inquiétude des chefs d’entreprises français, qui commencent à prendre conscience du risque d’être pris de vitesse par les plateformes de commerce en ligne, telles booking, airbnb, amazon, uber, … La relation entre les deux est frappante : d’un côté on continue de penser que les tâches techniques peuvent être déléguées à des techniciens, de l’autre on prend conscience que ces techniciens sont en train de prendre le pouvoir. Je voulais souligner que c’est précisément parce que les hôteliers, les libraires, les taxis, … ne comprennent pas ce qu’est un programme, qu’ils se laissent déposséder.

… oui de la presse quotidienne [1] au rapport du CNNum [2, page 87] le constat est unanime !

Comme les hôteliers auraient-ils pu se prémunir de ces informaticiens ?

G.D. C’est une fausse bonne idée de penser que le développement de logiciels peut se sous-traiter. Car contrairement aux mécaniciens qui, en général, changent les segments de pistons des moteurs des voitures de leurs clients, puis leur rendent ces voitures, les informaticiens exploitent souvent eux-même les objets qu’ils construisent. Les hôteliers auraient donc dû apprendre suffisamment d’informatique, sinon pour construire eux-même un site de réservation en ligne, au moins pour comprendre comment un tel site est construit et comment il permet d’échanger des informations avec ses clients. Ils auraient ainsi pu être les premiers à développer de tels sites et être les acteurs de la transformation de leur métier, au lieu d’en être les victimes.

… oui oui c’est justement ce que la chronique explique plus en détails !

Et au delà de cette fable, que trouve-t-on au fil des numéros dans la chronique Homo sapiens informaticus ?

J’essaie de montrer comment l’informatique change différents aspects de nos vies : le savoir, la pensée, l’écriture, l’école, le travail, l’économie, le corps, la mort, les institutions, …

Et pourquoi ce nom de Homo sapiens informaticus ?

Les historiens attirent notre attention sur le fait que chacune des révolutions techniques de la préhistoire – la pierre taillée, la pierre polie, l’agriculture, la céramique, la métallurgie, l’écriture, … – a complètement transformé l’humanité. Certains philosophes contemporains – notamment Michel Serres et, après lui, Michel Puech – nous montrent que cela s’applique aussi aux révolutions techniques plus récentes. En partant d’exemples concrets, j’essaie de comprendre, chronique après chronique, qui est homo sapiens informaticus et en quoi il diffère de son lointain ancêtre : l’homme du XXe siècle.

Publié le

Vous savez quoi ? « Girls Can Code! »

ÉducationTu ne seras pas forcément informaticienne, ma fille, mais la programmation informatique sera un sujet que tu maîtriseras dans ce monde devenu numérique : vazy !

C’est un stage gratuit pour apprendre à coder, comprendre les bases de l’informatique, et rencontrer d’autres personnes motivées à ne pas uniquement consommer, mais aussi co-construire le monde numérique. Un stage de programmation entre collégiennes et lycéennes du 24 au 29 août à Paris. Grâce à France-IOI et Prologin.

Et là quelqu’un (un mec, sûrement) va dire «mais pourquoi devraient-« elles´´ avoir un traitement particulier ?» … n’est ce pas l’aveu d’une dissymétrie ? Oui : une dissymétrie de la société [1].  Et dès qu’on se donne les moyens de ne pas créer cette dissymétrie, comme dans le cadre du concours Castor Informatique (avec 46% de filles), ou d’aider à la corriger [2] comme le fait cette initiative, alors les choses bougent.

Concrètement: Il est encore temps de s’inscrire: il suffit de remplir le formulaire sur gcc.prologin.org avant le 1er août. Le stage est entièrement gratuit et ouvert à toute fille née en 1995 ou après et qui n’est pas encore détentrice du baccalauréat.L’organisation prend en charge la restauration et l’hébergement à l’hôtel, mais pas les frais de transport jusqu’au lieu de stage. D’ici le stage, il est utile de se créer un compte sur France-ioi et se laisser guider par les exercices.

Serge Abiteboul et Thierry Viéville.

[1] Collet, Isabelle (2011). Effet de genre, le paradoxe des études d’informatique, TIC & Société, [En ligne], 5(1)

[2] Le MOOC Égalité Femmes-Hommes pour aider à comprendre et faire changer les choses à ce sujet

Note: Binaire essaie de ne pas sombrer dans le monde très masculin des sciences en ouvrant ses articles à un grand nombre d’amies. Au delà la journée des droits de la femme (Bonne fête des Meufes !, L’informatique: pour nous, les femmes!), on s’y interroge sur ce sujet (Où sont les femmes ?, Barbie est moins conne qu’on le dit) et parle bien volontiers de (Et un, et deux, et trois femmes Prix Turing !,  La pétulante Grace Hopper,  La visionnaire Ada Lovelace).