Thèmes centraux de ma recherche : Tolérance aux défaillances dans les réseaux et les systèmes distribués.
Mots clés : Calculabilité du distribué, Réseaux, Sécurité, Tolérance aux défaillances, Algorithmique distribuée, Consensus et accord, Sûreté et Sécurité des systèmes informatiques, Systèmes distribués, Systèmes de Middleware, Réseaux de capteurs, Modèles de calcul.

Thèses:

Comités de programmes de conférences internationales: PODC’10, SSS’10, ALGOTEL’10, SSS’09, DISC’05, SRDS’05, ICDCS’05, ICDCN’13, NETYS’2013, NETYS’2014, OPODIS’2014, Co-Chair NETYS’15.

1 Activités d’enseignement

1.1 Enseignements

Au cours des dernières années j’ai donné des cours et des travaux dirigés dans des domaines très larges de l’informatique et s’adressant à des publics ayant des niveaux de connaissance variés. Cette diversité est nécessaire et utile.

En tant que responsable de licence je suis bien placé pour savoir qu’il faut, surtout avec l’informatique, être capable de couvrir l’ensemble de l’informatique actuelle tout en présentant aussi des résultats issus de la recherche.

L’informatique est une matière nouvelle pour les étudiants entrant à l’Université aussi l’enseignement de licence est très important et doit permettre aux étudiants d’acquérir les bases et surtout de leur faire assimiler le fait que l’informatique est une science sans pour autant négliger les aspects plus pratiques.

J’ai des compétences plus particulières dans les domaines suivants: Réseaux, Protocoles, Algorithmique distribuée, Programmation distribuée, Internet, Programmation Objets Java.

1.2 Responsabilités

Je suis par ailleurs responsable du L3 licence d’informatique à l’Université Paris-Diderot et responsable de la mention informatique de la licence Sciences technologies Santé de l’Université Paris-Diderot. A ce titre, j’ai participé à l’élaboration de la nouvelle maquette et à la définition des contenus des enseignements pour la campagne d’habilitation de la vague D des licences de l’Université Paris-Diderot.

Je crois que le socle de l’enseignement à l’Université reste et restera basé sur le modèle des cours tds tps en présence des étudiants. Mais il faut intégrer aussi les moyens numérique qui doivent être un élément naturel de l’enseignement. C’est dans cet esprit que je participe à un projet entre les licences d’informatique de la ComUE (Pari-Diderot, Paris-Descartes et Paris-Nord) qui vise à créer des documents numériques d’accompagnement pour les cours de licence d’informatique. Ce projet a passé la première phase de l’appel à projet de l’IDEX sur les licences.

J’ai d’autre part créé plusieurs documents en ligne sur la plate-forme Wandida (http://wandida.com/fr/?s=fauconnier). Il s’agit de séquences courtes d’une dizaine de minutes sur un sujet particulier (terminaison distribuée, argument de partition, problème de l’attaque coordonnée, preuve de l’impossibilité de l’attaque coordonée).

2 Activités de recherche

2.1 Présentation des travaux

L’essentiel de mes travaux de recherche concerne l’algorithmique répartie et plus particulièrement la question de la tolérance aux défaillances dans les modèles asynchrones.

Après des travaux anciens concernant la sémantique du parallélisme en termes de langages infinitaires [17], la parallélisation d’algorithmes [16] et la vérification de propriétés des calculs distribués [15], ma recherche s’est concentrée sur les problèmes liés au distribué. L’objectif actuel de mes travaux est d’arriver à définir la notion de calculabilité dans le monde du distribué.

A travers l’importance considérable des réseaux et de l’internet, tout le monde reconnaît aisément le rôle des calculs distribués. Cependant il s’agit encore d’un domaine de recherche relativement neuf et d’ailleurs peu enseigné. Pourtant, l’univers du distribué pose des questions nouvelles en ce qui concerne, entre autres, l’algorithmique et la notion de calculabilité.

Pour mieux comprendre commençons par rappeler le célèbre résultat d’impossibilité du consensus de Fischer, Lynch et Paterson [FLP85](Dijkstra Prize 2003). Le consensus est le problème simple suivant: des processus communicant entre eux par envoi/réception de messages ont chacun une valeur initiale (par exemple 0 ou 1) et doivent s’entendre pour décider de façon irrévocable une de ces valeurs de façon à ce que tous décident la même valeur et que la valeur décidée soit la valeur initiale de l’un d’entre eux. Il s’agit d’un problème d’accord très élémentaire et on comprend bien que la plupart des protocoles distribués nécessitent au moins un accord de ce genre. Le résultat d’impossibilité du consensus montre qu’il n’existe pas d’algorithme de consensus pour des communications asynchrones (i.e. il n’y a pas de borne sur le temps de réception des messages) dès qu’un processus peut tomber en panne franche (il ne fait plus de pas de calculs). Ce résultat n’est pas lié au modèle de communication par envoi/réception de messages et s’étend très simplement à des modèles où les processus partagent des registres. On peut aussi constater que ce résultat d’impossibilité est de nature différente des résultats d’indécidabilité des machines de Turing.

Avec les calculs distribués, on est donc en présence de problèmes qui sont impossibles à résoudre dans un système asynchrone. On peut alors se poser plusieurs questions différentes:

Oracles et détecteurs de défaillances

Comme pour la calculabilité pour les calculs séquentiels, les oracles sont un outil puissant pour le distribué.

Comme les détecteurs de défaillances peuvent être comparés par réduction ils permettent de comparer la difficulté des problèmes. 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 ainsi définir une hiérarchie sur les problèmes de tolérance aux défaillances: le problème P est plus difficile que le problème P′, si le détecteur minimal pour résoudre P est plus fort que celui pour résoudre P′. En d’autres termes, pour résoudre P il faut plus de connaissance sur les défaillances que pour résoudre P′.

Concernant les détecteurs de défaillances minimaux, dans [13], nous déterminons quel est le plus faible détecteur de défaillances pour résoudre le problème classique de l’exclusion mutuelle en présence de défaillances.

Dans [62] et [58], nous déterminons le plus faible détecteur de défaillances pour résoudre le consensus dans le cas où plus d’une majorité de processus peut tomber en pannes. Ce problème était un porblème ouvert depuis près de 10 ans. Ce résultat montre que ce plus faible détecteur de défaillances peut se décomposer en deux détecteurs de défaillances: le premier, Ω, est un détecteur de défaillances qui choisit de façon ultime un même processus correct pour tous en ce sens Ω réalise une élection ultime de leader. Le second, Σ, est le détecteur minimal pour réaliser un registre atomique; il assure essentiellement une condition de quorum. Intuitivement, on retrouve ainsi la décomposition classique entre “safety” et “liveness”: Ω assure la liveness (terminaison) du consensus alors que Σ assure la safety (pas de décision contradictoire).

Dans [63], nous montrons, que si l’on se restreint à des détecteurs de défaillances qui, dans un certain sens, ne peuvent pas deviner les futures défaillances, alors tous les détecteurs de défaillances permettant de résoudre le consensus pour un nombre quelconque de pannes sont équivalents au détecteur parfait (un détecteur parfait fournit des informations exactes sur les défaillances).

Plus récemment nous avons déterminé quel était le plus faible détecteur de défaillances pour le problème du n - 1-set consensus [44]. Le k-set consensus est un accord approché pour lequel les processus peuvent choisir jusqu’à k valeurs distinctes. Rappelons que les résultats d’impossibilité du k-set consensus sont des résultats difficiles dont la preuve fait appel à des techniques de topologie algébrique [HS99] (Gödel Prize 2004). Enfin, nous avons résolu le problème général du plus faible détecteur de défaillances pour le k-set consensus dans les modèles à mémoire partagée [36].

Dans [42], on montre que si les processus ne disposent que d’une mémoire finie, le problème du consensus devient plus facile concernant la détection des défaillances que celui de la diffusion fiable.

Dans [40] et [8], nous nous intéressons au problème plus théorique de la localité des calculs distribués et au problème de trouver quel est le plus faible détecteur de défaillances qui permet de résoudre une tâche (algorithme de décision dans lequel tous les processus corrects doivent décider).

On a vu que les deux conditions de l’impossibilité du consensus sont la possibilité de défaillances de processus et le caractère asynchrone du système. Les détecteurs de défaillances correspondent à la première, concernant la deuxième on peut définir les conditions permettant de résoudre un problème en terme de synchronie partielle de la communication. D’un point de vue plus “pratique” les approches en terme de détecteur de défaillances et en terme de partielle synchronie peuvent se correspondre: on peut essayer de définir quelles sont les conditions de synchronie sur les communications qui permettent de d’implémenter un détecteur de défaillances. Une démarche générale par rapport à un problème donné peut être de (1) déterminer le détecteur de défaillances minimal permettant de résoudre ce problème (2) définir un algorithme pour résoudre le problème avec ce détecteur minimal (3) déterminer quelles sont les conditions minimales dans un certain sens pour réaliser ce détecteur minimal. On obtient ainsi une solution “pratique” pour le problème à la condition que le système assure ces conditions de synchronie.

Il est donc intéressant de développer une algorithmique des détecteurs de défaillances ([67], [68], [69], [61], [64] et [14]). Le détecteur de défaillances Ω, correspondant à une élection ultime de leader, étant le détecteur minimal pour le consensus joue un rôle fondamental. Dans [59], [55] et [11] nous définissons les conditions minimales de synchronie pour la réalisation de l’élection de leader (implémentation de Ω). Ces travaux sont à l’origine d’une recherche assez active qui a donné lieu à plus d’une vingtaine de publications d’autres chercheurs.

Des versions “auto-stables” de l’implémentation de Ω ont été proposées dans [46] et [75]. [32] et [75] correspondent à une extension de cette notion de leader à un cadre plus large: au lieu de déterminer un leader qui soit un processus non-défaillant, il s’agit d’élire un leader ayant de bonnes propriétés de ponctualité de communication. Cette approche peut permettre, par exemple, de construire dans des réseaux des tables de routages en présence de défaillances.

Notons enfin que dans [5], la notion de système partiellement synchrone classique est étendue par une notion de “set timeliness” qui définit des relations de ponctualité entre ensembles de processus et qui permet de définir des systèmes partiellement synchrones en mémoire partagée permettant de résoudre le k-set consensus. On peut ainsi arriver à une correspondance entre des classes de problèmes comme le k-set consensus, des propriétés du “scheduling” et des propriétés concernant la détection de défaillances.

Adversaires

La notion d’adversaires peut être une alternative complémentaire aux détecteurs de défaillances. Un adversaire définit quel est l’ensemble des processus qui peuvent être défaillants dans une exécution. Par exemple, on peut considérer l’adversaire pour lequel p ou bien q (mais pas les deux) peuvent tomber en panne. Dans ce cadre nous avons étudié les relations qui peuvent exister entre adversaires et nous avons déterminé pour certains types de tâches (les tâches “colorless”), en présence de quels adversaires elles peuvent être résolues. En complétant ce qui a été écrit plus haut on arrive à définir une hiérarchie de problèmes (les k-set consensus) et à la faire correspondre à une hiérarchie d’adversaires. Ainsi [37] et [7] permettent de définir une hiérarchie entre ces tâches définie par le type d’adversaires qui permettent de les résoudre. Cette notion d’adversaire permet aussi de faire le lien entre les défaillances de processus et le k-set consensus. Notons que [37] a reçu le “best paper award” dans cette conférence et que la notion d’adversaire a depuis été reprise dans de nombreux travaux.

Dans un sens un peu différent, la notion d’adversaire correspond à un paramètre du modèle qui peut être utilisé de façon “négative”. Par exemple, le fait qu’un processus puisse être byzantin (ne pas respecter son code) peut être utilisé pour empêcher le consensus. De la même façon l’anonymat des processus renforce la puissance de l’adversaire. Dans [49], nous montrons que le problème de l’accord dans le cas byzantin peut se résoudre avec des conditions faibles de synchronie. Dans le cas où les processus sont totalement anonymes des résultats classiques montrent que peu de choses peuvent être calculées, il est intéressant de considérer le cas où des processus peuvent partager la même identité on parlera alors de processus homonymes [30]. En combinant les défaillances byzantines et l’anonymat partiel des processus on montre dans [3] les conditions dans lesquelles le consensus reste possible dans des systèmes synchrones et partiellement synchrones. Notons aussi concernant l’anonymat total les résultats de [38] et pour l’anonymat partiel [20], [26] et [27].

Tâches et objets partagés

De façon classique, on considère deux grandes familles de modèles pour les systèmes distribués asynchrones: les modèles à mémoire partagée dans lesquels l’échange d’information entre processus se fait par l’intermédiaire de registres atomiques et les modèles à échange de messages où la seule interaction entre processus a lieu par une communication asynchrone.

Dans le contexte des systèmes à mémoire partagée, on définit des objets atomiques partagés comme, par exemple, le “test-and-set”. Un tel objet est défini par une spécification séquentielle qui indique quel doit être le comportement de l’objet si les processus y accèdent de façon non concurrente. On peut aussi considérer n’importe quel type de données comme par exemple une pile ou une file et c’est d’ailleurs ce qui est fait dans les classes java.util.concurrency de Java.

Avec le développement des architecture “multi-core”, la notion d’objets atomiques partagés est naturelle: ce sont les primitives existant ou pouvant être réalisées dans ces architectures. Il est intéressant de pouvoir comparer la puissance relative de ces objets. En considérant des implémentations “wait-free” c’est-à-dire telles que les appels à l’objet partagé peuvent toujours terminer sans la participation des autres processus, un résultat ancien [Her91] montre que, dans ce cadre, le consensus est universel dans le sens où il permet la réalisation de n’importe quel autre objet.

Pouvoir hiérarchiser ces objets suivant leur puissance de calcul, ou encore suivant les conditions en terme d’informations sur les défaillances que leurs implémentations nécessitent, permet de déterminer quelles sont les meilleures primitives. En déterminant quel est le plus faible détecteur de défaillances pour implémenter des registres atomiques [58] on aide à la clarification des relations entre les modèles à mémoire partagée et les modèles à envoi/réception de messages.

Une mesure classique pour définir la puissance des objets partagés est le nombre de consensus qui indique entre combien de participants de tels objets permettent de réaliser le consensus. On obtient ainsi une hiérarchie stricte de ces objets. Dans les modèles à échange de messages la situation est différente: cette hiérarchie se réduit à deux éléments [53] et [10]. D’un point de vue pratique cela signifie qu’implémenter dans de tels systèmes n’importe quel objet non trivial est aussi difficile qu’implémenter le consensus. On peut interpréter ces résultats on notant qu’il y a une différence entre implémenter des objets et supposer qu’ils sont donnés: l’implémentation écrase la hiérarchie et rend tous ces objets équivalents (à partir du moment où ils sont strictement plus puissants que les registres atomiques). Ces résultats s’obtiennent grâce à la minimalité des détecteurs de défaillances. Ces travaux ont fait l’objet d’une publication dans journal of the ACM [10].

D’une manière générale, la comparaison des modèles avec partage de mémoire et à échange de messages est un sujet particulièrement intéressant. Dans [43] nous montrons que le problème du n- 1-set consensus est moins difficile que celui de la réalisation de registres atomiques. Ainsi, pouvoir implémenter des registres atomiques permet de réaliser du n- 1-set consensus alors que le n- 1-set consensus ne peut être implémenté dans un modèle dans lequel les registres sont donnés. Ainsi on vérifie une fois de plus que donner un objet atomique comme une “boîte noire” ou par une implémentation ne revient pas au même.

Dans le cadre des modèles à mémoire partagée, dans [25] et [1] on montre comment on peut étendre la notion de détecteur de défaillances à des “wait-free tasks”.

Enfin concernant la complexité des calculs distribués, un problème important est celui du nombre de registres partagés utilisés. Ainsi il a été prouvé il y a près de 20 ans [FHS98] qu’une borne inférieure pour le nombre de registres pour le consensus (randomisé ou “obstruction free” - une condition qui assure la terminaison) est O( --
√ n

) (n étant le nombre de processus) alors que les meilleurs algorithmes connus sont en O(n). [23] et [2] montrent que n Mutli-Writer-Multi-Reader registres sont nécessaires et suffisants pour réaliser un système où chacun des n processus a son propre (Single-Writer-Multi-Reader) registre. Dans [22], on montre que le k-set consensus (obstruction free) peut être résolu avec moins de n registres.

Enfin [21] présente un algorithme de renommage linéaire. Notons que ce papier a été écrit en collaboration avec L. Lamport (c’est d’ailleurs à ma connaissance actuellement le dernier article de recherche publié par L. Lamport) et que l’algorithme est entièrement prouvé dans le système TLA+.

Protocoles de population

Toujours dans le cadre des calculs distribués, on peut définir d’autres modèles comme celui des protocoles de population [AAD+04] correspondant à un modèle de réseau de capteurs anonymes pouvant communiquer deux à deux.

Dans [52] et [50] nous essayons de déterminer comment définir des notions de tolérance aux défaillances dans ce modèle. En particulier, nous proposons un algorithme qui permet la transformation automatique d’un problème non tolérant aux défaillances en un algorithme tolérant à certains types de défaillances.

Un autre aspect intéressant de ce modèle est l’anonymat. Dans [48] nous montrons que l’anonymat des capteurs permet de toujours pouvoir rendre les calculs “privés”: un capteur ne peut obtenir d’autres informations concernant les valeurs initiales des autres capteurs que celles qu’il pourrait déduire du résultat final du calcul.

Enfin, dans [74], nous étudions dans quelle mesure les outils de vérification en model-checking classiques comme SPIN ou PRISM peuvent s’appliquer à des protocoles de population. Le fait que la puissance de calcul des protocoles de population soit l’arithmétique de Presburger qui est décidable devrait permettre une vérification infinie pour les protocoles de population. Notons que ce papier a été écrit en collaboration avec M. Sighieranu membre de l’équipe vérification du liafa. Cet article et celui publié avec L. Lamport peuvent être considérés comme étant à l’intersection de la vérification et de l’algorithmique distribuée.

Remarques et perspectives

La question de la notion calculabilité dans le monde du distribué reste au centre de mes travaux de recherche. De nombreux progrès ont été réalisés, et sans doute la compréhension des calculs distribués s’est largement améliorée. Cependant une approche plus systématique paraît utile. Cette approche n’est pas que théorique, et un taxonomie précise des modèles et de leur puissance relative (au sens d’une transformation algorithmique des uns vers les autres) aurait des implications pratiques dans le monde du dsitribué.

Il reste quelques thèmes de recherche importants, tout d’abord la notion de tâche dans les modèles à mémoire partagée permet sans doute une approche intéressante au moins d’un point de vue formelle. La question de la complexité en terme de nombre de registres reste presque entièrement ouverte.

La notion de modèles partiellement synchrones a surtout été étudiée dans les modèles à envoi/réception de messages, il est intéressant de l’approfondir aussi dans les modèles à mémoire partagée. A la notion de ponctualité des messages correspond (avec un sens légèrement différent) la notion de “schedule”. Définir les propriétés des “schedules” permettant de résoudre tel ou tel problème est en soi intéressant.

Par ailleurs, les questions de l’anonymat ou de l’homonymie des processus et des adversaires byzantins peuvent avoir des conséquences pratiques intéressantes dans le domaine par exemple de la sécurité (avec les notions d’adversaires byzantins et la question de l’homonymie qui peut être rapprochée d’une forme de “privacy”).

Enfin, dans l’ensemble de mes travaux, la question du réseau en tant que graphe est presque toujours absente (en général le graphe de communication est supposé être un graphe complet) et la prise en compte du graphe de communication est l’un des objectifs de mes recherches.

Tous ces travaux sont réalisés en collaboration avec les meilleurs chercheurs au niveau international, en particulier M. Aguilera (VMWare), C. Delporte (LIAFA Paris-Diderot), E. Gafni (UCLA), R. Guerraoui (EPFL Lausanne), L. Lamport (Microsoft), S. Rajbaum (UNAM), S. Toueg (University of Toronto).

2.2 Encadrement doctoral et scientifique

2.3 Diffusion scientifique et valorisation

Plus anciennement (2003), j’ai, avec C. Delporte et R. Guerraoui, organisé l’école de printemps du LIAFA-PPS sur le thème de l’algorithmique distribuée à Porquerolles (Var). Nous avons obtenu la participation des orateurs suivants F. Armand (Jaluna-Chorus), J. Beauquier (LRI), P. Felber (Université de Nice), P. Fraigniaud (LRI), E. Gafni (UCLA), E. Goubault (CEA), S. Kutten (Technion), L. Lamport (Microsoft), G. Le Lann (INRIA), D. Malkhi (Université de Jerusalem), F. Mattern (ETH), D. Powell (LASS), M. Raynal (IRISA), P. Verissimo (Université de Lisbonne). Cette école a réuni une cinquantaine de participants, et a reçu le label d’école thématique du CNRS.

J’ai aussi participé au projet ATR de l’action DRET/MENESR/CNRS “maîtrise des systèmes complexes réactifs et sûrs” dont le but était de réaliser un accord temps réel en présence de défaillances. Dans ce projet intervenait des partenaires industriels (Thomson-CSF, Dassault Aviation et AXLOG) et des partenaires académiques (INRIA, IMAG, LIAFA, LIX). Une solution algorithmique a été développée par AXLOG à partir d’un algorithme que nous avons proposé avec le LIAFA [70, 71]. Cette solution a ensuite été validée par les partenaires industriels.

De 2001 à 2004 j’ai participé à l’étude Architectures Génériques pour le Spatial (AGS) commandée par le CNES à l’INRIA. Les résultats de cette étude ont été présentés au CNES et ont donné lieu à deux publications [56, 57].

2.4 Responsabilités scientifiques

3 Responsabilités administratives

4 Publications

Publications dans Journal of the ACM , TCS , Distributed Computing, et JPDC. Un article de vulgarisation dans TSI.

Articles généraux d’autres auteurs.

[AAD⁺04] Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta. Computation in networks of passively mobile finite-state sensors. In Soma Chaudhuri and Shay Kutten, editors, PODC, pages 290–299. ACM, 2004.

[Ben83] Michael Ben-Or. Another advantage of free choice: Completely asynchronous agreement protocols. In Proceedings of the 2nd ACM Symposium on Principles of Distributed Computing, pages 27–30, August 1983.

[CT96] Tushar Deepak Chandra and Sam Toueg. Unreliable failure detectors for reliable distributed systems. Journal of the ACM, 43(2):225–267, March 1996.

[DLS88] Cynthia Dwork, Nancy A. Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM, 35(2):288–323, April 1988.

[FHS98] Faith Ellen Fich, Maurice Herlihy, and Nir Shavit. On the space complexity of randomized synchronization. J. ACM, 45(5):843–862, 1998.

[FLP85] Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374–382, April 1985.

[Her91] Maurice P. Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems, 13(1):123–149, January 1991.

[HS99] Maurice Herlihy and Nir Shavit. The topological structure of asynchronous computability. Journal of the ACM, 46(6):858–923, 1999.

Articles dans des revues internationales

[1] Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, and Petr Kuznetsov. Wait-freedom with advice. Distributed Computing, 28(1):3–19, 2015. doi:10.1007/s00446-014-0231-6.

[2] Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, and Sergio Rajsbaum. Linear space bootstrap communication schemes. Theor. Comput. Sci., 561:122–133, 2015. doi:10.1016/j.tcs. 2014.10.013.

[3] Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, Anne-Marie Kermarrec, Eric Ruppert, and Hung Tran-The. Byzantine agreement with homonyms. Distributed Computing, 26(5-6):321–340, 2013.

[4] Carole Delporte-Gallet, Hugues Fauconnier, and Hung Tran-The. Byzantine agreement with homonyms in synchronous systems. Theor. Comput. Sci., 496:34–49, 2013.

[5] Marcos K. Aguilera, Carole Delporte-Gallet, Hugues Fauconnier, and Sam Toueg. Partial synchrony based on set timeliness. Distributed Computing, 25(3):249–260, 2012.

[6] Carole Delporte-Gallet and Hugues Fauconnier. Objets partagés et détecteurs de défaillances. Technique et Science Informatiques, 30(7):841–871, 2011.

[7] Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, and Andreas Tielmann. The disagreement power of an adversary. Distributed Computing, 24(3-4):137–147, 2011.

[8] Carole Delporte-Gallet, Hugues Fauconnier, and Sam Toueg. The minimum information about failures for solving non-local tasks in message-passing systems. Distributed Computing, 24(5):255–269, 2011.

[9] Carole Delporte-Gallet, Stéphane Devismes, and Hugues Fauconnier. Stabilizing leader election in partial synchronous systems with crash failures. J. Parallel Distrib. Comput., 70(1):45–58, 2010.

[10] Carole Delporte-Gallet, Hugues Fauconnier, and Rachid Guerraoui. Tight failure detection bounds on atomic object implementations. J. ACM, 57(4), 2010.

[11] Marcos Kawazoe Aguilera, Carole Delporte-Gallet, Hugues Fauconnier, and Sam Toueg. On implementing omega in systems with weak reliability and synchrony assumptions. Distributed Computing, 21(4):285–314, 2008.

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

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

[14] Carole Delporte-Gallet, Hugues Fauconnier, Jean-Michel Hélary, and Michel Raynal. Early stopping in global data computation. IEEE Trans. Parallel Distrib. Syst., 14(9):909–921, 2003.

[15] Bernadette Charron-Bost, Carole Delporte-Gallet, and Hugues Fauconnier. Local and temporal predicates in distributed systems. ACM Trans. Program. Lang. Syst., 17(1):157–179, 1995.

[16] Carole Delporte-Gallet, Hugues Fauconnier, and Maurice Nivat. Parallélisation d’algorithmes avec un nombre fixe de processeurs. ITA, 24:353–386, 1990.

[17] Hugues Fauconnier. Semantique asynchrone et comportements infinis en csp. Theor. Comput. Sci., 54:277–298, 1987.

Publications dans les principales conférences internationales dans le domaine (PODC, DISC, ICDCS, SPAA) et aussi dans des conférences internationales plus spécialisées (SIROCCO, ICDCN, SSS, NETYS).

Conférences internationales avec comité de lecture

[18] Carole Delporte-Gallet, Hugues Fauconnier, and Michel Raynal. An exercise in concurrency: From non-blocking objects to fair objects. In International Conference on Network-Based Information Systems( NBiS 2014), Salerno, Italie, September 10-14. 2014.

[19] Carole Delporte-Gallet, Hugues Fauconnier, and Michel Raynal. Fair synchronization in the presence of process crashes and its weakest failure detector. In 33rd IEEE International Symposium on Reliable Distributed Systems, SRDS 2014, Nara, Japan, October 6-9, 2014, pages 161–170. 2014. doi:10.1109/SRDS.2014.18.

[20] Carole Delporte-Gallet, Hugues Fauconnier, and Hung Tran-The. Leader election in rings with homonyms. In Guevara Noubir and Michel Raynal, editors, Networked Systems - Second International Conference, NETYS 2014, Marrakech, Morocco, May 15-17, 2014. Revised Selected Papers, volume 8593 of Lecture Notes in Computer Science, pages 9–24. Springer, 2014. doi:10.1007/978-3-319-09581-3_2.

[21] Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, and Leslie Lamport. Adaptive register allocation with a linear number of registers. In Distributed Computing - 27th International Symposium, DISC 2013, Jerusalem, Israel, October 14-18, 2013. Proceedings, volume 8205 of Lecture Notes in Computer Science, pages 269–283. Springer, 2013. doi:10. 1007/978-3-642-41527-2_19.

[22] Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, and Sergio Rajsbaum. Black art: Obstruction-free k-set agreement with $|$ mwmr registers $|$ < $|$ proccesses $|$ . In Networked Systems - First International Conference, NETYS 2013, Marrakech, Morocco, May 2-4, 2013, Revised Selected Papers, volume 7853, pages 28–41. Springer, 2013. doi:10.1007/ 978-3-642-40148-0_3.

[23] Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, and Sergio Rajsbaum. Linear space bootstrap communication schemes. In Distributed Computing and Networking, 14th International Conference, ICDCN 2013, Mumbai, India, January 3-6, 2013. Proceedings, volume 7730 of Lecture Notes in Computer Science, pages 363–377. Springer, 2013.

[24] Carole Delporte-Gallet, Hugues Fauconnier, and Hung Tran-The. Uniform consensus with homonyms and omission failures. In Distributed Computing and Networking, 14th International Conference, ICDCN 2013, Mumbai, India, January 3-6, 2013. Proceedings, volume 7730 of Lecture Notes in Computer Science, pages 161–175. Springer, 2013.

[25] Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, and Petr Kuznetsov. Wait-freedom with advice. In ACM Symposium on Principles of Distributed Computing, PODC ’12, Funchal, Madeira, Portugal, July 16-18, 2012, pages 105–114. ACM, 2012.

[26] Carole Delporte-Gallet, Hugues Fauconnier, and Hung Tran-The. Byzantine agreement with homonyms in synchronous systems. In Distributed Computing and Networking - 13th International Conference, ICDCN 2012, Hong Kong, China, January 3-6, 2012. Proceedings, volume 7129 of Lecture Notes in Computer Science, pages 76–90. Springer, 2012.

[27] Carole Delporte-Gallet, Hugues Fauconnier, and Hung Tran-The. Homonyms with forgeable identifiers. In Structural Information and Communication Complexity - 19th International Colloquium, SIROCCO 2012, Reykjavik, Iceland, June 30-July 2, 2012, Revised Selected Papers, volume 7355 of Lecture Notes in Computer Science, pages 171–182. Springer, 2012.

[28] Julien Clement, Carole Delporte-Gallet, Hugues Fauconnier, and Mihaela Sighieranut. Guidelines for the verification of population protocols. In 31st International Conference on Distributed Computing Systems, Mineneapolis, 2011. 2011.

[29] Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, and Petr Kuznetsov. Brief announcement: On the meaning of solving a task with a failure detector. In Distributed Computing - 25th International Symposium, DISC 2011, Rome, Italy, September 20-22, 2011. Proceedings, volume 6950 of Lecture Notes in Computer Science, pages 145–146. Springer, 2011.

[30] Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, Tran-Te Hung, Anne-Marie Kermarrec, and Eric Ruppert. Byzantine agreement with homonyms. In PODC 2011, San Jose, USA, 2011. 2011.

[31] Carole Delporte-Gallet, Stéphane Devismes, and Hugues Fauconnier. Approximation of delta-timeliness. In Shlomi Dolev, Jorge Arturo Cobb, Michael J. Fischer, and Moti Yung, editors, Stabilization, Safety, and Security of Distributed Systems - 12th International Symposium, SSS 2010, New York, NY, USA, September 20-22, 2010. Proceedings, volume 6366 of Lecture Notes in Computer Science, pages 435–451. Springer, 2010.

[32] Carole Delporte-Gallet, Stéphane Devismes, Hugues Fauconnier, and Mikel Larrea. Algorithms for extracting timeliness graphs. In Boaz Patt-Shamir and Tinaz Ekim, editors, Structural Information and Communication Complexity, 17th International Colloquium, SIROCCO 2010, Sirince, Turkey, June 7-11, 2010. Proceedings, volume 6058 of Lecture Notes in Computer Science, pages 127–141. Springer, 2010.

[33] Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, and Anne-Marie Kermarrec. Brief announcement: byzantine agreement with homonyms. In Friedhelm Meyer auf der Heide and Cynthia A. Phillips, editors, SPAA 2010: Proceedings of the 22nd Annual ACM Symposium on Parallel Algorithms and Architectures, Thira, Santorini, Greece, June 13-15, 2010, pages 74–75. ACM, 2010.

[34] Marcos Kawazoe Aguilera, Carole Delporte-Gallet, Hugues Fauconnier, and Sam Toueg. Partial synchrony based on set timeliness. In Srikanta Tirthapura and Lorenzo Alvisi, editors, Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing, PODC 2009, Calgary, Alberta, Canada, August 10-12, 2009, pages 102–110. ACM, 2009.

[35] Carole Delporte-Gallet and Hugues Fauconnier. Two consensus algorithms with atomic registers and failure detector omega. In Vijay K. Garg, Roger Wattenhofer, and Kishore Kothapalli, editors, Distributed Computing and Networking, 10th International Conference, ICDCN 2009, Hyderabad, India, January 3-6, 2009. Proceedings, volume 5408 of Lecture Notes in Computer Science, pages 251–262. Springer, 2009.

[36] Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, and Andreas Tielmann. Ba: The disagreement power of an adversary: extended abstract. In Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing, PODC 2009, Calgary, Alberta, Canada, August 10-12, 2009, pages 288–289. 2009.

[37] Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, and Andreas Tielmann. The disagreement power of an adversary. In Idit Keidar, editor, Distributed Computing, 23rd International Symposium, DISC 2009, Elche, Spain, September 23-25, 2009. Proceedings, volume 5805 of Lecture Notes in Computer Science, pages 8–21. Springer, 2009.

[38] Carole Delporte-Gallet, Hugues Fauconnier, and Andreas Tielmann. Fault-tolerant consensus in unknown and anonymous networks. In 29th IEEE International Conference on Distributed Computing Systems (ICDCS 2009), 22-26 June 2009, Montreal, Québec, Canada, pages 368–375. IEEE Computer Society, 2009.

[39] Carole Delporte-Gallet, Hugues Fauconnier, Andreas Tielmann, Felix C. Freiling, and Mahir Kilic. Message-efficient omission-tolerant consensus with limited synchrony. In 23rd IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2009, Rome, Italy, May 23-29, 2009, pages 1–8. 2009.

[40] Carole Delporte-Gallet, Hugues Fauconnier, and Sam Toueg. Brief announcement: The minimum failure detector for non-local tasks in message-passing systems. In Idit Keidar, editor, Distributed Computing, 23rd International Symposium, DISC 2009, Elche, Spain, September 23-25, 2009. Proceedings, volume 5805 of Lecture Notes in Computer Science, pages 358–359. Springer, 2009.

[41] Carole Delporte-Gallet, Hugues Fauconnier, and Sam Toueg. The minimum information about failures for solving non-local tasks in message-passing systems. In Principles of Distributed Systems, 13th International Conference, OPODIS 2009, Nîmes, France, December 15-18, 2009. Proceedings, volume 5923 of Lecture Notes in Computer Science, pages 115–128. Springer, 2009.

[42] Carole Delporte-Gallet, Stéphane Devismes, Hugues Fauconnier, Franck Petit, and Sam Toueg. With finite memory consensus is easier than reliable broadcast. In Principles of Distributed Systems, 12th International Conference, OPODIS 2008, Luxor, Egypt, December 15-18, 2008. Proceedings, volume 5401 of Lecture Notes in Computer Science, pages 41–57. 2008.

[43] Carole Delporte-Gallet, Hugues Fauconnier, and Rachid Guerraoui. Sharing is harder than agreeing. In Rida A. Bazzi and Boaz Patt-Shamir, editors, Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing, PODC 2008, Toronto, Canada, August 18-21, 2008, pages 85–94. 2008.

[44] Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, and Andreas Tielmann. The weakest failure detector for message passing set-agreement. In Distributed Computing, 22nd International Symposium, DISC 2008, Arcachon, France, September 22-24, 2008. Proceedings, volume 5218 of Lecture Notes in Computer Science, pages 109–120. Springer, 2008.

[45] Emmanuelle Anceaume, Carole Delporte-Gallet, Hugues Fauconnier, Michel Hurfin, and Josef Widder. Clock synchronisation in the byzantine -recovery failure model. In Principles of Distributed System, 11th International Conference, OPODIS 2007, Guadeloupe, French West Indies, December 2007, Proceedings, volume 4878 of Lecture Notes in Computer Science, pages 89–104. Springer, 2007. ISBN 0302-9743.

[46] Carole Delporte-Gallet, Stéphane Devismes, and Hugues Fauconnier. Robust stabilizing leader election. In Stabilization, Safety, and Security of Distributed Systems, 9th International Symposium, SSS 2007, Paris, France, November 14-16, 2007, Proceedings, volume 4838 of Lecture Notes in Computer Science, pages 219–233. Springer, 2007. ISBN 978-3-540-76626-1.

[47] Carole Delporte-Gallet, Hugues Fauconnier, Felix C. Freiling, Lucia Draque Penso, and Andreas Tielmann. From crash-stop to permanent omission: Automatic transformation and weakest failure detectors. In DISC, pages 165–178. 2007.

[48] Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, and Eric Ruppert. Secretive birds: Privacy in populatin protocols. In Principles of Distributed System, 11th International Conference, OPODIS 2007, Guadeloupe, French West Indies, December 2007, Proceedings, volume 4878 of Lecture Notes in Computer Science, pages 329–342. Springer, 2007. ISBN 0302-9743.

[49] Marcos Kawazoe Aguilera, Carole Delporte-Gallet, Hugues Fauconnier, and Sam Toueg. Consensus with byzantine failures and little system synchrony. In 2006 International Conference on Dependable Systems and Networks (DSN 2006), 25-28 June 2006, Philadelphia, Pennsylvania, USA, Proceedings, pages 147–155. IEEE Computer Society, 2006. ISBN 0-7695-2607-1.

[50] Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, and Eric Ruppert. When birds die: Making population protocols fault-tolerant. In Distributed Computing in Sensor Systems, Second IEEE International Conference, DCOSS 2006, San Francisco, CA, USA, June 18-20, 2006, Proceedings, volume 4026 of Lecture Notes in Computer Science, pages 51–66. Springer, 2006.

[51] Carole Delporte-Gallet, Hugues Fauconnier, and Felix C. Freiling. Revisiting failure detection and consensus in omission failure environments. In Dang Van Hung and Martin Wirsing, editors, Theoretical Aspects of Computing - ICTAC 2005, Second International Colloquium, Hanoi, Vietnam, October 17-21, 2005, Proceedings, volume 3722 of Lecture Notes in Computer Science, pages 394–408. Springer, 2005.

[52] Carole Delporte-Gallet, Hugues Fauconnier, and Rachid Guerraou. What dependability for networks of mobile sensors ? In First Workshop on Hot Topics in System Dependability, DSN 05, Yokohama, Japan. 2005.

[53] Carole Delporte-Gallet, Hugues Fauconnier, and Rachid Guerraoui. (almost) all objects are universal in message passing systems. In Pierre Fraigniaud, editor, Distributed Computing, 19th International Conference, DISC 2005, Cracow, Poland, September 26-29, 2005, Proceedings, volume 3724 of Lecture Notes in Computer Science, pages 184–198. Springer, 2005.

[54] Carole Delporte-Gallet, Hugues Fauconnier, Stephanie Lorraine Horn, and Sam Toueg. Fast fault-tolerant agreement algorithms. In Marcos Kawazoe Aguilera and James Aspnes, editors, Proceedings of the Twenty-Fourth Annual ACM Symposium on Principles of Distributed Computing, PODC 2005, Las Vegas, NV, USA, July 17-20, 2005, pages 169–178. ACM, 2005.

[55] Marcos Kawazoe Aguilera, Carole Delporte-Gallet, Hugues Fauconnier, and Sam Toueg. Communication-efficient leader election and consensus with limited link synchrony. In Soma Chaudhuri and Shay Kutten, editors, Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, PODC 2004, St. John’s, Newfoundland, Canada, July 25-28, 200, pages 328–337. ACM, 2004.

[56] Emmanuelle Anceaume, Carole Delporte-Gallet, Hugues Fauconnier, Michel Hurfin, and Gérard Le Lann. Designing modular services in the scattered byzantine failure model. In 3rd International Symposium on Parallel and Distributed Computing (ISPDC 2004), 3rd International Workshop on Algorithms, Models and Tools for Parallel Computing on Heterogenous Networks (HeteroPar 2004), 5-7 July 2004, Cork, Ireland, pages 262–269. IEEE Computer Society, 2004.

[57] Emmanuelle Anceaume, Carole Delporte-Gallet, Hugues Fauconnier, Michel Hurfin, and Gérard Le Lann. Modular services with byzantine recovery. In IEEE Proc. of the International Conference on Dependable Systems and Networks (DSN), Florence, Italy (fast abstract), pages 46–47. 2004.

[58] Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, Vassos Hadzilacos, Petr Kouznetsov, and Sam Toueg. The weakest failure detectors to solve certain fundamental problems in distributed computing. In Soma Chaudhuri and Shay Kutten, editors, Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, PODC 2004, St. John’s, Newfoundland, Canada, July 25-28, 2004, pages 338–346. ACM, 2004.

[59] Marcos Kawazoe Aguilera, Carole Delporte-Gallet, Hugues Fauconnier, and Sam Toueg. On implementing omega with weak reliability and synchrony assumptions. In Proceedings of the Twenty-Two Annual ACM Symposium on Principles of Distributed Computing, PODC 2003, pages 306–314. 2003.

[60] Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, and Bastian Pochon. Distributed programming for dummies: A shifting transformation technique. In 22nd Symposium on Reliable Distributed Systems (SRDS 2003), 6-8 October 2003, Florence, Italy, pages 349–. IEEE Computer Society, 2003.

[61] Carole Delporte-Gallet and Hugues Fauconnier. Latency measures and lower bounds for consensus with failure detectors. In Christos Kaklamanis and Lefteris M. Kirousis, editors, SIROCCO 9, Proceedings of the 9th International Colloquium on Structural Information and Communication Complexity, Andros, Greece, June 10-12, 200, volume 13 of Proceedings in Informatics, pages 87–100. Carleton Scientific, 2002.

[62] Carole Delporte-Gallet, Hugues Fauconnier, and Rachid Guerraoui. Failure detection lower bounds on registers and consensus. In Dahlia Malkhi, editor, Distributed Computing, 16th International Conference, DISC 2002, Toulouse, France, October 28-30, 2002 Proceedings, volume 2508 of Lecture Notes in Computer Science, pages 237–251. Springer, 2002.

[63] Carole Delporte-Gallet, Hugues Fauconnier, and Rachid Guerraoui. A realistic look at failure detectors. In 2002 International Conference on Dependable Systems and Networks (DSN 2002), 23-26 June 2002, Bethesda, MD, USA, Proceedings, pages 345–353. IEEE Computer Society, 2002.

[64] Carole Delporte-Gallet, Hugues Fauconnier, Jean-Michel Hélary, and Michel Raynal. Early stopping in aglobal data computation. In PODC, page 258. 2002.

[65] Marcos Kawazoe Aguilera, Carole Delporte-Gallet, Hugues Fauconnier, and Sam Toueg. Stable leader election. In Distributed Computing, 15th International Conference, DISC 2001, Lisbon, Portugal, October 3-5, Proceedings, volume 2180 of Lecture Notes in Computer Science, pages 108–122. 2001.

[66] Carole Delporte-Gallet and Hugues Fauconnier. An example of real-time group communication system. In Proceedings of the 21th IEEE International Conference on Distributed Computing Systems Workshops, pages 5–10. 2001.

[67] Marcos Kawazoe Aguilera, Carole Delporte-Gallet, Hugues Fauconnier, and Sam Toueg. Thrifty generic broadcast. In Maurice Herlihy, editor, Distributed Computing, 14th International Conference, DISC 2000, Toledo, Spain, October 4-6, Proceedings, volume 1914 of Lecture Notes in Computer Science, pages 268–282. Springer, 2000.

[68] Carole Delporte-Gallet and Hugues Fauconnier. Fault-tolerant genuine atomic multicast to multiple groups. In Franck Butelle, editor, Procedings of the 4th International Conference on Principles of Distributed Systems, OPODIS 2000, Paris, France, December 20-22, Studia Informatica Universalis, pages 107–122. Suger, Saint-Denis, rue Catulienne, France, 2000.

[69] Carole Delporte-Gallet and Hugues Fauconnier. Lower bounds with unreliable failure detector. In 13th International Symposium on Distributed Computing(DISC’99), brief announcements. 1999.

[70] Carole Delporte-Gallet and Hugues Fauconnier. Real-time fault-tolerant atomic broadcast. In Symposium on Reliable Distributed Systems, pages 48–55. 1999.

[71] Hugues Fauconnier and Carole Delporte-Gallet. Synchronized phased systems. In Franck Petit and R. Gomez Cardenas, editors, Procedings of the 3rd International Conference on Principles of Distributed Systems. OPODIS 99, Hanoi, Vietnam, October 20-22,, Studia Informatica Universalis, pages 179–194. Suger, Saint-Denis, rue Catulienne, France, 1999.

Sommaire

Résumé du Curriculum Vitæ

Formation

Activités professionnelles

Parcours professionnel :

Enseignement :

Responsabilités administratives à l’Université Paris-Diderot:

Recherche :