Supervision : Sébastien TIXEUIL

Co-supervision : POTOP-BUTUCARU Maria

Tolérer les fautes transitoires, permanentes et intermittentes

Un système réparti est un système constitué d'un ensemble d'unités de calcul autonomes dotées de capacités de communication afin de résoudre une tâche globale. Ce modèle est suffisament général pour décrire tout type de réseau physique (réseau local, réseau de capteurs, ...). Lorsque la taille d'un système réparti devient importante ou lorsque ce système est déployé dans un environnement non contrôlé, la probabilité que certains éléments du système subissent des fautes (panne, corruption de mémoire, piratage, ...) devient non négligeable. Ces fautes peuvent être classifiées en fonction de leur durée, de leur étendue et de leur nature. Dans cette thèse, nous nous intéressons aux systèmes répartis capables de tolérer simultanément plusieurs types de fautes à travers l'étude de trois problèmes fondamentaux. Nous présentons ainsi un protocole réparti simulant un registre atomique mono-écrivan multi-lecteurs en présence de fautes transitoires et de fautes permanentes de type crash. Ce protocole repose sur deux outils ré-utilisables : un protocole de communication et un système d'estampillage borné. Ensuite, nous proposons une étude de la synchronisation faible d'horloges logiques en présence de fautes transitoires et de fautes intermittentes Byzantines. Nous prouvons de nombreux résultats d'impossibilité et nous fournissons un protocole optimal dans les cas non couverts par ces résultats. Finalement, nous définissons trois nouveaux concepts de tolérance pour les systèmes répartis sujets à des fautes transitoires et des fautes intermittentes Byzantines. Nous donnons un protocole de construction d'une vaste classe d'arbres couvrants optimal selon ces trois concepts.

One PhD student (Supervision / Co-supervision)

Three past PhD students (2016 - 2019) at Sorbonne University

2009-2023 Publications

• 2023
  • S. Dubois, L. Feuilloley, F. Petit, M. Rabie : “When Should You Wait Before Updating? Toward a Robustness Refinement”, 2^nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023), vol. 257, Leibniz International Proceedings in Informatics (LIPIcs), Pisa, Italy, pp. 7:1-7:15, (Schloss Dagstuhl – Leibniz-Zentrum für Informatik), (ISBN: 978-3-95977-275-4) (2023)
• 2020
  • L. Blin, S. Dubois, L. Feuilloley : “Silent MST Approximation for Tiny Memory”, SSS 2020 : The 22^th International Symposium on Stabilization, Safety, and Security of Distributed Systems, vol. 12514, Lecture Notes in Computer Science, Austin, TX / Virtual, United States, pp. 118-132, (Springer, Cham.) (2020)
  • A. Casteigts, S. Dubois, F. Petit, J. Robson : “Robustness: A new form of heredity motivated by dynamic networks”, Theoretical Computer Science, vol. 806, pp. 429-445, (Elsevier) (2020)
• 2019
  • S. Dubois, R. Guerraoui, P. Kuznetsov, F. Petit, P. Sens : “The weakest failure detector for eventual consistency”, Distributed Computing, vol. 32 (6), pp. 479-492, (Springer Verlag) (2019)
  • S. Bouchard, M. Bournat, Y. Dieudonné, S. Dubois, F. Petit : “Asynchronous approach in the plane: a deterministic polynomial algorithm”, Distributed Computing, vol. 32 (4), pp. 317-337, (Springer Verlag) (2019)
  • M. Bournat, A. Datta, S. Dubois : “Self-stabilizing robots in highly dynamic environments”, Theoretical Computer Science, vol. 772, pp. 88-110, (Elsevier) (2019)
  • K. Altisen, S. Devismes, S. Dubois, F. Petit : “Introduction to Distributed Self-Stabilizing Algorithms”, vol. 8 (1), Synthesis Lectures on Distributed Computing Theory, 1-165 pages, (Morgan & Claypool) (2019)
• 2018
  • M. Bournat, S. Dubois, F. Petit : “Gracefully Degrading Gathering in Dynamic Rings”, Stabilization, Safety, and Security of Distributed Systems - 20^th International Symposium, SSS 2018, vol. 11201, Lecture Notes in Computer Science, Tokyo, Japan, pp. 349-364, (Springer) (2018)
  • L. Blin, F. Boubekeur, S. Dubois : “A Self-Stabilizing Memory Efficient Algorithm for the Minimum Diameter Spanning Tree under an Omnipotent Daemon”, Journal of Parallel and Distributed Computing, vol. 117, pp. 50-62, (Elsevier) (2018)
  • S. Bouchard, M. Bournat, Y. Dieudonné, S. Dubois, F. Petit : “Approche asynchrone dans le plan : un algorithme déterministe polynomial”, ALGOTEL 2018 - 20^es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Roscoff, France (2018)
  • M. Bournat, S. Dubois, F. Petit : “Gracefully Degrading Gathering in Dynamic Rings”, (2018)
• 2017
  • S. Bouchard, M. Bournat, Y. Dieudonné, S. Dubois, F. Petit : “Asynchronous Approach in the Plane: A Deterministic Polynomial Algorithm”, 31^st International Symposium on Distributed Computing, DISC 2017, Vienna, Austria (2017)
  • M. Bournat, S. Dubois, F. Petit : “Computability of Perpetual Exploration in Highly Dynamic Rings”, The 37^th IEEE International Conference on Distributed Computing Systems (ICDCS 2017), Atlanta, United States (2017)
  • M. Bournat, S. Dubois, F. Petit : “Quel est le nombre optimal de robots pour explorer un anneau hautement dynamique ?”, ALGOTEL 2017 - 19^es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Quiberon, France (2017)
• 2016
  • M. Bournat, S. Dubois, F. Petit : “Computability of Perpetual Exploration in Highly Dynamic Rings”, (2016)
  • M. Bournat, A. Datta, S. Dubois : “Self-Stabilizing Robots in Highly Dynamic Environments”, SSS 2016 - 18^th International Symposium Stabilization, Safety, and Security of Distributed Systems, vol. 10083, Lecture Notes in Computer Science, Lyon, France, pp. 54-69, (Springer) (2016)
  • M. Bournat, Ajoy K. Datta, S. Dubois : “Self-Stabilizing Robots in Highly Dynamic Environments”, (2016)
  • L. Blin, F. Boubekeur, S. Dubois : “Algorithme auto-stabilisant efficace en mémoire pour la construction d’un arbre couvrant de diamètre minimum”, ALGOTEL 2016 - 18^es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Bayonne, France (2016)
  • N. Braud‑Santoni, S. Dubois, M. Kaaouachi, F. Petit : “The Next 700 Impossibility Results in Time-Varying Graphs”, International Journal of Networking and Computing, vol. 6 (1), pp. 27-41, (Higashi Hiroshima : Dept. of Computer Engineering, Hiroshima University) (2016)
• 2015
  • S. Dubois, T. Masuzawa, S. Tixeuil : “Maximum Metric Spanning Tree Made Byzantine Tolerant”, Algorithmica, vol. 73 (1), pp. 166-201, (Springer Verlag) (2015)
  • S. Dubois, R. Guerraoui, P. Kuznetsov, F. Petit, P. Sens : “The Weakest Failure Detector for Eventual Consistency”, 34^th Annual ACM Symposium on Principles of Distributed Computing (PODC-2015), Donostia-San Sebastián, Spain, Donostia-San Sebastián, Spain, pp. 375-384 (2015)
  • S. Dubois, M. Kaaouachi, F. Petit : “Dynamisme et Domination”, ALGOTEL 2015 — 17^es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Beaune, France (2015)
  • N. Alon, H. Attiya, Sh. Dolev, S. Dubois, M. Potop‑Butucaru, S. Tixeuil : “Practically stabilizing SWMR atomic memory in message passing systems”, Journal of Computer and System Sciences, vol. 81 (4), pp. 692-701, (Elsevier) (2015)
  • N. Braud‑Santoni, S. Dubois, M. Kaaouachi, F. Petit : “A Generic Framework for Impossibility Results in Time-Varying Graphs”, Parallel and Distributed Processing Symposium Workshop (IPDPSW), 2015 IEEE International, Hyderabad, India, pp. 483-489, (IEEE) (2015)
  • S. Dubois, M. Kaaouachi, F. Petit : “Enabling Minimal Dominating Set in Highly Dynamic Distributed Systems”, 17^th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS'15), vol. 9212, Lecture Notes in Computer Science, Edmonton, AB, Canada, pp. 51-66, (Springer) (2015)
  • L. Blin, F. Boubekeur, S. Dubois : “A Self-Stabilizing Memory Efficient Algorithm for the Minimum Diameter Spanning Tree under an Omnipotent Daemon”, Parallel and Distributed Processing Symposium (IPDPS), 2015 IEEE International, Hyberabad, India, pp. 1065-1074, (IEEE) (2015)
• 2014
  • N. Braud‑Santoni, S. Dubois, M. Kaaouachi, F. Petit : “The Next 700 Impossibility Results in Time-Varying Graphs”, (2014)
• 2013
  • A. Cournier, S. Dubois, A. Lamani, F. Petit, V. Villain : “Acheminement de messages instantanément stabilisant pour arbres couvrants”, 15^es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), Pornic, France, pp. 1-4 (2013)
  • A. Cournier, S. Dubois, A. Lamani, F. Petit, V. Villain : “The Snap-stabilizing message forwarding algorithm on tree topologies”, Theoretical Computer Science, vol. 496, pp. 89-112, (Elsevier) (2013)
• 2012
  • S. Dubois, S. Tixeuil, N. Zhu : “Mariages et Trahisons”, 14^es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), La Grande Motte, France, pp. 1-4 (2012)
  • S. Dubois, S. Tixeuil, N. Zhu : “The Byzantine Brides Problem”, (2012)
  • S. Dubois, T. Masuzawa, S. Tixeuil : “Bounding the Impact of Unbounded Attacks in Stabilization”, IEEE Transactions on Parallel and Distributed Systems, vol. 23 (3), pp. 460-466, (Institute of Electrical and Electronics Engineers) (2012)
  • Sh. Dolev, S. Dubois, M. Potop‑Butucaru, S. Tixeuil : “Crash Resilient and Pseudo-Stabilizing Atomic Registers”, OPODIS 2012 - 16^th International Conference on Principles of Distributed Systems, vol. 7702, Lecture Notes in Computer Science, Rome, Italy, pp. 135-150, (Springer) (2012)
  • S. Dubois, S. Tixeuil, N. Zhu : “The Byzantine Brides Problem”, FUN 2012 - 6^th International Conference Fun with Algorithms, vol. 7288, Lecture Notes in Computer Science, Venice, Italy, pp. 107-118, (Springer) (2012)
  • A. Cournier, S. Dubois, A. Lamani, F. Petit, V. Villain : “Snap-Stabilizing Message Forwarding Algorithm on Tree Topologies”, ICDCN 2012 - 13^th International Conference on Distributed Computing and Networking, vol. 7129, Lecture Notes in Computer Science, Hong Kong, China, pp. 46-60, (Springer) (2012)
  • S. Dubois, M. Potop‑Butucaru, M. Nesterenko, S. Tixeuil : “Self-stabilizing byzantine asynchronous unison”, Journal of Parallel and Distributed Computing, vol. 72 (7), pp. 917-923, (Elsevier) (2012)
• 2011
  • S. Dubois : “Tolérer les fautes transitoires, permanentes et intermittentes”, thesis, phd defence 12/01/2011, supervision Tixeuil, Sébastien, co-supervision : Potop-butucaru, Maria (2011)
  • S. Dubois, S. Tixeuil : “A Taxonomy of Daemons in Self-stabilization”, (2011)
  • Sh. Dolev, S. Dubois, M. Potop‑Butucaru, S. Tixeuil : “Stabilizing data-link over non-FIFO channels with optimal fault-resilience”, Information Processing Letters, vol. 111 (18), pp. 912-920, (Elsevier) (2011)
  • A. Cournier, S. Dubois, A. Lamani, F. Petit, V. Villain : “Snap-Stabilizing Message Forwarding Algorithm on Tree Topologies”, (2011)
  • S. Dubois, M. Potop‑Butucaru, S. Tixeuil : “Dynamic FTSS in asynchronous systems: The case of unison”, Theoretical Computer Science, vol. 412 (29), pp. 3418-3439, (Elsevier) (2011)
  • A. Cournier, S. Dubois, V. Villain : “How to improve snap-stabilizing point-to-point communication space complexity?”, Theoretical Computer Science, (Elsevier) (2011)
  • S. Dubois, T. Masuzawa, S. Tixeuil : “Maximum Metric Spanning Tree made Byzantine Tolerant”, 32 pages (2011)
  • S. Dubois, T. Masuzawa, S. Tixeuil : “Self-Stabilization, Byzantine Containment, and Maximizable Metrics: Necessary Conditions”, 17 pages (2011)
  • N. Alon, H. Attiya, Sh. Dolev, S. Dubois, M. Gradinariu Potop‑Butucaru, S. Tixeuil : “Pragmatic Self-Stabilization of Atomic Memory in Message-Passing Systems”, SSS 2011 - 13^th International Symposium on Stabilization, Safety, and Security of Distributed Systems, vol. 6976, Lecture Notes in Computer Science, Grenoble, France, pp. 19-31, (Springer) (2011)
  • S. Dubois, T. Masuzawa, S. Tixeuil : “Maximum Metric Spanning Tree made Byzantine Tolerant”, DISC 2011 - 25^th International Symposium on Distributed Computing, vol. 6950, Lecture Notes in Computer Science, Rome, Italy, pp. 150-164, (Springer) (2011)
  • S. Dubois, T. Masuzawa, S. Tixeuil : “Auto-Stabilisation et Confinement de Fautes Malicieuses : Optimalité du Protocole min+1”, 13^es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), Cap Estérel, France (2011)
  • Sh. Dolev, S. Dubois, M. Potop‑Butucaru, S. Tixeuil : “Communication Optimalement Stabilisante sur Canaux non Fiables et non FIFO”, 13^es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), Cap Estérel, France (2011)
  • A. Lamani, A. Cournier, S. Dubois, F. Petit, V. Villain : “Acheminement de Messages Instantanément Stabilisant : Solution Optimale sur les Topologies Linéaires”, Rencontres francophones du Parallélisme, Saint Malo, France (2011)
• 2010
  • Sh. Dolev, S. Dubois, M. Potop‑Butucaru, S. Tixeuil : “Stabilizing data-link over non-FIFO channels with optimal fault-resilience”, (2010)
  • N. Alon, H. Attiya, Sh. Dolev, S. Dubois, M. Gradinariu, S. Tixeuil : “Brief Announcement: Sharing Memory in a Self-stabilizing Manner”, 24^th International Symposium Distributed Computing DISC, vol. 6343, Lecture Notes in Computer Science, Cambridge, MA, United States, pp. 525-527, (Springer) (2010)
  • S. Dubois, T. Masuzawa, S. Tixeuil : “On Byzantine Containment Properties of the min+1 Protocol”, 12^th International Symposium Stabilization, Safety, and Security of Distributed Systems, SSS, New York, NY, United States, pp. 96-110, (Springer Berlin / Heidelberg) (2010)
  • A. Cournier, S. Dubois, A. Lamani, F. Petit, V. Villain : “Snap-Stabilizing Linear Message Forwarding”, 12^th International Symposium Stabilization, Safety, and Security of Distributed Systems, SSS, vol. 6366, Lecture Notes in Computer Science, New York, NY, United States, pp. 546-559, (Springer) (2010)
  • S. Dubois, T. Masuzawa, S. Tixeuil : “The Impact of Topology on Byzantine Containment in Stabilization”, 24^th International Symposium Distributed Computing DISC, vol. 6343, Lecture Notes in Computer Science, Cambridge, MA, United States, pp. 495-509, (Springer) (2010)
  • A. Lamani, A. Cournier, S. Dubois, F. Petit, V. Villain : “Snap-Stabilizing Linear Message Forwarding”, (2010)
  • S. Dubois, T. Masuzawa, S. Tixeuil : “On Byzantine Containment Properties of the $min+1$ Protocol”, (2010)
  • S. Dubois, T. Masuzawa, S. Tixeuil : “Bounding the Impact of Unbounded Attacks in Stabilization”, 20 pages (2010)
  • S. Dubois, T. Masuzawa, S. Tixeuil : “The Impact of Topology on Byzantine Containment in Stabilization”, 18 pages (2010)
  • S. Dubois, M. Gradinariu Potop‑Butucaru, M. Nesterenko, S. Tixeuil : “Self-stabilizing Byzantine Asynchronous Unison”, OPODIS 2010 - 14^th International Conference On Principles Of DIstributed Systems, vol. 6490, Lecture Notes in Computer Science, Tozeur, Tunisia, pp. 83-86, (Springer) (2010)
  • S. Dubois, T. Masuzawa, S. Tixeuil : “Construction auto-stabilisante d’arbre couvrant en dépit d’actions malicieuses”, 12^es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), Belle Dune, France (2010)
• 2009
  • S. Dubois, M. Gradinariu Potop‑Butucaru, S. Tixeuil : “Brief Announcement: Dynamic FTSS in Asynchronous Systems: The Case of Unison”, 23^rd International Symposium on Distributed Computing, DISC 2009, vol. 5805, Lecture Notes in Computer Science, Elche, Spain, pp. 291-293, (Springer) (2009)
  • A. Cournier, S. Dubois, V. Villain : “Two snap-stabilizing point-to-point communication protocols in message-switched networks”, (2009)
  • A. Cournier, S. Dubois, V. Villain : “How to improve snap-stabilizing point-to-point communication space complexity ?”, SSS 2009 - 11^th International Symposium on Stabilization, Safety, and Security of Distributed Systems, vol. 5873, Lecture Notes in Computer Science, Lyon, France, pp. 195-208, (Springer) (2009)
  • A. Cournier, S. Dubois, V. Villain : “Une CNS pour l’acheminement de messages instantanément stabilisant”, 11^es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel 2009), Carry-Le-Rouet, France (2009)
  • A. Cournier, S. Dubois, V. Villain : “A snap-stabilizing point-to-point communication protocol in message-switched networks”, IPDPS 2009 - 23^th IEEE International Parallel & Distributed Processing Symposium, Rome, Italy, pp. 1-11, (IEEE) (2009)
  • S. Dubois, M. Potop‑Butucaru, S. Tixeuil : “Dynamic FTSS in Asynchronous Systems: the Case of Unison”, 34 pages (2009)
  • S. Dubois, M. Gradinariu Potop‑Butucaru, M. Nesterenko, S. Tixeuil : “Self-Stabilizing Byzantine Asynchronous Unison”, 15 pages (2009)