46 results on '"Tixeuil, Sébastien"'
Search Results
2. Realistic Self-Stabilization (Invited Talk)
- Author
-
Tixeuil, Sébastien
- Subjects
Computing methodologies → Distributed algorithms ,Theory of computation → Distributed computing models ,Networks → Mobile networks ,Performance evaluation ,Probable stabilization ,Computer systems organization → Dependable and fault-tolerant systems and networks ,Asynchronous message passing ,Multi-tolerance ,Theory of computation → Distributed algorithms ,Security and privacy → Distributed systems security ,Distributed systems ,Self-stabilization - Abstract
It is almost fifty years since Dijkstra coined the term "self-stabilization" to denote a distributed system able to recover correct behavior starting from any arbitrary (even unreachable) configuration. His seminal paper triggered many works since then, exploring over the years new variants of the original concept, new application domains, and new complexity results. While the huge majority of those contributions relates to theory, considering computability and worst case complexity issues, this talk revisits old and recent contributions from the prism of "realistic" distributed systems, aiming to address the following question: is self-stabilization relevant in practice for distributed systems?, LIPIcs, Vol. 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022), pages 3:1-3:1
- Published
- 2023
- Full Text
- View/download PDF
3. Realistic Self-stabilization
- Author
-
Tixeuil, Sébastien, 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), and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT)-Sorbonne Université (SU)
- Subjects
distributed systems ,safety ,self-stabilization ,[INFO]Computer Science [cs] ,performance ,fault-tolerance - Abstract
International audience; It is almost fifty years since Dijkstra coined the term "self-stabilization" to denote a distributed system able to recover correct behavior starting from any arbitrary (even unreachable) configuration. His seminal paper triggered many works since then, exploring over the years new variants of the original concept, new application domains, and new complexity results. While the huge majority of those contributions relates to theory, considering computability and worst case complexity issues, this talk revisits old and recent contributions from the prism of ``realistic'' distributed systems, aiming to address the following question: is self-stabilization relevant in practice for distributed systems?
- Published
- 2022
4. Monotonic Stabilization
- Author
-
Yamauchi, Yukiko, 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, 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, Lu, Chenyang, editor, Masuzawa, Toshimitsu, editor, and Mosbah, Mohamed, editor
- Published
- 2010
- Full Text
- View/download PDF
5. A Self-stabilizing Link-Coloring Protocol Resilient to Unbounded Byzantine Faults in Arbitrary Networks
- Author
-
Masuzawa, Toshimitsu, 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, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Dough, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Anderson, James H., editor, Prencipe, Giuseppe, editor, and Wattenhofer, Roger, editor
- Published
- 2006
- Full Text
- View/download PDF
6. Maximum Metric Spanning Tree Made Byzantine Tolerant
- Author
-
Dubois, Swan, Masuzawa, Toshimitsu, and Tixeuil, Sébastien
- Published
- 2015
- Full Text
- View/download PDF
7. Stabilizing Inter-domain Routing in the Internet
- Author
-
Chen, Yu, Datta, Ajoy K., Tixeuil, Sébastien, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Monien, Burkhard, editor, and Feldmann, Rainer, editor
- Published
- 2002
- Full Text
- View/download PDF
8. A self-stabilizing 3-approximation for the maximum leaf spanning tree problem in arbitrary networks
- Author
-
Kamei, Sayaka, Kakugawa, Hirotsugu, Devismes, Stéphane, and Tixeuil, Sébastien
- Published
- 2013
- Full Text
- View/download PDF
9. Ascending Runs in Dependent Uniformly Distributed Random Variables: Application to Wireless Networks
- Author
-
Mitton, Nathalie, Paroux, Katy, Sericola, Bruno, and Tixeuil, Sébastien
- Published
- 2010
- Full Text
- View/download PDF
10. Transient fault detectors
- Author
-
Beauquier, Joffroy, Delaët, Sylvie, Dolev, Shlomi, and Tixeuil, Sébastien
- Published
- 2007
- Full Text
- View/download PDF
11. Secure and self-stabilizing clock synchronization in sensor networks
- Author
-
Hoepman, Jaap-Henk, Larsson, Andreas, Schiller, Elad M., Tsigas, Philippas, Masuzawa, Toshimitsu, Tixeuil, Sébastien, Masuzawa, Toshimitsu, and Tixeuil, Sébastien
- Subjects
General Computer Science ,Secure and resilient computer systems ,Computer science ,Clock-synchronization ,Real-time computing ,Self-stabilization ,Adversary ,Clock synchronization ,Theoretical Computer Science ,Nondeterministic algorithm ,Sampling (signal processing) ,Bounded function ,State (computer science) ,Sensor-network systems ,Digital Security ,Lect. Notes Comp. Sci. " 4838" ,Wireless sensor network ,GeneralLiterature_REFERENCE(e.g.,dictionaries,encyclopedias,glossaries) ,Security of Systems ,Computer Science::Cryptography and Security ,Self-Stabilization ,Computer Science(all) - Abstract
In sensor networks, correct clocks have arbitrary starting offsets and nondeterministic fluctuating skews. We consider an adversary that aims at tampering with the clock synchronization by intercepting messages, replaying intercepted messages (after the adversary’s choice of delay), and capturing nodes (i.e., revealing their secret keys and impersonating them). We present an efficient clock sampling algorithm which tolerates attacks by this adversary, collisions, a bounded amount of losses due to ambient noise, and a bounded number of captured nodes that can jam, intercept, and send fake messages. The algorithm is self-stabilizing, so if these bounds are temporarily violated, the system can efficiently stabilize back to a correct state. Using this clock sampling algorithm, we construct the first self-stabilizing algorithm for secure clock synchronization in sensor networks that is resilient to the aforementioned adversarial attacks.
- Published
- 2011
- Full Text
- View/download PDF
12. Self-stabilizing Vertex Coloring of Arbitrary Graphs
- Author
-
Gradinariu, Maria, Tixeuil, Sébastien, Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), and Tixeuil, Sébastien
- Subjects
distributed algorithm ,[INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI] ,arbitrary graph ,acyclic orientation ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,Vertex coloring ,maximal independent set ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,randomized algorithm ,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM] ,[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] ,self-stabilization ,[INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] - Abstract
International audience; A self-stabilizing algorithm, regardless of the initial system state, converges in finite time to a set of states that satisfy a legitimacy predicate without the need for explicit exception handler of backward recovery. The vertex coloration problem consists in ensuring that every node in the system has a color that is different from any of its neighbors. We provide three self-stabilizing solutions to the vertex coloration problem under unfair scheduling that are based on a greedy technique. We use at most $B+1$ different colors (in complete graphs), where $B$ is the graph degree, and ensure stabilization within $O(n\times B)$ processor atomic steps. Two of our algorithms deal with uniform networks where nodes do not have identifiers. Our solutions lead to directed acyclic orientation and maximal independent set construction at no additional cost.
- Published
- 2000
13. 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
14. Self-Stabilization, Byzantine Containment, and Maximizable Metrics: Necessary Conditions
- Author
-
Dubois, Swan, Masuzawa, Toshimitsu, 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), Department of Information and Computer Sciences [Toyonaka], Osaka University, 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), and Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)
- Subjects
Maximum Metric Tree ,Byzantine Containment ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,Computer Science::Distributed, Parallel, and Cluster Computing ,Self-stabilization - Abstract
Self-stabilization is a versatile approach to fault-tolerance since it permits a distributed system to recover from any transient fault that arbitrarily corrupts the contents of all memories in the system. Byzantine tolerance is an attractive feature of distributed systems that permits to cope with arbitrary malicious behaviors. We consider the well known problem of constructing a maximum metric tree in this context. Combining these two properties leads to some impossibility results. In this paper, we provide two necessary conditions to construct maximum metric tree in presence of transients and (permanent) Byzantine faults.
- Published
- 2011
15. Dynamic FTSS in Asynchronous Systems: the Case of Unison
- Author
-
Dubois, Swan, Potop-Butucaru, Maria, 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), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), Networks and Performance Analysis (NPA), and 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)
- Subjects
[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] ,Distributed algorithm ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,Unison ,fault tolerant self-stabilization ,Distributed systems ,ACM: F.: Theory of Computation ,Self-stabilization - 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 fault hit the system. FTSS protocols combine the best of both worlds since they are simultaneously fault-tolerant and self-stabilizing. To date, 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 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 many impossibility results for this difficult problem and propose a FTSS solution when the problem is solvable that exhibits optimal fault containment.
- Published
- 2009
16. Stabilizing Maximal Independent Set in Unidirectional Networks is Hard
- Author
-
Masuzawa, Toshimitsu, Tixeuil, Sébastien, Department of Information and Computer Sciences [Toyonaka], Osaka University, Global parallel and distributed computing (GRAND-LARGE), Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Paris-Sud - Paris 11 (UP11)-Laboratoire d'Informatique Fondamentale de Lille (LIFL), Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Laboratoire de Recherche en Informatique (LRI), CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec, Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), SAKURA, INRIA, 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 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Laboratoire d'Informatique Fondamentale de Lille (LIFL), Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria), Networks and Performance Analysis (NPA), and 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)
- Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,Distributed algorithm ,ACM: D.: Software/D.1: PROGRAMMING TECHNIQUES/D.1.3: Concurrent Programming/D.1.3.0: Distributed programming ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,Maximal Independent Set ,Distributed systems ,ACM: D.: Software/D.4: OPERATING SYSTEMS/D.4.5: Reliability/D.4.5.2: Fault-tolerance ,Unidirectional Networks ,ACM: F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY/F.2.3: Tradeoffs between Complexity Measures ,[INFO.INFO-PF]Computer Science [cs]/Performance [cs.PF] ,[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] ,Probabilistic self-stabilization ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,Self-stabilization - Abstract
A distributed algorithm is self-stabilizing if after faults and attacks hit the system and place it in some arbitrary global state, the system recovers from this catastrophic situation without external intervention in finite time. In this paper, we consider the problem of constructing self-stabilizingly a \emph{maximal independent set} in uniform unidirectional networks of arbitrary shape. On the negative side, we present evidence that in uniform networks, \emph{deterministic} self-stabilization of this problem is \emph{impossible}. Also, the \emph{silence} property (\emph{i.e.} having communication fixed from some point in every execution) is impossible to guarantee, either for deterministic or for probabilistic variants of protocols. On the positive side, we present a deterministic protocol for networks with arbitrary unidirectional networks with unique identifiers that exhibits polynomial space and time complexity in asynchronous scheduling. We complement the study with probabilistic protocols for the uniform case: the first probabilistic protocol requires infinite memory but copes with asynchronous scheduling, while the second probabilistic protocol has polynomial space complexity but can only handle synchronous scheduling. Both probabilistic solutions have expected polynomial time complexity.
- Published
- 2009
17. Ascending runs in dependent uniformly distributed random variables: Application to wireless networks
- Author
-
Mitton, Nathalie, Paroux, Katy, Sericola, Bruno, Tixeuil, Sébastien, System and Networking for Portable Objects Proved to be Safe (POPS), Laboratoire d'Informatique Fondamentale de Lille (LIFL), Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-IRCICA, Laboratoire de Mathématiques de Besançon (UMR 6623) (LMB), Université de Bourgogne (UB)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Centre National de la Recherche Scientifique (CNRS), Dependability Interoperability and perfOrmance aNalYsiS Of networkS (DIONYSOS), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-RÉSEAUX, TÉLÉCOMMUNICATION ET SERVICES (IRISA-D2), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-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)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-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), Global parallel and distributed computing (GRAND-LARGE), Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Paris-Sud - Paris 11 (UP11)-Laboratoire d'Informatique Fondamentale de Lille (LIFL), Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec, INRIA, Institut National de Recherche en Informatique et en Automatique (Inria), Centre National de la Recherche Scientifique (CNRS)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC), 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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), 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 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Laboratoire d'Informatique Fondamentale de Lille (LIFL), Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, 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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), 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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), 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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)
- Subjects
[MATH.MATH-PR]Mathematics [math]/Probability [math.PR] ,ACM: G.: Mathematics of Computing/G.3: PROBABILITY AND STATISTICS ,[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] ,self-stabilization ,Markov chains ,convergence time ,ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS ,maximal ascending run ,[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,ACM: C.: Computer Systems Organization/C.2: COMPUTER-COMMUNICATION NETWORKS - Abstract
We analyze in this paper the longest increasing contiguous sequence or maximal ascending run of random variables with common uniform distribution but not independent. Their dependence is characterized by the fact that two successive random variables cannot take the same value. Using a Markov chain approach, we study the distribution of the maximal ascending run and we develop an algorithm to compute it. This problem comes from the analysis of several self organizing protocols designed for large scale wireless sensor networks, and we show how our results apply to this domain.
- Published
- 2008
18. 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
19. 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
20. 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
21. 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
22. 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
23. Stabilizing inter-domain routing in the Internet.
- Author
-
Johnen, Colette, Gouda, Mohamed G., Chen, Yu, Datta, Ajoy K., and Tixeuil, Sébastien
- Subjects
SELF-stabilization (Computer science) ,BGP (Computer network protocol) ,INTERNET ,NETWORK routers ,COMPUTER network protocols ,COMPUTER networks - Abstract
This paper reports the first self-stabilizing Border Gateway Protocol (BGP). BGP is the standard inter-domain routing protocol in the Internet. Self-stabilization is a technique to tolerate arbitrary transient faults. The routing instability in the Internet can occur due to errors in configuring the routing data structures, the routing policies, transient physical and data link problems, software bugs, and memory corruption. This instability can increase the network latency, slow down the convergence of the routing data structures, and can also cause the partitioning of networks. Most of the previous studies concentrated on routing policies to achieve the convergence of BGP while the oscillations due to transient faults were ignored. The purpose of self-stabilizing BGP is to solve the routing instability problem when this instability results from transient failures. The self-stabilizing BGP presented here provides a way to detect and automatically recover from this type of faults. Our protocol is combined with an existing protocol to make it resilient to policy conflicts as well. [ABSTRACT FROM AUTHOR]
- Published
- 2005
24. Tolerating Transient and Intermittent Failures
- Author
-
Delaët, Sylvie and Tixeuil, Sébastien
- Subjects
- *
FAULT-tolerant computing , *DISTRIBUTED computing - Abstract
Fault tolerance is a crucial property for recent distributed systems. We propose an algorithm that solves the census problem (list all processor identifiers and their relative distance) on an arbitrary strongly connected network.This algorithm tolerates transient faults that corrupt the processors and communication links memory (it is self-stabilizing) as well as intermittent faults (fair loss, reorder, finite duplication of messages) on communication media. A formal proof establishes its correctness for the considered problem. Our algorithm leads to the construction of algorithms for any silent problems that are self-stabilizing while supporting the same communication hazards. [Copyright &y& Elsevier]
- Published
- 2002
- Full Text
- View/download PDF
25. Brief Announcement: Analysis of a Memory-Efficient Self-stabilizing BFS Spanning Tree Construction
- Author
-
Datta, Ajoy K., Devismes, Stéphane, Johnen, Colette, Larmore, Lawrence L., 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
26. Brief Announcement: Self-stabilizing Construction of a Minimal Weakly -Reachable Directed Acyclic Graph
- Author
-
Nakamura, Junya, Shibata, Masahiro, Sudo, Yuichi, Kim, Yonghwan, 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
27. 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
28. Brief Announcement: Self-stabilizing LCM Schedulers for Autonomous Mobile Robots Using Neighborhood Mutual Remainder
- Author
-
Dolev, Shlomi, Kamei, Sayaka, Katayama, Yoshiaki, Ooshita, Fukuhito, Wada, Koichi, 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
29. 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
30. 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
31. 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
32. A Self-stabilizing Approximation for the Minimum Connected Dominating Set with Safe Convergence
- Author
-
Kamei, Sayaka, Kakugawa, Hirotsugu, 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
33. Snap-Stabilizing Prefix Tree for Peer-to-Peer Systems
- Author
-
Caron, Eddy, Desprez, Frédéric, Petit, Franck, Tedeschi, Cédric, 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
34. Secure and Self-stabilizing Clock Synchronization in Sensor Networks
- Author
-
Hoepman, Jaap-Henk, Larsson, Andreas, Schiller, Elad M., Tsigas, Philippas, 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
35. The Truth System: Can a System of Lying Processes Stabilize?
- Author
-
Gouda, Mohamed G., Li, Yan, 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
36. Stabilizing Trust and Reputation for Self-Stabilizing Efficient Hosts in Spite of Byzantine Guests (Extended Abstract)
- Author
-
Dolev, Shlomi, Yagel, Reuven, 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
37. Stabilization of Flood Sequencing Protocols in Sensor Networks
- Author
-
Choi, Young-ri, Gouda, Mohamed G., 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
38. Self-stabilizing Mobile Node Location Management and Message Routing
- Author
-
Dolev, Shlomi, Lahiani, Limor, Lynch, Nancy, Nolte, Tina, 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
39. Snap-Stabilizing Optimal Binary Search Tree
- Author
-
Bein, Doina, Datta, Ajoy K., Villain, Vincent, 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
40. 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
41. Practically stabilizing SWMR atomic memory in message-passing systems.
- Author
-
Alon, Noga, Attiya, Hagit, Dolev, Shlomi, Dubois, Swan, Potop-Butucaru, Maria, and Tixeuil, Sébastien
- Subjects
- *
MESSAGE passing (Computer science) , *FAULT-tolerant computing , *COMPUTER simulation , *SCHEME programming language , *MATHEMATICAL bounds - Abstract
A fault-tolerant and practically stabilizing simulation of an atomic register is presented. The simulation works in asynchronous message-passing systems, and allows a minority of processes to crash. The simulation stabilizes in a practically stabilizing manner, by reaching a long execution in which it runs correctly. A key element in the simulation is a new combinatorial construction of a bounded labeling scheme accommodating arbitrary labels, including those not generated by the scheme itself. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
42. Fault Tolerant Network Constructors
- Author
-
Othon Michail, Paul G. Spirakis, Michail Theofilatos, Ghaffari, Mohsen, Nesterenko, Mikhail, Tixeuil, Sébastien, Tucci, Sara, and Yamauchi, Yukiko
- Subjects
FOS: Computer and information sciences ,Self-organization ,Discrete mathematics ,education.field_of_study ,Logarithm ,Computer science ,Open problem ,Population ,Crash ,Self-stabilization ,Von Neumann universal constructor ,Upper and lower bounds ,Computer Science Applications ,Theoretical Computer Science ,symbols.namesake ,Computer Science - Distributed, Parallel, and Cluster Computing ,Computational Theory and Mathematics ,symbols ,Distributed, Parallel, and Cluster Computing (cs.DC) ,education ,Information Systems - Abstract
In this work, we consider adversarial crash faults of nodes in the network constructors model $[$Michail and Spirakis, 2016$]$. We first show that, without further assumptions, the class of graph languages that can be (stably) constructed under crash faults is non-empty but small. In particular, if an unbounded number of crash faults may occur, we prove that (i) the only constructible graph language is that of spanning cliques and (ii) a strong impossibility result holds even if the size of the graphs that the protocol outputs in populations of size $n$ need only grow with $n$ (the remaining nodes being waste). When there is a finite upper bound $f$ on the number of faults, we show that it is impossible to construct any non-hereditary graph language. On the positive side, by relaxing our requirements we prove that: (i) permitting linear waste enables to construct on $n/(2f)-f$ nodes, any graph language that is constructible in the fault-free case, (ii) partial constructibility (i.e. not having to generate all graphs in the language) allows the construction of a large class of graph languages. We then extend the original model with a minimal form of fault notifications. Our main result here is a fault-tolerant universal constructor: We develop a fault-tolerant protocol for spanning line and use it to simulate a linear-space Turing Machine $M$. This allows a fault-tolerant construction of any graph accepted by $M$ in linear space, with waste $min\{n/2+f(n),\; n\}$, where $f(n)$ is the number of faults in the execution. We then prove that increasing the permissible waste to $min\{2n/3+f(n),\; n\}$ allows the construction of graphs accepted by an $O(n^2)$-space Turing Machine, which is asymptotically the maximum simulation space that we can hope for in this model. Finally, we show that logarithmic local memories can be exploited for a no-waste fault-tolerant simulation of any such protocol.
- Published
- 2019
43. Self-stabilizing byzantine asynchronous unison
- Author
-
Dubois, Swan, Potop-Butucaru, Maria, Nesterenko, Mikhail, and Tixeuil, Sébastien
- Subjects
- *
COMPUTER storage devices , *COMPUTER scheduling , *COMPUTER algorithms , *UNISON Author Language (Computer program language) , *TOPOLOGY , *COMPUTER networks - Abstract
Abstract: We explore asynchronous unison in the presence of systemic transient and permanent Byzantine faults in shared memory. We observe that the problem is not solvable under a less than strongly fair scheduler or for system topologies with maximum node degree greater than two. We present then a self-stabilizing Byzantine-tolerant solution to asynchronous unison for chain and ring topologies under the central strongly fair daemon. Our algorithm has minimum possible containment radius and optimal stabilization time. [Copyright &y& Elsevier]
- Published
- 2012
- Full Text
- View/download PDF
44. Snap-stabilization in message-passing systems
- Author
-
Delaët, Sylvie, Devismes, Stéphane, Nesterenko, Mikhail, and Tixeuil, Sébastien
- Subjects
- *
EMAIL systems , *COMPUTER network protocols , *FAULT tolerance (Engineering) , *INFORMATION processing , *MESSAGE theory (Communication) , *FEEDBACK control systems - Abstract
Abstract: In this paper, we tackle the problem of snap-stabilization in message-passing systems. Snap-stabilization allows designing protocols that withstand transient faults: indeed, any computation that is started after faults cease immediately satisfies the expected specification. Our contribution is twofold: we demonstrate that in message-passing systems (i) snap-stabilization is impossible for nontrivial problems if channels are of finite yet unbounded capacity, and (ii) snap-stabilization becomes possible in the same setting with bounded capacity channels. The latter contribution is constructive, as we propose two snap-stabilizing protocols for propagation of information with feedback and mutual exclusion. Our work opens exciting new research perspectives, as it enables the snap-stabilizing paradigm to be implemented in actual networks. [Copyright &y& Elsevier]
- Published
- 2010
- Full Text
- View/download PDF
45. Brief Announcement: Efficient Self-Stabilizing 1-Maximal Matching Algorithm for Arbitrary Networks
- Author
-
Fukuhito Ooshita, Michiko Inoue, Sébastien Tixeuil, Nara Institute of Science and Technology - Graduate School of Information Science (NAIST), Nara Institute of Science and Technology, 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), 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.), Laboratory of Information, Network and Communication Sciences (LINCS), Université Pierre et Marie Curie - Paris 6 (UPMC)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT), ANR-16-CE25-0009,ESTATE,Auto-stabilisation et amélioration de la sûreté dans les environnements distribués évoluant dans le temps(2016), Tixeuil, Sébastien, and 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
- Subjects
maximal matching ,Computer science ,Self-stabilization ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,ACM: D.: Software/D.4: OPERATING SYSTEMS/D.4.7: Organization and Design ,1-maximal matching ,020204 information systems ,0202 electrical engineering, electronic engineering, information engineering ,[INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,Blossom algorithm ,ACM: C.: Computer Systems Organization/C.2: COMPUTER-COMMUNICATION NETWORKS/C.2.4: Distributed Systems ,ACM: D.: Software/D.4: OPERATING SYSTEMS/D.4.8: Performance ,Node (networking) ,Locality ,ACM: D.: Software/D.4: OPERATING SYSTEMS/D.4.5: Reliability ,Identifier ,maximum matching ,self-stabilization ,010201 computation theory & mathematics ,arbitrary networks ,ACM: C.: Computer Systems Organization/C.2: COMPUTER-COMMUNICATION NETWORKS/C.2.2: Network Protocols ,Daemon ,unfair scheduler ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,Algorithm - Abstract
International audience; We present a new self-stabilizing 1-maximal matching algorithm that works under the distributed unfair daemon for arbitrarily shaped networks. The 1-maximal matching is a 2/3-approximation of a maximum matching, a significant improvement over the 1/2-approximation that is guaranteed by a maximal matching. Our algorithm is efficient (its stabilization time is $O(e)$ moves, where $e$ denotes the number of edges in the network). Besides, our algorithm is optimal with respect to identifiers locality (we assume node identifiers are distinct up to distance three, a necessary condition to withstand arbitrary networks). The proposed algorithm closes the complexity gap between two recent works: Inoue et al. presented a 1-maximal matching algorithm that is $O(e)$ moves but requires the network topology not to contain a cycle of size of multiple of three ; Cohen et al. consider arbitrary topology networks but requires $O(n^3)$ moves to stabilize (where $n$ denotes the number of nodes in the network). Our solution preserves the better complexity of $O(e)$ moves, yet considers arbitrary networks, demonstrating that previous restrictions were unnecessary to preserve complexity results.
- Published
- 2017
46. 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.