DALGO : Distributed Algorithms

Keys words

algorithms, distributed algorithms, computation models, mobile agents, shared memory, message passing systems, dynamic networks, fault tolerance, swarm robotics, anonymous networks, distributed computability, topological methods, embedded systems, synchronous programming

Head

Jérémy CHALOPIN

Permanent Members

CHALOPIN JérémieChargé de recherche
Courriel : jeremie.chalopin@lis-lab.fr
Page personnelle : https://pageperso.lis-lab.fr/jeremie.chalopin/
DAS ShantanuMaitre de Conférences
Courriel : shantanu.das@lis-lab.fr
Page personnelle : https://pageperso.lis-lab.fr/shantanu.das/
GODARD EmmanuelMaitre de Conférences
Courriel : emmanuel.godard@lis-lab.fr
Page personnelle : https://pageperso.lis-lab.fr/emmanuel.godard/
IMBS DamienMaitre de Conférences
Courriel : damien.imbs@lis-lab.fr
LABOUREL ArnaudMaitre de Conférences
Courriel : arnaud.labourel@lis-lab.fr
Page personnelle : https://pageperso.lis-lab.fr/arnaud.labourel/
NIEBERT PeterMaitre de Conférences
Courriel : peter.niebert@lis-lab.fr
Page personnelle : https://pageperso.lis-lab.fr/peter.niebert/

Phd Students

BERENGER CédricDoctorant
Courriel : cedric.berenger@lis-lab.fr
PERDEREAU ÉloiDoctorant
Courriel : eloi.perdereau@lis-lab.fr
Page personnelle : https://pageperso.lis-lab.fr/eloi.perdereau/

Other Staff

Scientific goal

The Distributed Algorithms (DALGO) team belongs to the Laboratoire d’Informatique et Systèmes (LIS, UMR 7020) and is based in Luminy.

The concept of distributed systems is fundamental for practical applications as well as for the theoretical foundations of computer science. A distributed system is an environment where several processes collaborate to achieve a common goal; in such a system, processes can only communicate directly with a limited number of other processes. We are interested in studying the global behaviors that can be obtained in such systems when the actions of the processes have only a local impact. The DALGO team is interested in the computational power of several models of distributed computing, as well as in the complexity of fundamental problems in these models.

The members of the team are particularly interested in the following topics:

  • Design and analysis of distributed algorithms
  • Mobile Agent Systems
  • Shared memory systems and fault tolerance
  • Dynamic networks
  • Embedded systems and synchronous programming

Web Site

For more detail :

Scientific publications


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⟩

Powered by HAL logo