27 results on '"Tixeuil, Sébastien"'
Search Results
2. Formal Methods for Mobile Robots
- Author
-
Potop-Butucaru, Maria, Sznajder, Nathalie, Tixeuil, Sébastien, Urbain, Xavier, 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, Flocchini, Paola, editor, Prencipe, Giuseppe, editor, and Santoro, Nicola, editor
- Published
- 2019
- Full Text
- View/download PDF
3. Fault-Tolerant Mobile Robots
- Author
-
Défago, Xavier, Potop-Butucaru, Maria, Tixeuil, Sébastien, 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, Flocchini, Paola, editor, Prencipe, Giuseppe, editor, and Santoro, Nicola, editor
- Published
- 2019
- Full Text
- View/download PDF
4. Packet Efficient Implementation of the Omega Failure Detector
- Author
-
Bramas, Quentin, Foreback, Dianne, Nesterenko, Mikhail, and Tixeuil, Sébastien
- Published
- 2019
- Full Text
- View/download PDF
5. Asynchronous Gathering in a Torus
- Author
-
Kamei, Sayaka, Lamani, Anissa, Ooshita, Fukuhito, Tixeuil, Sébastien, Wada, Koichi, Tixeuil, Sébastien, Auto-stabilisation et amélioration de la sûreté dans les environnements distribués évoluant dans le temps - - ESTATE2016 - ANR-16-CE25-0009 - AAPG2016 - VALID, Sûreté et preuve de protocoles adaptatifs pour robots oublieux - - SAPPORO2019 - ANR-19-CE25-0005 - AAPG2019 - VALID, Graduate School of Advanced Science and Engineering [Higashi-Hiroshima], Hiroshima University, 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), Nara Institute of Science and Technology - Graduate School of Information Science (NAIST), Nara Institute of Science and Technology, Networks and Performance Analysis (NPA), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Faculty of Science and Engineering, Hosei University, Hosei University, ANR-16-CE25-0009,ESTATE,Auto-stabilisation et amélioration de la sûreté dans les environnements distribués évoluant dans le temps(2016), ANR-19-CE25-0005,SAPPORO,Sûreté et preuve de protocoles adaptatifs pour robots oublieux(2019), Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-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)-Réseau nanophotonique et optique, Centre National de la Recherche Scientifique (CNRS)-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)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Matériaux et nanosciences d'Alsace (FMNGE), Institut de Chimie du CNRS (INC)-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)-Centre National de la Recherche Scientifique (CNRS)-Institut de Chimie du CNRS (INC)-Université de Strasbourg (UNISTRA)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS), Laboratory of Information, Network and Communication Sciences (LINCS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT)-Sorbonne Université (SU), and Hosei University [Chiyoda]
- Subjects
FOS: Computer and information sciences ,[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,Theory of computation ��� Distributed algorithms ,Robots gathering ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,[INFO.INFO-RB] Computer Science [cs]/Robotics [cs.RO] ,Autonomous distributed systems ,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG] ,Torus ,Computer Science::Robotics ,[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] ,Computer Science - Distributed, Parallel, and Cluster Computing ,[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG] ,[INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,Distributed algorithms ,[INFO.INFO-RB]Computer Science [cs]/Robotics [cs.RO] ,[INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC] ,Distributed, Parallel, and Cluster Computing (cs.DC) ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] - Abstract
We consider the gathering problem for asynchronous and oblivious robots that cannot communicate explicitly with each other, but are endowed with visibility sensors that allow them to see the positions of the other robots. Most of the investigations on the gathering problem on the discrete universe are done on ring shaped networks due to the number of symmetric configuration. We extend in this paper the study of the gathering problem on torus shaped networks assuming robots endowed with local weak multiplicity detection. That is, robots cannot make the difference between nodes occupied by only one robot from those occupied by more than one robots unless it is their current node. As a consequence, solutions based on creating a single multiplicity node as a landmark for the gathering cannot be used. We present in this paper a deterministic algorithm that solves the gathering problem starting from any rigid configuration on an asymmetric unoriented torus shaped network., Comment: 41 pages
- Published
- 2022
- Full Text
- View/download PDF
6. Probabilistic Self-stabilizing Vertex Coloring in Unidirectional Anonymous Networks
- Author
-
Bernard, Samuel, Devismes, Stéphane, Paroux, Katy, Potop-Butucaru, Maria, Tixeuil, Sébastien, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Kant, Krishna, editor, Pemmaraju, Sriram V., editor, Sivalingam, Krishna M., editor, and Wu, Jie, editor
- Published
- 2010
- Full Text
- View/download PDF
7. A Taxonomy of Daemons in Self-stabilization
- Author
-
Dubois, Swan, Tixeuil, Sébastien, Large-Scale Distributed Systems and Applications (Regal), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), Networks and Performance Analysis (NPA), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), SHAMAN, ANR-08-VERS-0015,SHAMAN,Architectures auto-* pour les réseaux adverses et malicieux(2008), and Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)
- Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,Fairness ,Boundedness ,Scheduler ,Taxonomy ,Daemon ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,Distributed Algorithms ,[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] ,Transformers ,Enabledness ,Centrality ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,Self-stabilization - Abstract
26 pages; We survey existing scheduling hypotheses made in the literature in self-stabilization, commonly referred to under the notion of daemon. We show that four main characteristics (distribution, fairness, boundedness, and enabledness) are enough to encapsulate the various differences presented in existing work. Our naming scheme makes it easy to compare daemons of particular classes, and to extend existing possibility or impossibility results to new daemons. We further examine existing daemon transformer schemes and provide the exact transformed characteristics of those transformers in our taxonomy.
- Published
- 2011
8. Vers l'auto-stabilisation des systèmes à grande échelle
- Author
-
Tixeuil, Sébastien, Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Université Paris Sud - Paris XI, Serge Haddad(haddad@lamsade.dauphine.fr), FRAGILE, SR2I, SOGEA, ALPAGE, Mobicoop, and STAR
- Subjects
Fault-tolerance ,[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] ,Sytèmes distribués ,Distributed Systems ,Large-scale systems ,Algorithmique répartie ,Auto-stabilisation ,Tolérance aux pannes ,Systèmes à grande échelle ,Self-stabilization ,Distributed Algorithms - Abstract
Toward self-stabilizing large-scale systems.; Vers l'auto-stabilisation des systèmes à grande échelle.
- Published
- 2006
9. The complexity of data aggregation in static and dynamic wireless sensor networks.
- Author
-
Bramas, Quentin and Tixeuil, Sébastien
- Subjects
- *
WIRELESS sensor networks , *NP-complete problems , *DYNAMICAL systems , *COMPUTATIONAL complexity , *GRAPH theory , *DISTRIBUTED algorithms - Abstract
The contribution of this paper is threefold. First, we give tight bounds for the complexity of the problem of data aggregation in static networks. In more details, we show that the problem remains NP-complete when the graph is of degree at most three. Second, we investigate the complexity of the same problem in a dynamic network, that is, a network whose topology can evolve through time. In the case of dynamic networks, we show that the problem is NP-complete even in the case where the graph is of degree at most two. Third, we give the first lower and upper bounds for the minimum data aggregation time in a dynamic graph. We also observe that even in a well-connected evolving graphs, the optimal solution cannot be found by a distributed algorithm or by a centralized algorithm that does not know the future. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
10. Auto-stabilisation Efficace
- Author
-
Tixeuil, Sébastien, Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Université Paris Sud - Paris XI, and Joffroy Beauquier(jb@lri.fr)
- Subjects
[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] ,Distributed Systems ,Algorithmique répartie ,Fault Tolerance ,Auto-stabilisation ,Systèmes répartis ,Tolérance aux pannes ,Self-stabilization ,Distributed Algorithms - Abstract
When a distributed system is subject to transient failures that arbitrarily modify its state, it is crucial to recover a correct behavior within finite time. Self-stabilization offers such a guarantee, but usually uses large resources. In this thesis, we focus on minimizing these resources when such solutions exist.We introduced the concept of transient failure detectors, oracles that are called by processors, which notify if transient failures occurred within constant time. Our implementation enables classifying classic problems according to the specific resources dedicated to error detection.A natural extension was to show that a local property on the local code executed by each processor is sufficient to guarantee self-stabilization of the whole system, whatever the computation assumptions and communication graph may be. Since the original algorithm is not modified, it is overhead-free. Similarly, we developed two synchronizers that enable dynamic tasks to be solved self-stabilizingly, whose memory overhead is constant. Moreover, one of them is snap-stabilizing. Finally, we presented a general technique to systematically reduce the communicationcost, assuming a bounded retransmission delay, and we gave a general framework and tools to design self-stabilizing algorithms in this context.; Quand un système réparti est sujet à des défaillances transitoires qui modifient arbitrairement son état, il est crucial de pouvoir retrouver un comportement correct au bout d'un temps fini. L'auto-stabilisation présente une telle garantie, mais en général au prix de ressources importantes. Dans cette thèse, notre démarche a consisté à minimiser ces ressources lorsque cela était possible. Nous avons développé le concept de détecteur de défaillances transitoires, des oracles appelés par les processeurs du système, qui indiquent si des défaillances transitoires sont survenues, en un temps constant. Notre implantation permet de classifier les problèmes classiques suivant les ressources spécifiques nécessaires à la détection d'une erreur. Pour les tâches statiques, une suite naturelle a été de montrer qu'une condition sur le code localement exécuté par chaque processeur pouvait être suffisante pour garantir l'auto-stabilisation du système tout entier, indépendamment des hypothèses d'exécution et de la topologie du graphe de communication. Du fait que l'algorithme n'est pas modifié, il est forcément sans surcoût. De manière duale, nous avons développé des outils de synchronisation permettant de construire des algorithmes auto-stabilisants pour des spécifications dynamiques avec un surcoût en mémoire constant, c'est à dire indépendant de la taille du réseau. En outre, l'un des algorithmes présentés est instantanément stabilisant. Enfin, nous avons présenté une technique générale pour réduire systématiquement le coût des communications, en garantissant un délai de retransmission borné, et nous avons donné un cadre général ainsi que des outils d'implantation pour écrire des algorithmes auto-stabilisants dans ce contexte.
- Published
- 2000
11. Efficient Self-stabilization
- Author
-
Tixeuil, Sébastien, Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Université Paris Sud - Paris XI, and Joffroy Beauquier(jb@lri.fr)
- Subjects
[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] ,Distributed Systems ,Algorithmique répartie ,Fault Tolerance ,Auto-stabilisation ,Systèmes répartis ,Tolérance aux pannes ,Self-stabilization ,Distributed Algorithms - Abstract
When a distributed system is subject to transient failures that arbitrarily modify its state, it is crucial to recover a correct behavior within finite time. Self-stabilization offers such a guarantee, but usually uses large resources. In this thesis, we focus on minimizing these resources when such solutions exist.We introduced the concept of transient failure detectors, oracles that are called by processors, which notify if transient failures occurred within constant time. Our implementation enables classifying classic problems according to the specific resources dedicated to error detection.A natural extension was to show that a local property on the local code executed by each processor is sufficient to guarantee self-stabilization of the whole system, whatever the computation assumptions and communication graph may be. Since the original algorithm is not modified, it is overhead-free. Similarly, we developed two synchronizers that enable dynamic tasks to be solved self-stabilizingly, whose memory overhead is constant. Moreover, one of them is snap-stabilizing. Finally, we presented a general technique to systematically reduce the communicationcost, assuming a bounded retransmission delay, and we gave a general framework and tools to design self-stabilizing algorithms in this context.; Quand un système réparti est sujet à des défaillances transitoires qui modifient arbitrairement son état, il est crucial de pouvoir retrouver un comportement correct au bout d'un temps fini. L'auto-stabilisation présente une telle garantie, mais en général au prix de ressources importantes. Dans cette thèse, notre démarche a consisté à minimiser ces ressources lorsque cela était possible. Nous avons développé le concept de détecteur de défaillances transitoires, des oracles appelés par les processeurs du système, qui indiquent si des défaillances transitoires sont survenues, en un temps constant. Notre implantation permet de classifier les problèmes classiques suivant les ressources spécifiques nécessaires à la détection d'une erreur. Pour les tâches statiques, une suite naturelle a été de montrer qu'une condition sur le code localement exécuté par chaque processeur pouvait être suffisante pour garantir l'auto-stabilisation du système tout entier, indépendamment des hypothèses d'exécution et de la topologie du graphe de communication. Du fait que l'algorithme n'est pas modifié, il est forcément sans surcoût. De manière duale, nous avons développé des outils de synchronisation permettant de construire des algorithmes auto-stabilisants pour des spécifications dynamiques avec un surcoût en mémoire constant, c'est à dire indépendant de la taille du réseau. En outre, l'un des algorithmes présentés est instantanément stabilisant. Enfin, nous avons présenté une technique générale pour réduire systématiquement le coût des communications, en garantissant un délai de retransmission borné, et nous avons donné un cadre général ainsi que des outils d'implantation pour écrire des algorithmes auto-stabilisants dans ce contexte.
- Published
- 2000
12. A New Self-Stabilizing Minimum Spanning Tree Construction with Loop-Free Property.
- Author
-
BLIN, LÉLIA, POTOP-BUTUCARU, MARIA, ROVEDAKIS, STÉPHANE, and TIXEUIL, SÉBASTIEN
- Subjects
SELF-stabilization (Computer science) ,SPANNING trees ,DISTRIBUTED computing ,DISTRIBUTED algorithms ,DATA recovery - Abstract
The minimum spanning tree (MST) construction is a classical problem in Distributed Computing for creating a globally minimized structure distributedly. Self-stabilization is versatile technique for forward recovery that permits to handle any kind of transient faults in a unified manner. The loop-free property provides interesting safety assurance in dynamic networks where edge-cost changes during operation of the protocol.We present a new self-stabilizing MST protocol that improves on previous known approaches in several ways. First, it makes fewer system hypotheses as the size of the network (or an upper bound on the size) need not be known to the participants. Secondly, it is loop-free in the sense that it guarantees that a spanning tree structure is always preserved while edge costs change dynamically and the protocol adjusts to a new MST. Finally, time complexity matches the best known results, while space complexity results show that this protocol is the most efficient to date. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
13. Weak vs. Self vs. Probabilistic Stabilization.
- Author
-
Devismes, Stéphane, Tixeuil, Sébastien, and Yamashita, Masafumi
- Subjects
- *
SELF-stabilization (Computer science) , *PROBABILISTIC number theory , *DISTRIBUTED algorithms , *COMPUTER software correctness , *PROBLEM solving - Abstract
Self-stabilization is a strong property, which guarantees that a distributed system always resumes a correct behavior starting from an arbitrary initial state. Since it is a strong property, some problems cannot have self-stabilizing solutions. Weaker guarantees hence have been later introduced to cope with impossibility results, e.g., probabilistic self-stabilization only guarantees probabilistic convergence to a correct behavior, and weak stabilization only guarantees the possibility of convergence. In this paper, we investigate the relative power of self, probabilistic, and weak stabilization, with respect to the set of problems that can be solved. Weak stabilization is by definition stronger than self-stabilization and probabilistic self-stabilization in that precise sense. We first show that weak stabilization allows to solve problems having no self-stabilizing solution. We then show that any finite state deterministic weak stabilizing algorithm to solve a problem under the strongly fair scheduler is always a probabilistic self-stabilizing algorithm to solve the same problem under the randomized scheduler. Unfortunately, this good property does not hold in general for infinite state algorithms. We however show that for some classes of infinite state algorithms, this property holds. These results hint at more practical use of weak stabilizing algorithms, as they are easier to design and prove their correctness than their self-stabilizing and probabilistic self-stabilizing counterparts. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
14. Quiescence of self-stabilizing gossiping among mobile agents in graphs
- Author
-
Masuzawa, Toshimitsu and Tixeuil, Sébastien
- Subjects
- *
SELF-stabilization (Computer science) , *DISTRIBUTED algorithms , *MOBILE agent systems , *GRAPH theory , *INFORMATION theory , *COMPUTER science - Abstract
Abstract: This paper considers gossiping among mobile agents in graphs: agents move on the graph and have to disseminate their initial information to every other agent. We focus on self-stabilizing solutions for the gossip problem, where agents may start from arbitrary locations in arbitrary states. Self-stabilization requires (some of the) participating agents to keep moving forever, hinting at maximizing the number of agents that could be allowed to stop moving eventually. This paper formalizes the self-stabilizing agent gossip problem, introduces the quiescence number (i.e., the maximum number of eventually stopping agents) of self-stabilizing solutions and investigates the quiescence number with respect to several assumptions related to agent anonymity, synchrony, link duplex capacity, and whiteboard capacity. [Copyright &y& Elsevier]
- Published
- 2010
- Full Text
- View/download PDF
15. Using model checking to formally verify rendezvous algorithms for robots with lights in Euclidean space.
- Author
-
Défago, Xavier, Heriban, Adam, Tixeuil, Sébastien, and Wada, Koichi
- Subjects
- *
MOBILE robots , *ROBOTS , *DISTRIBUTED algorithms , *ALGORITHMS , *ROBOT programming , *AUTONOMOUS robots , *SYNCHRONIC order - Abstract
The paper details the first successful attempt at using model checking techniques to verify the correctness of distributed algorithms for robots evolving in a continuous environment. The study focuses on the problem of rendezvous of two robots with lights. There exist many different rendezvous algorithms that aim at finding the minimal number of colors needed to solve rendezvous in various synchrony models (e.g. , FSYNC, SSYNC, ASYNC). While these rendezvous algorithms are typically very simple, their analysis and proof of correctness tend to be extremely complex, tedious, and error-prone as impossibility results are based on subtle interactions between the activation schedules of the robots. The paper presents a generic verification model that can be concretely expressed in available software model-checkers. In particular, we explain the subtle design decisions that allow to keep the search space finite and tractable, as well as prove several important theorems that support them. As a sanity check, we use the model to verify several known rendezvous algorithms in six different models of synchrony. In each case, we find that the results obtained from the model checker are consistent with the results known in the literature. The model checker outputs a counter-example execution in every case that is known to fail. In the course of developing and proving the validity of the model, we identified several fundamental theorems, including the ability for a well chosen algorithm and ASYNC scheduler to produce an emerging property of memory in a system of oblivious mobile robots, and why it is not a problem when robots executing the gathering algorithms are equipped with lights. [Display omitted] • We describe a model to verify mobile robot gathering algorithms that evolve in a Euclidean continuous space. • We show that positive results obtained for the model extend to the initial system model. • We model check all known mobile robot gathering algorithms and verify previous pen-and-paper results. • We obtain new insights about key system hypotheses about problem solvability. • We introduce weaker models of consistency (inspired by regular registers). • We derive a new algorithm that solves mobile robot gathering in such a model. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
16. Gathering fat mobile robots with slim omnidirectional cameras.
- Author
-
Honorat, Anthony, Potop-Butucaru, Maria, and Tixeuil, Sébastien
- Subjects
- *
MOBILE robots , *OMNIRANGE system , *INFORMATION asymmetry , *CAMERAS , *DISTRIBUTED computing , *COMPUTER algorithms - Abstract
Most distributed solutions for swarms of oblivious mobile robots consider that individual robots are represented by points that can overlap, which is physically impossible. A recent trend is to consider “fat” robots, i.e. robots that are represented by unit discs and cannot overlap, but still assume that robots can be seen if there exists a point in the unit disc that has a line of sight with the target robot. Again, this does not match practical sensing devices implementations. We propose a new model for sensing devices that originates from embedded omnidirectional cameras, sonars, or lasers found on real robots. This model opens new algorithmic issues since the visibility relation becomes asymmetric. As a case study, we consider the gathering problem for four volumic robots and provide an algorithm to solve the problem in the fully asynchronous setting in our extended model. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
17. Self-adjusting Linear Networks
- Author
-
Avin, Chen, van Duijn, Ingo, Schmid, Stefan, 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
18. Dynamic FTSS in asynchronous systems: The case of unison
- Author
-
Dubois, Swan, Potop-Butucaru, Maria, and Tixeuil, Sébastien
- Subjects
- *
FAULT tolerance (Engineering) , *SELF-stabilization (Computer science) , *NUMBER theory , *SYNCHRONIZATION , *DISTRIBUTED algorithms , *COMPUTER simulation - Abstract
Abstract: Distributed fault-tolerance can mask the effect of a limited number of permanent faults, while self-stabilization provides forward recovery after an arbitrary number of transient faults hit the system. FTSS (Fault-Tolerant Self-Stabilizing) protocols combine the best of both worlds since they tolerate simultaneously transient and (permanent) crash faults. To date, deterministic FTSS solutions either consider static (i.e. fixed point) tasks, or assume synchronous scheduling of the system components. In this paper, we present the first study of deterministic FTSS solutions for dynamic tasks in asynchronous systems, considering the unison problem as a benchmark. Unison can be seen as a local clock synchronization problem as neighbors must maintain digital clocks at most one time unit away from each other, and increment their own clock value infinitely often. We present several impossibility results for this difficult problem and propose an FTSS solution (when the problem is solvable) for the state model that exhibits optimal fault-containment. [Copyright &y& Elsevier]
- Published
- 2011
- Full Text
- View/download PDF
19. Optimal Byzantine-resilient convergence in uni-dimensional robot networks
- Author
-
Bouzid, Zohir, Potop-Butucaru, Maria Gradinariu, and Tixeuil, Sébastien
- Subjects
- *
STOCHASTIC convergence , *ROBOTS , *COMPUTER networks , *COORDINATES , *FAULT tolerance (Engineering) , *DISTRIBUTED algorithms , *SELF-stabilization (Computer science) - Abstract
Abstract: Given a set of robots with arbitrary initial location and no agreement on a global coordinate system, convergence requires that all robots asymptotically approach the exact same, but unknown beforehand, location. Robots are oblivious–they do not recall the past computations–and are allowed to move in a one-dimensional space. Additionally, robots cannot communicate directly, instead they obtain system related information only via visual sensors. Even though convergence and the classical distributed approximate agreement problem (that requires correct processes to decide, for some constant , values distance apart and within the range of initial proposed values) are similar, we provide evidence that solving convergence in robot networks requires specific assumptions about synchrony and Byzantine resilience. In more detail, we prove necessary and sufficient conditions for the convergence of mobile robots despite a subset of them being Byzantine (i.e. they can exhibit arbitrary behavior). Additionally, we propose two deterministic convergence algorithms for robot networks and analyze their correctness and complexity in various atomicity and synchrony settings. The first algorithm tolerates Byzantine robots for -sized robot networks in fully synchronous ATOM networks, while the second proposed algorithm tolerates Byzantine robots for -sized robot networks in non-atomic CORDA networks. The resilience of these two algorithms is proved to be optimal. [Copyright &y& Elsevier]
- Published
- 2010
- Full Text
- View/download PDF
20. On asynchronous rendezvous in general graphs.
- Author
-
Bampas, Evangelos, Blin, Lélia, Czyzowicz, Jurek, Ilcinkas, David, Labourel, Arnaud, Potop-Butucaru, Maria, and Tixeuil, Sébastien
- Subjects
- *
GRAPH theory , *ASYNCHRONOUS learning , *POLYNOMIAL time algorithms , *COMPUTER algorithms , *MOBILE agent systems - Abstract
Abstract A pair of agents (robots) are moving in a graph with the goal of meeting at the same node or while traversing the same edge. An asynchronous adversary knows the prescribed walks of the two agents and is in complete control of the speed of each agent during its walk. We provide a complete characterization of pairs of walks that enforce rendezvous against an asynchronous adversary after traversing a given number of edges. The characterization is efficient in that it can be checked in polynomial time. We argue that the certificate of rendezvous enforcement that is produced by the checking algorithm contains a wealth of information on why rendezvous is enforced. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
21. Evaluating and optimizing stabilizing dining philosophers.
- Author
-
Adamek, Jordan, Farina, Giovanni, Nesterenko, Mikhail, and Tixeuil, Sébastien
- Subjects
- *
SELF-stabilization (Computer science) , *COMPUTER algorithms , *MATHEMATICAL optimization , *FAULT-tolerant computing , *SIMULATION methods & models - Abstract
We study theoretical and practical aspects of five of the most well-known self-stabilizing dining philosophers algorithms. We theoretically prove that three of them are incorrect. For practical evaluation, we simulate these five algorithms as well as two classic non-self-stabilizing algorithms and evaluate their fault-tolerance, latency and throughput of critical section access. We present a new combined algorithm that achieves the best throughput of the two remaining correct self-stabilizing algorithms by determining the system load and switching between these basic algorithms. We prove the combined algorithm correct, simulate it and study its performance characteristics. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
22. Optimal Deterministic Remote Clock Estimation in Real-Time Systems
- Author
-
Moser, Heinrich, Schmid, Ulrich, 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, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Baker, Theodore P., editor, Bui, Alain, editor, and Tixeuil, Sébastien, editor
- Published
- 2008
- Full Text
- View/download PDF
23. Bounds for Deterministic Reliable Geocast in Mobile Ad-Hoc Networks
- Author
-
Fernández Anta, Antonio, Milani, Alessia, 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, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Baker, Theodore P., editor, Bui, Alain, editor, and Tixeuil, Sébastien, editor
- Published
- 2008
- Full Text
- View/download PDF
24. Distributed Synthesis of Fault-Tolerant Programs in the High Atomicity Model
- Author
-
Bonakdarpour, Borzoo, Kulkarni, Sandeep S., Abujarad, Fuad, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Masuzawa, Toshimitsu, editor, and Tixeuil, Sébastien, editor
- Published
- 2007
- Full Text
- View/download PDF
25. Towards Automatic Convergence Verification of Self-stabilizing Algorithms
- Author
-
Oehlerking, Jens, Dhama, Abhishek, Theel, Oliver, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Tixeuil, Sébastien, editor, and Herman, Ted, editor
- Published
- 2005
- Full Text
- View/download PDF
26. Uniform Bipartition in the Population Protocol Model with Arbitrary Communication Graphs
- Author
-
Yasumi, Hiroto, Ooshita, Fukuhito, Inoue, Michiko, Tixeuil, S��bastien, Tixeuil, Sébastien, Nara Institute of Science and Technology - Graduate School of Information Science (NAIST), Nara Institute of Science and Technology, Networks and Performance Analysis (NPA), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Laboratory of Information, Network and Communication Sciences (LINCS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT)-Sorbonne Université (SU), and ANR-19-CE25-0005,SAPPORO,Sûreté et preuve de protocoles adaptatifs pour robots oublieux(2019)
- Subjects
FOS: Computer and information sciences ,[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,distributed protocol ,[INFO] Computer Science [cs] ,uniform bipartition ,population protocol ,[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] ,Computer Science - Distributed, Parallel, and Cluster Computing ,Theory of computation → Concurrent algorithms ,[INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,Distributed algorithms ,[INFO]Computer Science [cs] ,Distributed, Parallel, and Cluster Computing (cs.DC) ,Theory of computation → Distributed algorithms ,Concurrent algorithms phrases population protocol ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
In this paper, we focus on the uniform bipartition problem in the population protocol model. This problem aims to divide a population into two groups of equal size. In particular, we consider the problem in the context of arbitrary communication graphs. As a result, we investigate the solvability of the uniform bipartition problem with arbitrary communication graphs when agents in the population have designated initial states, under various assumptions such as the existence of a base station, symmetry of the protocol, and fairness of the execution. When the problem is solvable, we present protocols for uniform bipartition. When global fairness is assumed, the space complexity of our solutions is tight., LIPIcs, Vol. 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020), pages 33:1-33:16
- Published
- 2020
27. Self-stabilizing Algorithms
- Author
-
Sébastien Tixeuil, Networks and Performance Analysis (NPA), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), and Tixeuil, Sébastien
- Subjects
Computer science ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,Self-stabilization ,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] ,[INFO.INFO-PF] Computer Science [cs]/Performance [cs.PF] ,0202 electrical engineering, electronic engineering, information engineering ,[INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,Final version ,[INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI] ,Group (mathematics) ,business.industry ,Fault tolerance ,Data structure ,Distributed Algorithms ,Fault-tolerance ,[INFO.INFO-PF]Computer Science [cs]/Performance [cs.PF] ,010201 computation theory & mathematics ,Distributed algorithm ,Theory of computation ,020201 artificial intelligence & image processing ,Artificial intelligence ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,business ,Algorithm - Abstract
50 pages; The final version of this book chapter appears in: Sébastien Tixeuil. Algorithms and Theory of Computation Handbook, Second Edition, chapter Self-stabilizing Algorithms, pages 26.1–26.45. Chapman & Hall/CRC Applied Algorithms and Data Structures. CRC Press, Taylor & Francis Group, November 2009.
- Published
- 2009
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.