Search

Your search keyword '"Durand, Anaïs"' showing total 44 results
Start Over Author "Durand, Anaïs"

Refine your results

more »

more »

more »
44 results on '"Durand, Anaïs"'

1. Optimal Asynchronous Perpetual Grid Exploration

Author

Bramas, Quentin, Devismes, Stéphane, Durand, Anaïs, Lafourcade, Pascal, Lamani, Anissa, Goos, Gerhard, Series Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Masuzawa, Toshimitsu, editor, Katayama, Yoshiaki, editor, Kakugawa, Hirotsugu, editor, Nakamura, Junya, editor, and Kim, Yonghwan, editor

Published
2025
Full Text
View/download PDF

2. Better Sooner Rather Than Later

Author

Durand, Anaïs, Raynal, Michel, and Taubenfeld, Gadi

Subjects
Computer Science - Distributed, Parallel, and Cluster Computing
Abstract

This article unifies and generalizes fundamental results related to $n$-process asynchronous crash-prone distributed computing. More precisely, it proves that for every $0\leq k \leq n$, assuming that process failures occur only before the number of participating processes bypasses a predefined threshold that equals $n-k$ (a participating process is a process that has executed at least one statement of its code), an asynchronous algorithm exists that solves consensus for $n$ processes in the presence of $f$ crash failures if and only if $f \leq k$. In a very simple and interesting way, the "extreme" case $k=0$ boils down to the celebrated FLP impossibility result (1985, 1987). Moreover, the second extreme case, namely $k=n$, captures the celebrated mutual exclusion result by E.W. Dijkstra (1965) that states that mutual exclusion can be solved for $n$ processes in an asynchronous read/write shared memory system where any number of processes may crash (but only) before starting to participate in the algorithm (that is, participation is not required, but once a process starts participating it may not fail). More generally, the possibility/impossibility stated above demonstrates that more failures can be tolerated when they occur earlier in the computation (hence the title)., Comment: 10 pages

Published
2023

3. Better Sooner Rather Than Later

Author

Durand, Anaïs, Raynal, Michel, Taubenfeld, Gadi, Goos, Gerhard, Series Editor, Hartmanis, Juris, Founding Editor, van Leeuwen, Jan, Series Editor, Hutchison, David, Editorial Board Member, Kanade, Takeo, Editorial Board Member, Kittler, Josef, Editorial Board Member, Kleinberg, Jon M., Editorial Board Member, Kobsa, Alfred, Series Editor, Mattern, Friedemann, Editorial Board Member, Mitchell, John C., Editorial Board Member, Naor, Moni, Editorial Board Member, Nierstrasz, Oscar, Series Editor, Pandu Rangan, C., Editorial Board Member, Sudan, Madhu, Series Editor, Terzopoulos, Demetri, Editorial Board Member, Tygar, Doug, Editorial Board Member, Weikum, Gerhard, Series Editor, Vardi, Moshe Y, Series Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, and Emek, Yuval, editor

Published
2024
Full Text
View/download PDF

6. Ressource Efficient Stabilization for Local Tasks despite Unknown Capacity Links

Author

Blin, Lélia, Durand, Anaïs, and Tixeuil, Sébastien

Subjects
Computer Science - Distributed, Parallel, and Cluster Computing
Abstract

Self-stabilizing protocols enable distributed systems to recover correct behavior starting from any arbitrary configuration. In particular, when processors communicate by message passing, fake messages may be placed in communication links by an adversary. When the number of such fake messages is unknown, self-stabilization may require huge resources: (a) generic solutions (a.k.a. data link protocols) require unbounded resources, which makes them unrealistic to deploy and (b) specific solutions (e.g., census or tree construction) require $O(n\log n)$ or $O(\Delta\log n)$ bits of memory per node, where $n$ denotes the network size and $\Delta$ its maximum degree, which may prevent scalability. We investigate the possibility of resource efficient self-stabilizing protocols in this context. Specifically, we present a self-stabilizing protocol for $(\Delta+1)$-coloring in any n-node graph, under the asynchronous message-passing model. It is deterministic, it converges in $O(k\Delta n^2\log n)$ message exchanges, where $k$ is the bound of the link capacity in terms of number of messages, and it uses messages on $O(\log\log n+\log\Delta)$ bits with a memory of $O(\Delta\log\Delta+\log\log n)$ bits at each node. The resource consumption of our protocol is thus almost oblivious to the number of nodes, enabling scalability. Moreover, a striking property of our protocol is that the nodes do not need to know the number, or any bound on the number of messages initially present in each communication link of the initial (potentially corrupted) network configuration. This permits our protocol to handle any future network with unknown message capacity communication links. A key building block of our coloring scheme is a spanning directed acyclic graph construction, that is of independent interest, and can serve as a useful tool for solving other tasks in this challenging setting.

Published
2020

10. Perpetual Torus Exploration by Myopic Luminous Robots

Author

Darwich, Omar, Ulucan, Ahmet-Sefa, Bramas, Quentin, Lamani, Anissa, Durand, Anaïs, Lafourcade, Pascal, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Devismes, Stéphane, editor, Petit, Franck, editor, Altisen, Karine, editor, Di Luna, Giuseppe Antonio, editor, and Fernandez Anta, Antonio, editor

Published
2022
Full Text
View/download PDF

11. Reaching Consensus in the Presence of Contention-Related Crash Failures

Author

Durand, Anaïs, Raynal, Michel, Taubenfeld, Gadi, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Devismes, Stéphane, editor, Petit, Franck, editor, Altisen, Karine, editor, Di Luna, Giuseppe Antonio, editor, and Fernandez Anta, Antonio, editor

Published
2022
Full Text
View/download PDF

13. Acyclic Strategy for Silent Self-Stabilization in Spanning Forests

Author

Altisen, Karine, Devismes, Stéphane, and Durand, Anaïs

Subjects
Computer Science - Distributed, Parallel, and Cluster Computing, C.2.4 Distributed Systems
Abstract

In this paper, we formalize design patterns, commonly used in the self-stabilizing area, to obtain general statements regarding both correctness and time complexity guarantees. Precisely, we study a general class of algorithms designed for networks endowed with a sense of direction describing a spanning forest (e.g., a directed tree or a network where a directed spanning tree is available) whose characterization is a simple (i.e., quasi-syntactic) condition. We show that any algorithm of this class is (1) silent and self-stabilizing under the distributed unfair daemon, and (2) has a stabilization time which is polynomial in moves and asymptotically optimal in rounds. To illustrate the versatility of our method, we review several existing works where our results apply.

Published
2018

16. Reducing the Number of Messages in Self-stabilizing Protocols

Author

Durand, Anaïs, Kutten, Shay, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Ghaffari, Mohsen, editor, Nesterenko, Mikhail, editor, Tixeuil, Sébastien, editor, Tucci, Sara, editor, and Yamauchi, Yukiko, editor

Published
2019
Full Text
View/download PDF

17. Set Agreement and Renaming in the Presence of Contention-Related Crash Failures

Author

Durand, Anaïs, Raynal, Michel, Taubenfeld, Gadi, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Izumi, Taisuke, editor, and Kuznetsov, Petr, editor

Published
2018
Full Text
View/download PDF

18. Message-Efficient Self-stabilizing Transformer Using Snap-Stabilizing Quiescence Detection

Author

Durand, Anaïs, Kutten, Shay, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Lotker, Zvi, editor, and Patt-Shamir, Boaz, editor

Published
2018
Full Text
View/download PDF

20. Gradual Stabilization Under -Dynamics

Author

Altisen, Karine, Devismes, Stéphane, Durand, Anaïs, Petit, Franck, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Dutot, Pierre-François, editor, and Trystram, Denis, editor

Published
2016
Full Text
View/download PDF

21. Leader Election in Rings with Bounded Multiplicity (Short Paper)

Author

Altisen, Karine, Datta, Ajoy K., Devismes, Stéphane, Durand, Anaïs, Larmore, Lawrence L., Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Bonakdarpour, Borzoo, editor, and Petit, Franck, editor

Published
2016
Full Text
View/download PDF

23. Concurrency in Snap-Stabilizing Local Resource Allocation

Author

Altisen, Karine, Devismes, Stéphane, Durand, Anaïs, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Bouajjani, Ahmed, editor, and Fauconnier, Hugues, editor

Published
2015
Full Text
View/download PDF

24. Exploration en 3D par des robots désorientés : tu montes en bas ou tu descends en haut ?

Author

Bramas, Quentin, Devismes, Stéphane, Durand, Anaïs, Lafourcade, Pascal, Lamani, Anissa, Université de Strasbourg (UNISTRA), Equipe Réseaux du laboratoire ICUBE (ICUBE-Réseaux), Département Informatique du laboratoire ICUBE (ICUBE-Informatique), Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie (ICube), École Nationale du Génie de l'Eau et de l'Environnement de Strasbourg (ENGEES)-Université de Strasbourg (UNISTRA)-Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Les Hôpitaux Universitaires de Strasbourg (HUS)-Centre National de la Recherche Scientifique (CNRS)-Matériaux et Nanosciences Grand-Est (MNGE), Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Réseau nanophotonique et optique, Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS)-École Nationale du Génie de l'Eau et de l'Environnement de Strasbourg (ENGEES)-Université de Strasbourg (UNISTRA)-Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie (ICube), Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS), Université de Picardie Jules Verne (UPJV), Modélisation, Information et Systèmes - UR UPJV 4290 (MIS), Université Clermont Auvergne (UCA), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), and ANR-22-CE25-0008,SKYDATA,Un nouveau paradigme de donnée: Les données autononomes et intelligentes(2022)

Subjects
robots mobiles, grille 3D finie, algorithme distribué, exploration exclusive perpétuelle, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract

International audience; Nous nous intéressons à l'exploration d'un environnement 3D par un petit nombre de robots ayant des capacités très limitées. Ces robots ont une vision à portée bornée et des capacités d'orientation limitées. Précisément, ils doivent explorer perpétuellement une grille 3D bien qu'ils n'aient pas de système de coordonnées commun. Cependant, ils s'accordent sur une chiralité commune. Ils exécutent le même algorithme de manière synchrone et sont équipés de lumières capables de changer de couleur. En outre, chaque robot dispose d'un panel réduit de couleurs et ces couleurs constituent les seules informations pouvant être mémorisées par le robot et perçues par les robots alentour. Dans ce cadre restreint, notre problème consiste à assurer que les robots visitent infiniment souvent et de manière exclusive chaque noeud d'une grille 3D. Notre but est de proposer des solutions mobilisant le moins de ressources possibles. Dans ce contexte, nous montrons qu'avec une visibilité à un saut, trois robots sont nécessaires et suffisants pour résoudre l'exploration perpétuelle exclusive d'une grille 3D. L'algorithme proposé nécessite cependant cinq couleurs. Nous proposons aussi une solution utilisant uniquement une couleur (l'optimal) et cinq robots avec une visibilité à deux sauts.

Published
2023

25. Comment se mettre d'accord quand les autres dorment ?

Author

Durand, Anaïs, Raynal, Michel, Taubenfeld, Gadi, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), the World Is Distributed Exploring the tension between scale and coordination (WIDE), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Reichman University [Herzliya], ANR-20-CE25-0002,ByBloS,Au-delà des Blockchains : Modules de construction pour les applications à grande échelle zero-confiance multi-utilisateurs(2020), ANR-10-LABX-0781,PriCLeSS, and ANR-22-CE25-0008,SKYDATA,Un nouveau paradigme de donnée: Les données autononomes et intelligentes(2022)

Subjects
Systèmes asynchrones, Consensus, Nombre-consensus, Contention, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Registres
Abstract

International audience

Published
2023

26. Self-stabilizing Leader Election in Polynomial Steps

Author

Altisen, Karine, Cournier, Alain, Devismes, Stéphane, Durand, Anaïs, Petit, Franck, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Felber, Pascal, editor, and Garg, Vijay, editor

Published
2014
Full Text
View/download PDF

30. Beedroids: How Luminous Autonomous Swarms of UAVs Can Save the World?

Author

Bramas, Quentin, Devismes, Stéphane, Durand, Anaïs, Lafourcade, Pascal, Lamani, Anissa, Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie (ICube), École Nationale du Génie de l'Eau et de l'Environnement de Strasbourg (ENGEES)-Université de Strasbourg (UNISTRA)-Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Les Hôpitaux Universitaires de Strasbourg (HUS)-Centre National de la Recherche Scientifique (CNRS)-Matériaux et Nanosciences Grand-Est (MNGE), Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Réseau nanophotonique et optique, Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS), Modélisation, Information et Systèmes - UR UPJV 4290 (MIS), Université de Picardie Jules Verne (UPJV), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), and Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA)

Subjects
greenhouse, Bee extinction, luminous swarms of beedroids, perpetual flower pollination problem, Theory of computation → Distributed algorithms, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract

Bee extinction is a great risk for humanity. To circumvent this ineluctable disaster, we propose to develop beedroids, i.e., small UAVs mimicking the behaviors of real bees. Those beedroids are endowed with very weak capabilities (short-range visibility sensors, no GPS, light with a few colors, ...). Like real bees, they have to self-organize together into swarms. Beedroid swarms will be deployed in cuboid-shaped greenhouse. Each beedroid swarm will have to indefinitely search for flowers to pollinate in its greenhouse. We model this problem as a perpetual exploration of a 3D grid by a swarm of beedroids. In this paper, we propose two optimal solutions to solve this problem and so to save humanity., LIPIcs, Vol. 226, 11th International Conference on Fun with Algorithms (FUN 2022), pages 7:1-7:21

Published
2022
Full Text
View/download PDF

31. Beedroids: How Luminous Autonomous Swarms of UAVs Can Save the World?

Author

Quentin Bramas and Stéphane Devismes and Anaïs Durand and Pascal Lafourcade and Anissa Lamani, Bramas, Quentin, Devismes, Stéphane, Durand, Anaïs, Lafourcade, Pascal, Lamani, Anissa, Quentin Bramas and Stéphane Devismes and Anaïs Durand and Pascal Lafourcade and Anissa Lamani, Bramas, Quentin, Devismes, Stéphane, Durand, Anaïs, Lafourcade, Pascal, and Lamani, Anissa

Abstract

Bee extinction is a great risk for humanity. To circumvent this ineluctable disaster, we propose to develop beedroids, i.e., small UAVs mimicking the behaviors of real bees. Those beedroids are endowed with very weak capabilities (short-range visibility sensors, no GPS, light with a few colors, ...). Like real bees, they have to self-organize together into swarms. Beedroid swarms will be deployed in cuboid-shaped greenhouse. Each beedroid swarm will have to indefinitely search for flowers to pollinate in its greenhouse. We model this problem as a perpetual exploration of a 3D grid by a swarm of beedroids. In this paper, we propose two optimal solutions to solve this problem and so to save humanity.

Published
2022
Full Text
View/download PDF

34. On peut tromper mille personnes mille fois, mais pas plus

Author

Blin, Lélia, Durand, Anaïs, Tixeuil, Sébastien, and Durand, Anaïs

Subjects
canaux de communication non bornés, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Auto-stabilisation, coloration
Abstract

Nous explorons la possibilité de concevoir des algorithmes auto-stabilisants pour des systèmes distribués à passage de messages où l'adversaire peut initialement placer un nombre arbitraire de messages corrompus (leur contenu est également déterminé par l'adversaire) dans les canaux de communications. Plus précisément, nous proposons un algorithme auto-stabilisant de (∆ + 1)-coloration pour un graphe arbitraire de degré maximum ∆ dans le modèle à passage de messages asynchrone. Cet algorithme est déterministe et converge en O(k ∆ n 2 log n) échanges de messages, où k est une borne sur la capacité des canaux de communications et n est le nombre de processus. Notre algorithme utilise des messages de O(log log n + log ∆) bits et une mémoire de O(∆ log ∆ + log log n) bits par processus. La propriété fondamentale de notre algorithme est le fait que les processus ne nécessitent aucune connaissance sur le nombre de messages initialement présents dans les canaux (k est inconnu). Pour concevoir notre protocole de coloration, nous utilisons une construction auto-stabilisante de graphe orienté acyclique couvrant, qui peut également servir d'outil pour résoudre d'autres tâches dans le même contexte.

Published
2020

39. Pannes de processus liées à la contention

Author

Durand, Anaïs, Raynal, Michel, Taubenfeld, Gadi, DistributEd aLgorithms and sYStems (DELYS), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), the World Is Distributed Exploring the tension between scale and coordination (WIDE), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), The Hong Kong Polytechnic University [Hong Kong] (POLYU), Interdisciplinary Center [Israël] (IDC), Interdisciplinary Center, Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique)

Subjects
Systèmes asynchrones, Renommage, k-accord, Tolérance aux pannes, Contention, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract

International audience; Cet article est un résumé étendu de [DRT18] dans lequel nous nous intéressons à un nouveau type de pannes de processus défini récemment par l'un des auteurs [Tau18] : les pannes λ-contraintes. Cette nouvelle notion est explicitement liée à la contention. En effet, elle ne considère que les exécutions dans lesquelles les pannes de processus se produisent lorsque la contention est plus petite où égale à un seuil λ donné. Si des pannes se produisent lorsque la contention a dépassé ce seuil λ, aucune propriété de correction (comme par exemple la terminaison) n'est garantie. [Tau18] montre que, lorsque λ = n − 1, il est possible de résoudre le problème du consensus dans un système asynchrone à registres atomiques de n processus même si un processus tombe en panne, outrepassant ainsi le résultat d'impossibilité FLP. Nous proposons ici des algorithmes pour les problèmes de k-accord et de renommage qui tolèrent à la fois des pannes de processus "classiques" et des pannes λ-contraintes.

Published
2019

40. Élection et anneaux unidirectionnels en présence d’homonymes

Author

Durand, Anaïs, SYNCHRONE, VERIMAG (VERIMAG - IMAG), Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Grenoble (INPG)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Université Joseph Fourier - Grenoble 1 (UJF)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Grenoble (INPG)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Université Joseph Fourier - Grenoble 1 (UJF), and Durand, Anaïs

Subjects
Anneau unidirectionnel, Homonymes, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Élection de leader, Algorithmes distribués, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract

International audience; Cet article est un résumé de deux articles [1, 2] portant sur l'élection de leader dans les anneaux unidirectionnels en présence de processus homonymes, c'est-à-dire des anneaux unidirectionnels où les processus sont nommés par des étiquettes qui ne sont pas nécessairement uniques. Nous étudions la résolution de ce problème dans des classes d'anneaux où l'étiquetage des processus est asymétrique. Nous proposons trois algorithmes pour des classes où une borne sur la multiplicité des étiquettes (c'est-à-dire, le nombre de processus partageant la même étiquette) est connue.

Published
2017

41. Gradual stabilization

Author

Altisen, Karine, primary, Devismes, Stéphane, additional, Durand, Anaïs, additional, and Petit, Franck, additional

Published
2019
Full Text
View/download PDF

42. Algorithmes distribués efficaces adaptés à un contexte incertain

Author

Durand, Anaïs, VERIMAG (VERIMAG - IMAG), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Université Grenoble Alpes, Karine Altisen, Stéphane Devismes, and STAR, ABES

Subjects
[INFO.INFO-OH] Computer Science [cs]/Other [cs.OH], Fault-Tolerance, Dynamic networks, Autostabilisation, Réseaux dynamiques, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], Anonymat, Distributed algorithms, Tolérance aux pannes, Algorithmes distribués, Anonymity, Self-Stabilization
Abstract

Distributed systems become increasingly wide and complex, while their usage extends to various domains (e.g., communication, home automation, monitoring, cloud computing). Thus, distributed systems are executed in diverse contexts. In this thesis, we focus on uncertain contexts, i.e., the context is not completely known a priori or is unsettled. More precisely, we consider two main kinds of uncertainty: processes that are not completely identified and the presence of faults. The absence of identification is frequent in large networks composed of massively produced and deployed devices. In addition, anonymity is often required for security and privacy. Similarly, large networks are exposed to faults (e.g, process crashes, wireless connection drop), but the service must remain available.This thesis is composed of four main contributions. First, we study the leader election problem in unidirectional rings of homonym processes, i.e., processes are identified but their ID is not necessarily unique. Then, we propose a silent self-stabilizing leader election algorithm for arbitrary connected network. This is the first algorithm under such conditions that stabilizes in a polynomial number of steps. The third contribution is a new stabilizing property designed for dynamic networks that ensures fast and gradual convergences after topological changes. We illustrate this property with a clock synchronizing algorithm. Finally, we consider the issue of concurrency in resource allocation problems. In particular, we study the level of concurrency that can be achieved in a wide class of resource allocation problem, i.e., the local resource allocation., Les systèmes distribués sont de plus en plus grands et complexes, alors que leur utilisation s'étend à de nombreux domaines (par exemple, les communications, la domotique, la surveillance, le ``cloud''). Par conséquent, les contextes d'exécution des systèmes distribués sont très divers. Dans cette thèse, nous nous focalisons sur des contextes incertains, autrement dit, le contexte n'est pas complètement connu au départ ou il est changeant. Plus précisément, nous nous focalisons sur deux principaux types d'incertitudes : une identification incomplète des processus et la présence de fautes. L'absence d'identification est fréquente dans de grands réseaux composés d'appareils produits et déployés en masse. De plus, l'anonymat est souvent une demande pour la sécurité et la confidentialité. De la même façon, les grands réseaux sont exposés aux pannes comme la panne définitive d'un processus ou une perte de connexion sans fil. Néanmoins, le service fourni doit rester disponible.Cette thèse est composée de quatre contributions principales. Premièrement, nous étudions le problème de l'élection de leader dans les anneaux unidirectionnels de processus homonymes (les processus sont identifiés mais leur ID n'est pas forcément unique). Par la suite, nous proposons un algorithme d'élection de leader silencieux et autostabilisant pour tout réseau connecté. Il s'agit du premier algorithme fonctionnant sous de telles conditions qui stabilise en un nombre polynomial de pas de calcul. La troisième contribution est une nouvelle propriété de stabilisation conçue pour les réseaux dynamiques qui garantit des convergences rapides et progressives après des changements topologiques. Nous illustrons cette propriété avec un algorithme de synchronisation d'horloges. Finalement, nous considérons la question de la concurrence dans les problèmes d'allocation de ressources. En particulier, nous étudions le niveau de concurrence qui peut être atteint dans une grande classe de problèmes d'allocation de ressources, l'allocation de ressources locales.

Published
2017

Catalog

Books, media, physical & digital resources
See catalog results