Journal Le prix Turing 2008 pour Barbara Liskov

Posté par ɹǝıʌıʃO le 11 mars 2009 à 15:46.

Étiquettes :

mar.

2009

À 69 ans, la professeure au MIT remporte la plus prestigieuse des récompenses en informatique. Largement considéré comme équivalent à un prix Nobel, le prix Turing est décerné chaque année par l'Association for Computing Machinery à une ou plusieurs personnes dont les contributions à l'informatique sont particulièrement brillantes.

Comme beaucoup de chercheurs de premier plan, Barbara Liskov a contribué à plusieurs domaines de l'informatique, principalement :

les langages de programmation, en particulier avec le support de la programmation répartie ;
la théorie des types, où elle a défini une nouvelle notion de type dérivé (T est un type dérivé de S si toute propriété prouvable sur les objets de S est prouvable sur les objets de T) ;
les bases de données, en particulier orientées objet ;
l'algorithmique répartie avec tolérance aux défaillances, et en particulier les plus difficiles de toutes ces défaillances : les processus byzantins.

Sur ces quatre points, c'est sans doute le dernier qui est le moins connu. On parle d'algorithmique répartie lorsque l'on écrit un algorithme fonctionnant non pas sur une seule machine, mais sur plusieurs machines reliées par un réseau de communication. C'est déjà amusant à ce stade, mais là où le sujet prend tout son intérêt, c'est lorsque l'on permet aux machines de tomber en panne, comme dans la vraie vie.

On distingue plusieurs niveaux de défaillances :

les pannes par arrêt définitif (crash) : la machine s'arrête sans prévenir en plein milieu d'un calcul. Si le système est asynchrone, comme les réseaux informatiques (si on ne leur ajoute pas de dispositif pour contourner le problème), un joli théorème (Fischer, Lynch, Paterson 1985) nous indique qu'il n'est pas possible de résoudre dans ce cadre même un problème simple comme celui du consensus, dans lequel les machines doivent se mettre d'accord pour décider la même valeur ;
les pannes par arrêt et redémarrage ;
les défaillances transitoires : la mémoire des machines et le contenu des canaux du réseau peuvent être modifiés arbitrairement. Ceci modélise par exemple les modification de la mémoire par des phénomènes physiques dus, par exemple, aux rayons cosmiques ou à une température trop élevée. Les techniques habituellement utilisées dans ce cadre sont la redondance modulaire et l'autostabilisation ;
les défaillances byzantines. Introduites par Lamport, Pease et Shostak en 1982, elles modélisent la situation dans laquelle un processus (une machine) se comporte arbitrairement, sans tenir compte de son programme, comme un traître dans le système. Leur origine remonte à un problème posé par la NASA, qui voulait des algorithmes aussi fiables que possible pour piloter ses appareils volants. Les défaillances byzantines sont, bien entendu, particulièrement difficiles à tolérer. L'algorithme de consensus byzantin le plus connu est sans doute Paxos (Lamport 1998), utilisé entre autres dans les bases de données de Google.

C'est pour l'ensemble de son œuvre que Barbara Liskov a été récompensée. L'ACM note ses contributions fondamentales aux langages de programmation, aux techniques de mise au point de logiciels et à l'algorithmique répartie. Ces deux derniers points sont à la fête ces derniers temps, puisque l'année dernière le domaine mis en valeur était le model-checking. En tous cas, nul doute que c'est un grand jour pour le génie logiciel, à tous les sens du terme.

# Turing Award

Posté par patrick_g (site web personnel) le 11 mars 2009 à 18:25. Évalué à 6.

Merci pour ce journal très intéressant.
Quelques liens en plus :
La citation du prix sur le site de l'ACM : http://awards.acm.org/citation.cfm?id=1108679&srt=all&am(...)
Un article sur MIT News : http://web.mit.edu/newsoffice/2009/turing-liskov-0310.html/
Un autre article avec une courte interview : http://www.ddj.com/hpc-high-performance-computing/215801518

On y apprends que Barbara Liskov est la toute première femme a avoir obtenu un doctorat en informatique aux USA (c'était en 1968).
# Mouches, cachez-vous

Posté par auve le 11 mars 2009 à 18:42. Évalué à 8.

la théorie des types, où elle a défini une nouvelle notion de type dérivé (T est un type dérivé de S si toute propriété prouvable sur les objets de S est prouvable sur les objets de T)

Quelques remarques un peu pédantes :

1/ Le terme de « théorie des types » n'est probablement pas le plus adapté dans la mesure où il se réfère plus habituellement à la théorie des lambda-calculs typés.

2/ On parle de sous-type, plutôt que de type dérivés. Je pense que parler de « type dérivé » insinue qu'il s'agit d'une histoire d'héritage, alors que c'est précisément ce qu'il ne faut pas confondre : héritage et sous-typage (grosso-modo « le type A est sous-type de B si tout A peut-être utilisé à la place d'un B ») sont distincts, et les confondre en violant le principe de substitution de Liskov s'est s'exposer à des ennuis... Les langages à objets typés mélangeant les deux idées nous tendent le bâton pour nous battre avec :-)

Pour les précisions : http://okmij.org/ftp/Computation/Subtyping/
- [^] # Re: Mouches, cachez-vous
  
  Posté par Victor le 11 mars 2009 à 21:17. Évalué à 3.
  
  J'ai tout lu !
  
  C'est très intéressant, mais je comprend pas pourquoi dans la solution (BRules) ça marche !
  
  En gros, il met le résultat d'un put (qui retourne un Bag) sur un objet de type Set dans une variable de type Set et ça marche comme ça par magie genre on peut mettre un Bag dans une variable Set ...
  
  Alors j'imagine qu'il y a un détail de C++ (que je ne connais pas du tout) qui m'échappe, une conversion implicite ou un truc du genre, mais alors, je ne vois pas du tout comment BRules pourrait être appliqué au Java, qui, je crois en être sûr, n'a pas du tout ce genre de comportement !
  Ou alors il faudrait explicitement construire un Set à partir du Bag sortant du put mais c'est un peu lourdingue...
  
  Si quelqu'un a une idée pour expliquer tout ça, ça m'intéresse :)
  - [^] # Re: Mouches, cachez-vous
    
    Posté par Gof (site web personnel) le 12 mars 2009 à 00:52. Évalué à 3.
    
    Il y a un constructeur de copie implicite de Bag vers Set, c'est le
    FSet::FSet(const FBag& bag)
    
    Voir par exemple http://publib.boulder.ibm.com/infocenter/comphelp/v8v101/ind(...)
    
    En Java, il faudrais explicitement apeller implicitement le contstructeur.
    Le code ressemblerais à un truc du genre
    FSet set = new FSet( put(new FSet(),2) );
    - [^] # Re: Mouches, cachez-vous
      
      Posté par Victor le 12 mars 2009 à 10:57. Évalué à 2.
      
      Ok, merci.
      
      Peut-être qu'appliquer BRules serait plus simple avec un langage comme Scala ( http://scala-lang.org ) qui propose des conversions implicites (mais qu'il faut explicitement définir bien sûr :) et qui propose des constructeurs moins moches quand on le veut (en particulier utilisé quand on fait des structures de données immutables, ça tombe bien)
      
      On pourrait même écrire quelque chose comme ça :
      val set: FSet = Fset().put(2)
      
      Avec une conversion implicite de FSet qui permet de lui ajouter la méthode put comme si elle lui appartenait (alors que non :) et une conversion implicite du FBag sortant du put vers FSet.
# Byzantine

Posté par ǝpɐןƃu∀ nǝıɥʇʇɐW-ǝɹɹǝıԀ (site web personnel) le 11 mars 2009 à 20:25. Évalué à 3.

Est-ce que cet adjéctif fait référence à un événement historique particulier ? Y aurait-il eu des cas de trahison particulièrement célèbre à Byzance ? Quelqu'un peut-il me rafraichir la mémoire s.v.p. ?
« IRAFURORBREVISESTANIMUMREGEQUINISIPARETIMPERAT » — Odes — Horace
- [^] # Re: Byzantine
  
  Posté par Antoine J. le 11 mars 2009 à 21:22. Évalué à -1.
  
  Le grand schisme d'Orient peut-être ?
  - [^] # Re: Byzantine
    
    Posté par windu.2b le 11 mars 2009 à 21:54. Évalué à 3.
    
    Ton exemple est un peu pauvre...
    C'est pas Byzance !
- [^] # Re: Byzantine
  
  Posté par Sylvain Sauvage le 12 mars 2009 à 13:21. Évalué à 5.
  
  Deux choses :
  1. le sens : en français, l’adjectif byzantin, au sens figuré, qualifie une pensée (souvent une politique) trop raffinée, trop travaillée, qui se contorsionne dans les détails. En anglais, la notion de complot et d’intrigue compliqués est encore plus forte. (Le sens en anglais est proche de celui de machiavélique en français.)
  
  Ce sens vient du fait que Byzance est réputée pour avoir été pourvue d’une administration très labyrinthique : des dizaines de niveaux hiérarchiques, des départements à ne plus savoir qu’en faire, des chefs de tout et n’importe quoi dans tous les coins, et donc une quasi impossibilité d’y naviguer.
  Un peu comme chez nous, quoi…
  
  2. l’origine : comme dit dans l’article, ce sont Lamport, Pease et Shostak qui ont donné une solution au problème des généraux byzantins. Ce problème est celui de généraux qui font le siège d’une cité et qui doivent communiquer et concevoir un plan alors que des traîtres peuvent se trouver parmi eux. La qualité byzantine des généraux sert surtout à appuyer l’idée qu’ils sont très malins, très sophistiqués, surtout les traîtres, et qu’il y a des chances non négligeables qu’ils se bouffent le nez les uns les autres à la moindre occasion.

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.