DALGO : Algorithmique Distribuée

Mots clés

algorithmes, algorithmes distribués, modèles de calcul, agents mobiles, mémoire partagée, passage de messages, réseaux dynamiques, tolérance aux défaillances, réseaux anonymes, calculabilité distribuée, méthodes topologiques, systèmes embarqués, programmation synchrone

Responsable
Jeremie CHALOPIN

Membres

CHALOPIN Jeremie  Enseignant-Chercheur / Chercheur
DAS Shantanu  Enseignant-Chercheur / Chercheur
GODARD Emmanuel  Enseignant-Chercheur / Chercheur
IMBS Damien  Enseignant-Chercheur / Chercheur
LABOUREL Arnaud  Enseignant-Chercheur / Chercheur
NIEBERT Peter  Enseignant-Chercheur / Chercheur
PERDEREAU Eloi  Doctorant

Objectif scientifique

L’équipe d’Algorithmique Distribuée (DALGO) située à Luminy est une équipe du Laboratoire d’Informatique et Systèmes (UMR CNRS 7020). Le concept de système distribué est fondamental tant pour les applications pratiques que pour les fondements théoriques de l’informatique. Un système distribué est un environnement où plusieurs processus collaborent pour réaliser un objectif commun; dans un tel système, les différents processus ne peuvent communiquer directement qu’avec un nombre limité d’autres processus. On cherche à déterminer quels sont les comportements globaux qui peuvent être obtenus dans ces systèmes où les actions des processus n’ont qu’un impact local. L’équipe DALGO s’intéresse à la puissance de calcul de différents modèles distribués, et la complexité des problèmes considérés.

Les types de problématiques principalement considérées par l’équipe sont:

  • Conception et analyse d’algorithmes distribués
  • Systèmes à agents mobiles
  • Systèmes à mémoire partagée et tolérance aux défaillances
  • Modélisation des réseaux dynamiques
  • Systèmes embarqués et programmation synchrone

Publications récentes de l’équipe


36 documents

Article dans une revue12 documents

  • Andreas Bärtschi, Evangelos Bampas, Jérémie Chalopin, Shantanu Das, Christina Karousatou, et al.. Near-gathering of energy-constrained mobile agents. Theoretical Computer Science, Elsevier, 2021, 849, pp.35-46. ⟨10.1016/j.tcs.2020.10.008⟩. ⟨hal-03065725⟩
  • Jérémie Chalopin, Victor Chepoi. A counterexample to Thiagarajan's conjecture on regular event structures. Journal of Computer and System Sciences, Elsevier, 2020, 113, pp.76-100. ⟨10.1016/j.jcss.2020.05.001⟩. ⟨hal-03047160⟩
  • Jérémie Chalopin, Andreas Bärtschi, Shantanu Das, Yann Disser, Barbara Geissmann, et al.. Collaborative delivery with energy-constrained mobile robots. Theoretical Computer Science, Elsevier, 2020, 810, pp.2-14. ⟨10.1016/j.tcs.2017.04.018⟩. ⟨hal-01787176⟩
  • Victor Chepoi, Arnaud Labourel, Sébastien Ratel. On density of subgraphs of halved cubes. European Journal of Combinatorics, Elsevier, 2019, 80, pp.57-70. ⟨10.1016/j.ejc.2018.02.039⟩. ⟨hal-02268756⟩
  • Shantanu Das, Riccardo Focardi, Flaminia Luccio, Euripides Markou, Marco Squarcina. Gathering of robots in a ring with mobile faults. Theoretical Computer Science, Elsevier, 2019, 764, pp.42-60. ⟨10.1016/j.tcs.2018.05.002⟩. ⟨hal-02082148⟩
  • Jérémie Chalopin, Victor Chepoi, Feodor Dragan, Guillaume Ducoffe, Abdulhakeem Mohammed, et al.. Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs. Discrete and Computational Geometry, Springer Verlag, In press, ⟨10.1007/s00454-019-00107-9⟩. ⟨hal-02149991⟩
  • Jérémie Chalopin, Victor Chepoi. 1-Safe Petri nets and special cube complexes: equivalence and applications. ACM Transactions on Computational Logic, Association for Computing Machinery, 2019, 20 (3), pp.17:1-17:49. ⟨10.1145/3322095⟩. ⟨hal-01863455v2⟩
  • Jurek Czyzowicz, Maxime Godon, Evangelos Kranakis, Arnaud Labourel. Group search of the plane with faulty robots. Theoretical Computer Science, Elsevier, 2018. ⟨hal-01959096⟩
  • Shantanu Das, Dariusz Dereniowski, Christina Karousatou. Collaborative Exploration of Trees by Energy-Constrained Mobile Robots. Theory of Computing Systems, Springer Verlag, 2018, 62 (5), pp.1223-1240. ⟨10.1007/s00224-017-9816-3⟩. ⟨hal-02082153⟩
  • Jérémie Chalopin, Victor Chepoi, Hirai Hiroshi, Damian Osajda. Weakly modular graphs and nonpositive curvature. Memoirs of the American Mathematical Society, American Mathematical Society, In press. ⟨hal-01787197⟩
  • Shantanu Das, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, Masafumi Yamashita. Autonomous mobile robots with lights. Theoretical Computer Science, Elsevier, 2016, 609, pp.171-184. ⟨10.1016/j.tcs.2015.09.018⟩. ⟨hal-02082178⟩
  • Jérémie Chalopin, Victor Chepoi, Guyslain Naves. Isometric Embedding of Busemann Surfaces into $L_1$. Discrete and Computational Geometry, Springer Verlag, 2015, 53 (1), pp.16-37. ⟨10.1007/s00454-014-9643-0⟩. ⟨hal-02268738⟩

Communication dans un congrès18 documents

  • Emmanuel Godard, Damien Imbs, Michel Raynal, Gadi Taubenfeld. From Bezout's Identity to Space-Optimal Election in Anonymous Memory Systems. PODC '20: ACM Symposium on Principles of Distributed Computing, Aug 2020, Virtual Event Italy, Italy. pp.41-50, ⟨10.1145/3382734.3405727⟩. ⟨hal-03148627⟩
  • Laurine Bénéteau, Jérémie Chalopin, Victor Chepoi, Yann Vaxès. Medians in Median Graphs and Their Cube Complexes in Linear Time. ICALP 2020 47th International Colloquium on Automata, Languages, and Programming, 2020, Saarbrücken, Germany. pp.10:1--10:17, ⟨10.4230/LIPIcs.ICALP.2020.10⟩. ⟨hal-03047193⟩
  • Emmanuel Godard, Damien Imbs, Michel Raynal, Gadi Taubenfeld. Anonymous Read/Write Memory: Leader Election and De-anonymization. SIROCCO'19 - 26th International Colloquium on Structural Information and Communication Complexity, Jul 2019, L'Aquila, Italy. pp.246-261, ⟨10.1007/978-3-030-24922-9_17⟩. ⟨hal-02445121⟩
  • Jérémie Chalopin, Shantanu Das, Yann Disser, Arnaud Labourel, Matúš Mihalák. Collaborative Delivery on a Fixed Path with Homogeneous Energy-Constrained Agents.. 26th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2019), Jul 2019, L'Aquila, Italy. pp.139-153, ⟨10.1007/978-3-030-24922-9\_10⟩. ⟨hal-02351341⟩
  • Andreas Bärtschi, Evangelos Bampas, Jérémie Chalopin, Shantanu Das, Christina Karousatou, et al.. Near-Gathering of Energy-Constrained Mobile Agents. 26th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2019), Jul 2019, L'Aquila, Italy. pp.52-65, ⟨10.1007/978-3-030-24922-9/_4⟩. ⟨hal-02351154⟩
  • Emmanuel Godard, Damien Imbs, Michel Raynal, Gadi Taubenfeld. Mutex-Based De-anonymization of an Anonymous Read/Write Memory. NETYS 2019 - 7th International Conference on Networked Systems, Jun 2019, Marrakech, Morocco. pp.311-326, ⟨10.1007/978-3-030-31277-0_21⟩. ⟨hal-02445119⟩
  • Shantanu Das, Nikos Giachoudis, Flaminia Luccio, Euripides Markou. Gathering of Robots in a Grid with Mobile Faults. SOFSEM 2019: Theory and Practice of Computer Science., Jan 2019, Nový Smokovec, Slovakia. pp.164-178, ⟨10.1007/978-3-030-10801-4_14⟩. ⟨hal-02082188⟩
  • Victor Chepoi, Arnaud Labourel, Sébastien Ratel. Distance and routing labeling schemes for cube-free median graphs. 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), 2019, Aachen, Germany. pp.15:1--15:14, ⟨10.4230/LIPIcs.MFCS.2019.15⟩. ⟨hal-02268771⟩
  • Jérémie Chalopin, Victor Chepoi, Shay Moran, Manfred Warmuth. Unlabeled Sample Compression Schemes and Corner Peelings for Ample and Maximum Classes. 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), 2019, Patras, Greece. pp.34:1--34:15, ⟨10.4230/LIPIcs.ICALP.2019.34⟩. ⟨hal-02269141⟩
  • Shantanu Das, Dariusz Dereniowski, Przemyslaw Uznanski. Brief Announcement: Energy Constrained Depth First Search. ICALP 2018: 45th International Colloquium on Automata, Languages, and Programming, Jul 2018, Prague, Czech Republic. ⟨hal-02082201⟩
  • Jérémie Chalopin, Victor Chepoi, Feodor Dragan, Guillaume Ducoffe, Abdulhakeem Mohammed, et al.. Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs. 34th International Symposium on Computational Geometry (SoCG 2018), Jun 2018, Budapest, Hungary. pp.22, ⟨10.4230/LIPIcs.SoCG.2018.22⟩. ⟨hal-01836063⟩
  • Jurek Czyzowicz, Maxime Godon, Evangelos Kranakis, Arnaud Labourel, Euripides Markou. Exploring Graphs with Time Constraints by Unreliable Collections of Mobile Robots. 44th International Conference on Current Trends in Theory and Practice of Computer Science, Jan 2018, Krems an der Donau, France. pp.381-395. ⟨hal-01959079⟩
  • Damien Imbs, Achour Mostefaoui, Matthieu Perrin, Michel Raynal. Set-Constrained Delivery Broadcast: Definition, Abstraction Power, and Computability Limits. ICDCN '18 - 19th International Conference on Distributed Computing and Networking, Jan 2018, Varanasi, India. pp.1-10, ⟨10.1145/3154273.3154296⟩. ⟨hal-02053261⟩
  • Kévin Perrot, Cédric Berenger, Peter Niebert. Balanced Connected Partitioning of Unweighted Grid Graphs. Proceedings of MFCS'2018, 2018, Liverpool, United Kingdom. pp.39:1--39:18, ⟨10.4230/LIPIcs.MFCS.2018.39⟩. ⟨hal-02093978⟩
  • Damien Imbs, Petr Kuznetsov, Thibault Rieutord. Progress-Space Tradeoffs in Single-Writer Memory Implementations. 21st International Conference on Principles of Distributed Systems (OPODIS 2017), Dec 2017, Lisbon, Portugal. ⟨10.4230/LIPIcs.OPODIS.2017.9⟩. ⟨hal-01787848⟩
  • Damien Imbs, Achour Mostefaoui, Matthieu Perrin, Michel Raynal. Which Broadcast Abstraction Captures k-Set Agreement?. 31st International Symposium on Distributed Computing (DISC 2017), Oct 2017, Vienna, Austria. pp.1-16, ⟨10.4230/LIPIcs.DISC.2017.27⟩. ⟨hal-01787801⟩
  • Andreas Bärtschi, Jérémie Chalopin, Shantanu Das, Yann Disser, Daniel Graf, et al.. Energy-Efficient Delivery by Heterogeneous Mobile Agents. STACS 2017, 2017, Hannover, Germany. ⟨10.4230/LIPIcs.STACS.2017.10⟩. ⟨hal-01787218⟩
  • Jérémie Chalopin, Victor Chepoi. A Counterexample to Thiagarajan's Conjecture on Regular Event Structures. ICALP 2017, 2017, Warsaw, Poland. ⟨10.4230/LIPIcs.ICALP.2017.101⟩. ⟨hal-01787205⟩

Chapitre d'ouvrage3 documents


Pré-publication, Document de travail2 documents

  • Jérémie Chalopin, Victor Chepoi, Shay Moran, Manfred K. Warmuth. Unlabeled sample compression schemes and corner peelings for ample and maximum classes. 2019. ⟨hal-02065772⟩
  • Jérémie Chalopin, Victor Chepoi, Feodor F. Dragan, Guillaume Ducoffe, Abdulhakeem Mohammed, et al.. Fast approximation and exact computation of negative curvature parameters of graphs. 2018. ⟨hal-01737445⟩

Thèse1 document

  • Sébastien Ratel. Densité, VC-dimension et étiquetages de graphes. Mathématique discrète [cs.DM]. Aix-Marseile Université, 2019. Français. ⟨tel-02436255⟩

Documents récupérés de l'archive ouverte HAL logo