Contractualisation vague C 2009-2012

 

Unité de recherche

Dossier de demande de reconnaissance auprès du ministère

et éventuellement d’association à un EPST ou EPIC

 

UR3 : Fiche individuelle d’activité

enseignant-chercheur ou chercheur

concernant les 4 dernières années

 

Fiche à remplir par tous les enseignants-chercheurs et chercheurs

figurant à l’organigramme de l’unité

 

 

Nom : Fauconnier

 

Prénom : Hugues

 

Établissement public d’affectation statutaire ou d’exercice : Université Paris 7-Denis Diderot

 

Unité de recherche d’appartenance (label et n°, intitulé, établissement principal) : LIAFA UMR 7089, Laboratoire d’Informatique Algorithmique, fondements et applications.

 

(Une personne ne peut figurer que sur la liste d’une seule unité de recherche ; si exceptionnellement ce n’est pas le cas, ce ne peut être qu’en qualité de membre associé, à titre informatif)

 

Nom du responsable de l’unité :  Jean-Eric Pin

 

 

Enseignant-chercheur  x              HDR  x

 

Chercheur  o                 HDR o

 

Date de naissance : 17 novembre 1959

 

Corps-grade : Maître de Conférences

 

N° de téléphone : 01 44 27 28 43

 

Section du CNU 

et / ou du Comité National :  27

 

Bénéficiaire de la PEDR : X oui, depuis …2005…….                               

                                         

 

Domaine scientifique : Informatique

 

Département scientifique du CNRS : STIC

 

ou CSS INSERM :

 

ou CSS INRA :

 

ou CSS IRD :

 

ou autre :

 

Délégation du CNRS :

 

 

Appartenance à :          

- commission de spécialistes de l'établissement  oui X    n°…27…            

- conseil scientifique      non

           

 

1)       Thèmes de recherche développés

                             

 Algorithmique distribuée et tolérance aux pannes

La finalité de l'algorithmique distribuée tolérante aux pannes est d'offrir, malgré les pannes, des services fiables. Le champ d'application de ces services est vaste: réseaux de téléphones ou de communication, système de réservation,   gestion de trafic aérien, bourse, systèmes embarqués, etc.

     

Généralités

Dans le cadre de l'algorithmique distribuée tolérante aux défaillances, un problème fondamental est celui de l'accord (ou  consensus): comment arriver en présence de défaillances à un accord entre les processus sur une certaine valeur. Il est, en effet, difficile d'envisager des applications tolérantes aux défaillances sans pouvoir au moins arriver à un accord entre les participants. Or, un résultat fondamental (Fischer, Lynch et Paterson 1985)  prouve que, dans le  cas de systèmes asynchrones, un tel accord est impossible à atteindre dès qu'au moins un processus est susceptible de tomber en panne.

Une partie importante des travaux de recherche en algorithmique distribuée tolérante aux défaillances consistent à arriver à contourner ce résultat négatif.  Pour cela, il existe essentiellement trois possibilités. La première consiste à restreindre le caractère asynchrone du modèle considéré: c'est l'approche des modèles partiellement synchrones. On peut aussi modifier la spécification du consensus, soit en remplaçant la condition de terminaison par une terminaison sûre (= avec probabilité 1), soit en ajoutant des conditions sur les valeurs proposées. La troisième solution est celle des détecteurs de défaillances; elle consiste à maintenir le caractère asynchrone du système mais à supposer que les processus peuvent obtenir des informations sur les défaillances. D'un point de vue pratique, c'est souvent ce que l'on fait en utilisant des time-out: si un processus ne répond pas assez vite, on considère qu'il est en panne. Cependant, l'information ainsi obtenue est imparfaite et peut être erronée. D'un point de vue plus théorique cette approche est celle des détecteurs de défaillances : un détecteur de défaillances est une abstraction qui fournit aux processus des informations sur les  défaillances des processus. Pour l'essentiel, un détecteur de défaillances encapsule la connaissance nécessaire sur les défaillances des processus. Cette dernière approche a l'avantage d'être rigoureuse et formelle et a de nombreuses implications pratiques. Elle permet de développer une algorithmique dans un cadre asynchrone qui, en utilisant des détecteurs de défaillances, peut contourner les résultats d'impossibilité.  Elle est aussi modulaire: les détecteurs de défaillances peuvent être considérés comme une abstraction définie par ses propriétés. Cette abstraction étant ensuite réalisée dans un système partiellement synchrone (c'est-à-dire avec certaines  propriétés de synchronie).

 

Mes travaux concernent les thèmes suivants:

Détecteurs de défaillances

Chandra et Toueg ont  introduit dans les années 90 les détecteurs de défaillances non fiables. Ce sont des oracles qui donnent aux processus des indications sur les pannes, le plus souvent  sous la forme de liste de processus suspectés.  Ces indications peuvent être plus ou moins exactes. Ainsi, par exemple, le détecteur parfait,  donne des indications parfaites alors que le détecteur Oméga correspond à une élection ultime de leader. Si on enrichit un système asynchrone avec un détecteur de défaillances Oméga ou le détecteur parfait, on peut résoudre le consensus si une majorité de processus sont corrects.

 

Plus faible détecteur de défaillances

Un problème qui nécessite le détecteur parfait pour être résolu sera plus difficile, au sens de l'information nécessaire sur les pannes, qu'un problème qui peut être résolu avec un détecteur de défaillances comme Oméga. Pour certains problèmes on peut définir le plus faible détecteur de défaillances pour un problème: ce détecteur  permet de résoudre le problème et tout détecteur  de défaillances permettant de résoudre le problème permet de  le construire.

En déterminant quel est le détecteur de défaillances minimal pour résoudre un problème P, on détermine quelle est

la connaissance minimale sur les défaillances pour résoudre P. On peut ensuite déterminer quelles sont les conditions de synchronie qui doivent être assurées par le système sous-jacent pour assurer cette connaissance minimale sur les défaillances.

 

Élection de leader et implémentation de détecteurs de défaillances

 Quelles sont les conditions de synchronie nécessaires pour réaliser un détecteur de défaillances? Plus précisément:

 (1) comment l'implémenter efficacement?  (2) quelles sont les hypothèses  requises sur le synchronisme et la fiabilité du système partiellement synchrone?

 

Efficacité et pertinence de l'approche

Une question se pose maintenant naturellement: perd-on de la puissance de calcul et/ou de l'efficacité quand plutôt que de  développer les algorithmes directement dans un système partiellement synchrone, on les développe dans un système asynchrone avec un détecteur de défaillances puis on réalise ce détecteur dans un système partiellement synchrone.

 

Extension à d'autres types de pannes

Les détecteurs de défaillances ont prouvé leur efficacité dans le cas des pannes par arrêt (crash), il s'agit maintenant de faire un travail semblable pour les autres types de pannes et en particulier pour les pannes byzantines. Comme les défaillances byzantines peuvent être ``sémantiques'' (le processus n'exécute pas son code) la notion de détecteur de défaillances est plus difficile à définir (que signifie qu'un processus est défaillant à un instant donné?).

 

Transformations automatiques d'algorithmes

Le développement d'algorithmes robustes est difficile, d'autant plus difficile que les pannes considérées sont des pannes sévères. La possibilité de disposer d'une transformation automatique d'un algorithme tolérant des  pannes bénignes en un algorithme tolérant des pannes plus sévères permet de simplifier  grandement le travail du développeur.

 

Réseaux de capteurs

Des systèmes à grande échelle sous différentes formes existent actuellement: grilles de calcul, réseaux pair à pair, réseaux de capteurs... Le nombre de processus sur de tels systèmes (plusieurs dizaines de milliers à plusieurs dizaines de millions) change fondamentalement les hypothèses classiques. La défaillance d'un processus n'est plus un événement rare mais courant et il n'est pas raisonnable que tous les sites communiquent fréquemment avec tous les sites.

Plusieurs questions se posent alors :

Quel peut être le sens d'un problème comme le consensus dans ces systèmes ? Il faut définir de nouvelles  primitives plus adaptées et surtout les solutions actuelles sont clairement inadaptées à ce changement d'échelle. 

Comment réaliser la sûreté de fonctionnement dans un tel système ?  

Comment assurer la confidentialité des données ?

 

Sécurité et confidentialité

Le point de vue de la tolérance aux défaillances et celui de la cryptographie sont souvent différents cependant il existe de nombreux points de convergence et dans de nombreux cas les méthodes de l'algorithmique distribuées peuvent s'avérer utiles pour des problèmes liés à la cryptographie.

 

2)       Points forts de vos activités de recherche

Principaux résultats obtenus:

Détecteurs de défaillances

Plus faible détecteur de défaillances:

·         Pour l'exclusion mutuelle

·         Pour le consensus quelque soit le nombre de pannes

·         Pour implémenter un registre atomique (Détecteur de défaillances Sigma)

Hiérarchie du consensus de Herlihy pour l'implémentions de objets avec des détecteurs de défaillances (cette hiérarchie n'a plus dans ce cas que deux niveaux).

 

 

Élection de leader et implémentation de détecteurs de défaillances

            Implémentation de Oméga dans des systèmes avec une synchronie faible

            Définitions de systèmes partiellement synchrones permettant de réaliser le consensus

 

Efficacité et pertinence de l'approche des détecteurs de défaillances

            Algorithme optimal de consensus avec terminaison au plus tôt avec un détecteur de défaillances parfait.

            Algorithme de consensus à terminaison rapide pour des types de pannes particuliers

 

Extension à d'autres types de pannes

            Extension des détecteurs de défaillances pour des pannes par omissions

            Algorithmes de consensus pour ce type de pannes dans des modèles partiellement synchrones

            Applications à l'utilisation de modules fiables de sécurité

           Consensus avec des pannes byzantines dans des modèles partiellement synchrones.

 

Modèles et transformations automatiques

            Transformation automatique d'algorithmes tolérants des pannes bénignes en algorithmes tolérants des pannes plus sévères.

            Transformation automatique de problèmes et d'algorithmes avec détecteurs de défaillances pour le modèle avec omissions.

 

Réseaux de capteurs

            Tolérance aux défaillances dans les "population protocols"

            Notion de confidentialité dans les "population protocols"

            Détecteurs de collisions dans les réseaux de capteurs.

 

Sécurité et confidentialité

            Notion de confidentialité dans des réseaux anonymes

            Algorithmes distribués en présence d'adversaires byzantins

            Modules de sécurité et modèles à omissions.

 

 

3)       Liste (auteurs, titres, références) de vos 10 principales publications au cours des quatre dernières années, dans et hors le cadre de l’activité du laboratoire d’appartenance :

(Publications dans des revues avec comité de lecture, communications internationales avec actes et comité de lecture, ouvrages ou livres)

 

Publications dans des revues avec comité de lecture :

 

  Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, Bastian Pochon: The perfectly synchronized round-based model of distributed computing. Inf. Comput. 205(5): 783-815 (2007)

 

 Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, Petr Kouznetsov: Mutual exclusion in asynchronous systems with failure detectors. J. Parallel Distrib. Comput. 65(4): 492-505 (2005)

 

 

Communications internationales avec actes et comité de lecture

  Carole Delporte-Gallet, Hugues Fauconnier, Felix C. Freiling, Lucia Draque Penso, Andreas Tielmann: From Crash-Stop to Permanent Omission: Automatic Transformation and Weakest Failure Detectors. DISC 2007: 165-178

 

Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, Eric Ruppert: When Birds Die: Making Population Protocols Fault-Tolerant. DCOSS 2006: 51-66

 

Marcos Kawazoe Aguilera, Carole Delporte-Gallet, Hugues Fauconnier, Sam Toueg: Consensus with Byzantine Failures and Little System Synchrony. DSN 2006: 147-155

 

Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui: (Almost) All Objects Are Universal in Message Passing Systems. DISC 2005: 184-198

 

Carole Delporte-Gallet, Hugues Fauconnier, Stephanie Lorraine Horn, Sam Toueg: Fast fault-tolerant agreement algorithms. PODC 2005: 169-178

 

Emmanuelle Anceaume, Carole Delporte-Gallet, Hugues Fauconnier, Michel Hurfin, Gérard Le Lann: Designing Modular Services in the Scattered Byzantine Failure Model. ISPDC/HeteroPar 2004: 262-269

 

Marcos Kawazoe Aguilera, Carole Delporte-Gallet, Hugues Fauconnier, Sam Toueg: Communication-efficient leader election and consensus with limited link synchrony. PODC 2004: 328-337

 

Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, Vassos Hadzilacos, Petr Kouznetsov, Sam Toueg: The weakest failure detectors to solve certain fundamental problems in distributed computing. PODC 2004: 338-346

 

 

 

 

4)    Principales responsabilités scientifiques et administratives (dont direction de thèses) :

 

Je suis, avec Carole Delporte, initiatieur de l'Action Spécifique: Algorithmes Distribués et Applications (septembre 2003-septembre 2004).

Organisation en septembre 2004, de 4  journées thématiques de présentation des travaux de l'AS. Elles étaient organisées autour de quatre thèmes principaux: "Algorithmique distribuée", "Grilles et calculs parallèles", "Réseaux pair-à-pair et leurs applications", "Réseaux ad'hoc et dynamiques " et de deux tutoriaux: "Réseaux sociaux" et "Base de données et algorithmique distribuée".

 

 

Direction de thèse

            Petr Kouznetsov (participation à l'encadrement avec C. Delporte et R. Guerraoui) EPFL

            B. Pochon   (participation à l'encadrement avec C. Delporte et R. Guerraoui) EPFL

            Mohssen Abboud (encadrement Carole Delporte et Hugues Fauconnier), Détecteurs de défaillances et service tolérants aux pannes}, doctorant depuis octobre 2004. Bourse de 4 ans de l'état Syrien.

            Andreas Thielmann (encadrement Carole Delporte et Hugues Fauconnier), Vérification automatique des algorithmes distribués tolérants aux défaillances, doctorant depuis Février 2007. Bourse de 3 ans de l'Ile de France.

 

 

5)    Coopérations industrielles et valorisation (contrats, dépôts de brevets, logiciels) :

 

De fin  2001 à début 2004, j'ai  participé à l'étude Architectures Génériques pour le Spatial (AGS). Cette étude, commandée par le CNES à l'INRIA  était  sous la responsabilité scientifique de Gérard Le Lann (INRIA).

 

6)    Information scientifique et technique et vulgarisation :

Dans le cadre de l'AS : Algorithmes distribués et Applications. Nous avons organisé en septembre 2004, 4  journées thématiques de présentation des travaux de l'AS a destination des doctorants et des jeunes chercheurs .autour de quatre thèmes principaux:

"Algorithmique distribuée", "Grilles et calculs parallèles", "Réseaux pair-à-pair et leurs applications", "Réseaux ad'hoc et dynamiques " et de deux tutoriaux: "Réseaux sociaux" et "Base de données et algorithmique distribuée".

 

 

7)    Activités internationales (conférences invitées, contrats, séjours à l’étranger de plus de 2 mois...) :

       N.B. : Les séminaires et rapports ne seront pas mentionnés

 

 

·         PAI Germaine de Staël : "Algorithmique distribuée : détecteurs de défaillances et masquage de fautes". Collaboration  avec le laboratoire Distributed Programming Laboratory (LPD) de l'EPFL dirigé par Rachid Guerraoui. Responsable Carole Delporte. (Janvier 2004-decembre 2005)

 

·         PAI Germaine de Staël "Réseaux de capteurs". Collaboration  avec le laboratoire Distributed Programming Laboratory (LPD) de l'EPFL dirigé par Rachid Guerraoui. Responsable Hugues Fauconnier. Environ 2000 Euros par an. (Janvier 2007-decembre 2008)

 

·         PAI Procope " Sécurité et Algorithmique Distribuée". Collaboration avec Felix Freiling, chef du département Dependable Distributed systems à Mannheim et son équipe. Responsable Hugues Fauconnier (Janvier 2006-décembre 2007)

 

J’ai été membre des comités de programme des conférences internationales avec actes et comité de lecture suivantes :

 

 

8)    Activités d’enseignement :

 

Etablissement : Université Paris 7 Denis Diderot

 

Discipline : Informatique

 

Nature (CM, TD, TP) et volume (nombre d'heures effectives) : en moyenne par année :  CM (70) TD (10)TP (40)

 

Niveau (L, M, D, à l'exception de la direction des thèses) :L, M

 

 

9)    Demande particulière et mobilité :

 

Veuillez indiquer si vous avez effectué une mobilité dans les 12 derniers mois. Précisez également si vous souhaitez une mise à disposition ou un détachement auprès d’un autre établissement ou organisme de recherche ; une prolongation de mise à disposition ou de détachement ; un changement de section ; un changement d’affectation ; un rattachement à une commission interdisciplinaire.