Curriculum Vitæ : Gabriel Le Bouder


Adresse professionnelle :
Sorbonne Université - LIP6
Boîte courrier 169
4 place Jussieu, 75252 Paris CEDEX 05
e-mail : Gabriel.Le-Bouder@lip6.fr
site web: https://lip6.fr/Gabriel.Le-Bouder

Date de naissance: 22/04/1994
Nationalité: Française

Situation Actuelle

Doctorat

Thèse:“Optimisation de la Mémoire pour Algorithmes Distribués Auto-Stabilisants" soutenue le 6 Janvier 2023 à Sorbonne Université.
Jury:

Autres diplômes

2019
MPRI, Master Parisien de Recherche en Informatique Université Paris Diderot, Paris, France.
2018
Agrégation de Mathématiques option informatique.
2016
Licence Informatique, Université Paris Diderot, Paris, France.

Formation

2015 - 2019
ENS Cachan (ENS Paris-Saclay), Département Informatique, Cachan, France.

Activités professionnelles

01-09-2022 - 31-08-2023:
ATER UFR d'Ingénierie Sorbonne Université.
01-10-2019 - 06-01-2023:
Doctorant, LIP6 équipe DELYS, Sorbonne Université.
01-03-2019 - 31-08-2019:
Stage de Mater 2, Encadrement: Lélia Blin, Sujet: Minimisation de la mémoire dans les algorithmes auto-stabilisants bavards, LIP6 équipe NPA (Network Performances Analysis).
01-06-2017 - 15-08-2017
Stage de Master 1, Encadrement: Olivier Bonaventure, Sujet: A deeper understanding of BBR, UC Louvain.
01-07-2016 - 15-08-2016
Stage de Licence 3, Encadrement: Pierre-Alain Fouque, Sujet: A study over Goldreich's hash function for SPHINCS, Université Rennes 1 - IRISA.

Enseignements: Total 411,25h eq-TD.

L'intégralité de mon service a été effectué à Sorbonne Université dans l'UFR d'Ingénierie (UFR 919) en filière Informatique.

Statut Année Ex. Niveaux #étudiants Volume Type Intitulés des cours
ATER 22-23 M1 30 21 CM/TD/TP Algorithmique Répartie
ATER 22-23 M1 4 8 Projet Systèmes et Applications Réparties
ATER 22-23 L3 34 38,5 TD/TP Fondements des systèmes d'exploitation
ATER 22-23 L2 25 77 TD/TP Structures de données
ATER 22-23 L2 34 38,5 TD/TP Programmation Shell et initiation au système
ATER 22-23 L2 25 21 TD/TP C avancé
Moniteur 21-22 L2 25 38,5 TD/TP Structures de données
Moniteur 21-22 L2 25 22,75 TD/TP Programmation fonctionnelle
Moniteur 20-21 L2 25 31,5 TD/TP C avancé
Moniteur 20-21 L1 25 40 TP Éléments de programmation 2
Moniteur 19-20 L1 25 60 TP Éléments de programmation 2
Moniteur 19-20 L2/L3 25 14,5 TP Initiation aux systèmes d'exploitation

Publications

Conférences Internationales avec Comité de Sélection

Articles

1
Lélia Blin, Colette Johnen, Gabriel Le Bouder, and Franck Petit.
Silent anonymous snap-stabilizing termination detection.
In 41th IEEE Symposium on Reliable Distributed Systems (SRDS 2022), Vienna, Austria, October 19-22, 2022. IEEE Computer Society, 2022.
Rang: B.
2
Lélia Blin, Laurent Feuilloley, and Gabriel Le Bouder.
Optimal space lower bound for deterministic self-stabilizing leader election algorithms.
In Quentin Bramas, Vincent Gramoli, and Alessia Milani, editors, 25th International Conference on Principles of Distributed Systems, OPODIS 2021, December 13-15, 2021, Strasbourg, France, volume 217 of LIPIcs, pages 24:1–24:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
Rang: B, Taux de sélection: 40%.

Brief Announcement

3
Lélia Blin, Laurent Feuilloley, and Gabriel Le Bouder.
Brief announcement: Memory lower bounds for self-stabilization.
In Jukka Suomela, editor, 33rd International Symposium on Distributed Computing, DISC 2019, October 14-18, 2019, Budapest, Hungary, volume 146 of LIPIcs, pages 37:1–37:3. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
Rang: A.

Conférences Nationales avec Comité de Sélection

4
Lélia Blin, Laurent Feuilloley, and Gabriel Le Bouder.
Borne inférieure optimale pour la complexité spatiale des algorithmes déterministes auto-stabilisants d'élection.
In 13e rencontres francophones sur les aspects algorithmiques des télécommunications, Algotel 2022, May 30 - June 3, Université Paris-Saclay, France, 2022.
5
Lélia Blin, Colette Johnen, Gabriel Le Bouder, and Franck Petit.
Détection de terminaison auto-stabilisante silencieuse, anonyme et instantanée.
In 13e rencontres francophones sur les aspects algorithmiques des télécommunications, Algotel 2022, May 30 - June 3, Université Paris-Saclay, France, 2022.

Récompenses

[2] a été nommé Best Student Paper en 2021 à OPODIS, 25th International Conference on Principles of Distributed Systems (référence en page 10).

Travaux acceptés non encore publiés

Soumissions en Cours

Séminaires et séjours de recherche

Enseignement

Mon service d'enseignement a été effectué trois années en tant que moniteur, et une année en tant qu'ATER. J'ai enseigné les bases de la programmation en C en Licence 1 et en Licence 2. En Licence 1 au second semestre, les étudiants ont une connaissance basique de la programmation apprise à travers le langage de script Python, mais de nombreuses compétences de base sont encore à acquérir ou à approfondir, la notion de boucle, les sauts conditionnels, les pointeurs et plus généralement la gestion de la mémoire, mais également la compilation et l'exécution de code.

 

En Licence 2 au premier semestre, nous reprenons et approfondissons ces notions, et en abordons de nouvelles plus complexes, la compilation séparée, la lecture et écriture dans des fichiers, les problèmes liés à l'utilisation de la mémoire dans le tas, l'analyse des erreurs du compilateur, et l'utilisation d'outils comme ddd ou valgrind pour les réparer, la notions de structure, de liste chaînées, d'arbres binaire. Nous introduisons également des notions particulièrement avancées, comme les pointeurs de fonctions et les pointeurs vides, en faisant réaliser aux étudiants une bibliothèque générique de gestion de listes. Ã mi-semestre, un projet simulant l'évolution d'un écosystème proie-prédateur est également demandé aux étudiants, sur une durée de 5 semaines.

 

Au second semestre de la Licence 2, l'UE de structure de données permet de mettre en application les compétences en langage C acquises précedemment, à l'occasion de la découverte de structures de données plus complexes que les tableaux ou les listes, et les problèmes algorithmiques qui y sont liés. Nous étudions notamment les tables de hachage, les tas, les graphes, certains arbres binaires particuliers (ABR, arbres rouge-noir), introduisons différents algorithmes de tris de liste (tri rapide, tri fusion, tri par tas notamment).

 

D'autre part, j'ai également enseigné la programmation fonctionnelle au premier semestre de Licence 2, à travers le langage de programmation Ocaml. Nous y approfondissons la programmation récursive, et introduisons la notion de récursion terminale. Les étudiants codent des fonctions prenant comme paramètre des fonctions, typiquement des itérateurs, et progressivement les itérateurs classiques d'Ocaml sur les listes (fold_left, map, iter) sont découverts, utilisés, et également combinés entre eux. Les étudiants apprennent également à définir des types propres, utilisés pour définir différents types d'arbres sur lesquels ils sont amenés à travailler, à définir des fonctions de recherche, de calcul de chemin.

 

Sur un tout autre aspect, j'ai également enseigné des élements plus accès système. En Licence 2, au premier semestre, j'ai enseigné la Programmation Shell et Initiation au Système. Le langage utilisé est le bash, qui permet relativement simplement de mettre en applications les notions introduites durant cette UE. Après quelques semaines dédiées essentiellement à maîtriser le langage bash, les redirections de flux, et les différents utilitaires classiques fournis par la distribution Linux ou par le noyau, tels que wc, grep, sed, kill, nous abordons en profondeurs des notions plus fondamentales du système. En particulier, nous inrtoduions les notions de cycle de vie d'un processus, d'execution concurrente et d'ordonnanceur, de synchronisation entre processus (à l'aide de wait, de signaux, et de verrous Linux).

 

Au second semestre de Licence 2, nous approfondissons ces notions systèmes dans l'UE d'Initiation aux Systemes d'exploitation, en utilisant cette fois-ci le langage C. Une nouveauté importante de cette UE est la découverte des tubes permettant la communications entre processus, tubes anonymes et tubes nommés.

 

Les UE d'Algorithmique Répartie, de Fondement des Systèmes d'Exploitation, et le Projet Systèmes et Applications Réparties auront lieu au second semestre de l'année en cours, et je ne peux donc m'attarder sur leur contenu.

 

Ces quatre années d'enseignement m'ont permis de pratiquer l'enseignement de l'informatique sur différentes thématiques, et à différents niveaux. Ces années m'ont permis de m'assurer que le métier d'enseignant me convient, et que je peux envisager de travailler auprès d'étudiants sur le long terme. J'ai également découvert d'autres facettes du métier d'enseignant, la préparation de sujets (en tant que relecteur), la réalisation de barèmes, et bien entendu la correction de copies.

Ces expériences ont confirmé mon intérêt et ma motivation pour l'enseignement dans le supérieur.

Recherche

Mots-Clefs

Algorithmes Distribués, Tolérance aux Pannes, Auto-Stabilisation, Minimisation de la Mémoire, Anonymat

Domaine

L'auto-stabilisation est un paradigme adapté aux systèmes distribués, particulièrement susceptibles de subir des fautes transitoires. Des erreurs de corruption de mémoire, de messages, la rupture d'un lien de communication peuvent plonger le système dans un état incohérent. Un protocole est auto-stabilisant si, quel que soit l'état initial du système, il garantit un retour à un fonctionnement normal en temps fini.

Plusieurs contraintes s'appliquent aux algorithmes conçus pour les systèmes distribués. L'asynchronie en est un exemple emblématique. Avec le développement de réseaux d'objets connectés, censés être autonomes, il devient également central de concevoir des algorithmes ayant un faible coût en termes de consommation énergétique et peu exigeants en termes de ressources.

Une des manières d'appréhender ces problèmes est de chercher à réduire la taille des messages échangés entre les différents nœuds du réseau. Mon travail se concentre sur l'optimisation de la mémoire nécessaire à la communication pour les algorithmes distribués auto-stabilisants. Nous nous intéressons à l'étude de borne inférieure pour la complexité spatiale de certains problèmes, tout comme à la conception d'algorithmes efficaces en mémoire pour la résolution de certains problèmes.


Résultats

Nous avons obtenus des résultats des deux types.

Notre première contribution [2] est un résultat d'impossibilité, qui se traduit également comme une borne inférieure pour la mémoire nécessaire à la résolution de certains problèmes. Nous montrons que, quel que soit le paramétrage du réseau considéré, il n'était pas possible d'utiliser la puissance algorithmique fournie par l'existence d'identifiants uniques sur le réseau en utilisant une mémoire inférieure à $O(\log \log n)$ bits par nœud où $n$ est le nombre de nœuds du réseau. Nous montrons qu'avec une mémoire inférieure à cette borne, un algorithme se comporte de la même manière sur un réseau avec identifiants, et sur un réseau sans identifiants. Nous obtenons notre résultat par un argument de dénombrement de fonctions, en montrant qu'une mémoire trop petite ne laisse pas assez de possibilté pour un algorithme de se comporter différemment en fonction de l'identifiant fourni. Ãtant donné que certains problèmes sont connus comme impossibles à résoudre en l'absence d'identifiant, ce résultat d'équivalence constitue bien une borne inférieure pour la complexité de ces problèmes. En particulier, des problèmes fondamentaux comme l'élection ou la construction d'arbre ne sont pas résolubles dans les réseauc anonymes, et ont donc tous deux une complexité en $\Omega(\log\log n)$ bits par nœud. La seule borne connue précedemment pour ces problèmes dans le cas général était en $\omega(1)$, c'est-à-dire qu'il avait été démontré impossible de les résoudre avec une mémoire constante en la taille du réseau. Notre borne améliore significativement l'état de l'art.

Nous proposons également deux algorithmes pour deux problèmes différents, tous deux peu exigeant en mémoire et l'un étant en réalité optimal. Ce dernier (Chapitre 5 de ma thèse) est un algorithme auto-stabilisant de circulation de jeton dans un type particulier de réseaux, que sont les DODAGs. La circulation de jeton consiste en la circulation perpétuelle d'un unique jeton, qui doit visiter de façon équitable tous les nœuds du réseau. Notre algorithme fonctionne sous un ordonnanceur non-équitable, et avec une mémoire en $O(\log \log n)$ bits par nœud. Notre précédente borne s'applique au problème et aux hypothèses qui sont les notres, ce qui nous permet d'affirmer l'optimalité de notre algorithme. La principale difficulté dans la conception d'un tel algorithme avec une mémoire en $O(\log \log n)$ bits par nœud est que les différents nœuds du réseau ne peuvent pas simplement communiquer un message, et donc faire passer un jeton à l'un seul de leurs voisins. En effet, les nœuds communiquand de façon indentique à tous leurs voisins, la distinction d'un unique destinataire d'un message est généralement réalisée en indiquant dans le message l'identifiant de son destinataire, ce qui a un coût en mémoire de $O(\log n)$. De la même manière, il est impossible pour un nœud de stocker un pointeur vers l'un de ses voisins, ceci ayant un coût en $O(\log \Delta)$, $\Delta$ étant le degré du réseau, pouvant être de l'ordre de grandeur de $n$ dans certains réseaux. Notre algorithme est, à notre connaissance, le premier algorithmes utilisant $O(\log \log n)$ bits par nœud sur des réseaux de degré non-borné.

Enfin, notre dernier résultat [1] est double. Le résultat principal est un algorithme de détection de terminaison, instantanément stabilisant, pour les réseaux anonymes. La détection consiste en l'observation continue d'un algorithme fonctionnant indépendemment sur le même réseau, de façon à ce que chaque nœud puisse recevoir une requête locale de détection de terminaison, après quoi le nœud doit fournir une réponse en temps fini à la question de savoir si l'algorithme observé a globalement stabilisé ou non. Notre algorithme utilise $O(\log D)$ bits par nœud, et fournit une réponse en $O(D)$ pas de calcul, $D$ étant le diamètre du réseau. Cet algorithme est le premier algorithme de détection de terminaison qui soit instantanément stabilisant et utilisable dans les réseaux anonymes. Il a de plus une faible complexité spatiale. Notre algorithme se base sur l'utilisation de deux compteurs, synchronisés l'un avec l'autre de différentes manières. Le premier mode de synchronisation est que l'un des compteurs n'est activé que sous la condition que l'autre compteur est tombé à 0. Le second mode de synchronisation est que ces deux compteurs ne sont décrémentés qu'au moment où un troisième compteur, compteur l'unison, est incrémenté. L'unison est un problème classique des systèmes distribués, et de nombreux algorithmes d'unison auto-stabilisants pour les réseaux anonymes existent dans la littérature. Notre algorithme de détection de terminaison peut s'appuyer sur n'importe lequel de ces algorithmes, vu comme une boîte noire. Ceci n'est possible que parce que nous avons démontré certaines propriétés globales que repectent nécessairement tous les algorithmes auto-stabilisants, ce qui constitue la seconde partie de notre contribution. Il s'agit d'un travail théorique d'analyse des propriétés globales qui sont nécessairement vérifiées par tout algorithmes qui respecte la spécification du problème de l'unison.

Projet de recherche

Notre algorithme de détection de terminaison ne retourne que des réponses positives: aucune réponse n'est fournie tant que le l'algorithme observé n'a pas réellement stabilisé. Adapter notre solution pour pouvoir retourner des réponses négatives, tout en maintenant la propriété de stabilisation instantanée, sans faux négatif, n'est pas simple à réaliser. Deux autres questions restent en suspens : la première concerne la nécessité pour les nœuds de connaitre une borne sur le diamètre du réseau pour résoudre ce problème, dans le cas des réseaux anonymes, et la seconde, liée à la première, concerne l'optimalité en mémoire de notre algorithme instantanément stabilisant our les réseaux anonymes. Plus généralement se pose la question de la nécessité d'utiliser $\Omega(\log D)$ bits par nœud pour résoudre des problèmes d'observation globale dans les réseaux anonymes.

D'autre part, notre borne inférieure en $\Omega(\log\log n)$ bits par nœud s'applique à de nombreux problèmes pour lesquels des algorithmes plus ou moins efficaces existent. La question qui subsiste concerne l'optimalité de cette borne. En ce qui concerne les problèmes de l'élection et de la construction d'arbre, les algorithmes les plus efficaces nécessitent $O(\log \log n + \log \Delta)$ bits par nœud. La question de savoir s'il est possible de résoudre ces deux problèmes en utilisant exactement $\Theta(\log\log n)$ bits par nœud reste ouverte.

D'autre part, notre algorithme de circulation de jeton nous permet d'être optimistes quant à la possibilité de concevoir un algorithme auto-stabilisant de circulation de jeton pour les réseaux quanconques, et non plus seulement les DODAGs, avec une complexité spatiale de $\Theta(\log\log n)$ bits par nœud. Trois problèmes fondamentaux doivent être résolus pour obtenir un tel résultat dans le cadre de l'auto-stabilisation. Le premier est l'existence de plusieurs racines. La présence de multiples racines n'est pas la situation la plus compliquée, puisqu'il nous semble possible d'implémenter une négociation à distance, sur la base des identifiants, entre les différentes racines. Le deuxième problème est l'absence de racine. L'absence de racine est elle un peu plus compliquée à gérer, et notamment à détecter. En effet en l'absence de racine, on peut tout à fait envisager un réseau dans lequel aucun token ne circule, et aucun nœud pour détecter l'anomalie. Le troisième problème fondamental, qui n'est pas sans lien avec l'absence de racine, est la présence de cycles dans le graphe ces cycles étant par définition proscrits dans les DODAGs. La difficulté majeure consiste en la détection de ces cycles, avec une mémoire en $O(\log \log n)$. Les symmétries causées par la présence de cycles rendent égalament très compliquée l'adaptation de notre algorithme aux graphes généraux.

L'existence d'un tel algorihme, résolvant la circulation de jeton dans les graphes généraux en $\Theta(\log\log n)$ bits par nœuds, constituerait un outil particulièrement intéressant pour la conception d'algorithmes efficaces en mémoire pour d'autres problèmes, et notamment pour l'élection et la construction d'arbre.