Barbara Liskov (USA)

Prix Turing 2008

À 69 ans, la professeure Barbara Liskov du 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.

linuxfr

Page de Barbara Liskov

Aucun commentaire: