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
Nom : Fauconnier
Prénom : Hugues
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 |
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.
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.
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.