logo EDITE Sébastien TIXEUIL
Identité
Sébastien TIXEUIL
État académique
Thèse soutenue le 2000-01-14
Titulaire d'une HDR (ou équivalent) 2006-05-22
Laboratoire: personnel permanent
Direction de thèses (depuis 2007)
3
Propositions de sujets de thèse
Voisinage
Ellipse bleue: doctorant, ellipse jaune: docteur, rectangle vert: permanent, rectangle jaune: HDR. Trait vert: encadrant de thèse, trait bleu: directeur de thèse, pointillé: jury d'évaluation à mi-parcours ou jury de thèse.
Productions scientifiques
http://www.springerlink.com/content/h3722w81502947k4/ http://www.springerlink.com/content/h3722w81502947k4/fulltext.pdf
A Self-Stabilizing 3-Approximation for the Maximum Leaf Spanning Tree Problem in Arbitrary Networks
The maximum leaf spanning tree (MLST) is a good candidate for constructing a virtual backbone in self-organized multihop wireless networks, but is practically intractable (NP-complete). Self-stabilization is a general technique that permits to recover from catastrophic transient failures in self-organized networks without human intervention. We propose a fully distributed self-stabilizing approximation algorithm for the MLST problem on arbitrary topology networks. Our algorithm is the first self-stabilizing protocol that is specifically designed for the construction of an MLST. It improves over previous self-stabilizing solutions both for generality (arbitrary topology graphs vs. unit disk graphs or generalized unit disk graphs, respectively) and for approximation ratio, as it guarantees the number of its leaves is at least 1/3 of the maximum one. The time complexity of our algorithm is O(n2) rounds.
2011
edite:1332792336107
Asynchronous exclusive perpetual grid exploration without sense of direction
In this paper, we investigate the exclusive perpetual exploration of grid shaped networks using anonymous, oblivious and fully asynchronous robots. Our results hold for robots without sense of direction i.e. they do not agree on a common North, nor do they agree on a common left and right ; furthermore, the "North" and "left" of each robot is decided by an adversary that schedules robots for execution, and may change between invocations of particular robots). We focus on the minimal number of robots that are necessary and sufficient to solve the problem in general grids. %X In more details, we prove that three deterministic robots are necessary and sufficient, provided that the size of the grid is n*m with 3<=n<=m or n=2 and m>=4. Perhaps surprisingly, and unlike results for the exploration with stop problem (where grids are "easier" to explore and stop than rings with respect to the number of robots), exclusive perpetual exploration requires as many robots in the ring and in the grid. %X Furthermore, we propose a classification of configurations such that the space of configurations to be checked is drastically reduced. This pre-processing lays the bases for the automated verification of our algorithm for general grids as it permits to avoid combinatorial explosion in many cases.
Proceedings of OPODIS 2011, Toulouse, France 2011
http://arxiv.org/abs/1104.5660
Asynchronous mobile robot gathering from symmetric configurations without global multiplicity detection
Proceedings of Sirocco 2011, Gdansk, Poland 2011
http://arxiv.org/abs/1104.4022
Auto-Stabilisation et Confinement de Fautes Malicieuses : Optimalit'e du Protocole min 1
CoRR Proceedings of Algotel 2011 2011
edite:1332792337115
Bounding the Impact of Unbounded Attacks in Stabilization
2011
http://arxiv.org/abs/1106.0113
Brief Announcement: The BG-simulation for Byzantine Mobile Robots
This paper investigates the task solvability of mobile robot systems subject to Byzantine faults. We first consider the gathering problem, which requires all robots to meet in finite time at a non-predefined location. It is known that the solvability of Byzantine gathering strongly depends on a number of system attributes, such as synchrony, the number of Byzantine robots, scheduling strategy, obliviousness, orientation of local coordinate systems and so on. However, the complete characterization of the attributes making Byzantine gathering solvable still remains open. In this paper, we show strong impossibility results of Byzantine gathering. Namely, we prove that Byzantine gathering is impossible even if we assume one Byzantine fault, an atomic execution system, the n-bounded centralized scheduler, non-oblivious robots, instantaneous movements and a common orientation of local coordinate systems (where n denote the number of correct robots). Those hypotheses are much weaker than used in previous work, inducing a much stronger impossibility result. At the core of our impossibility result is a reduction from the distributed consensus problem in asynchronous shared-memory systems. In more details, we newly construct a generic reduction scheme based on the distributed BG-simulation. Interestingly, because of its versatility, we can easily extend our impossibility result for general pattern formation problems.
Proceedings of DISC 2011, Roma, Italy 2011
http://arxiv.org/abs/1104.3947
Communication Optimalement Stabilisante sur Canaux non Fiables et non FIFO
CoRR Proceedings of Algotel 2011 2011
edite:1332792352171
Distributed Computing with Mobile Robots: an Introductory Survey
This paper surveys the main characteristics of the distributed models proposed for robot networks and briefly presents the latest algorithmic achievements for tackling the agreement abstraction in both continuous and discrete space. %X
Proceedings of the International Conference on Network-Based Information Systems (NBIS), Tirana, Albania 2011
edite:1332792352177
Dynamic FTSS in Asynchronous Systems: the Case of Unison
Distributed fault-tolerance can mask the effect of a limited number of per- manent 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 syn- chronisation 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 im- possiblity results for this difficult problem and propose a FTSS solution when the problem is solvable that exhibits optimal fault containment.
Vol. 29 412, pp. 3418-3439 2011
http://arxiv.org/abs/0906.1947
Ideal Stabilization
We define and explore the concept of ideal stabilization. The program is ideally stabilizing if its every state is legitimate. Ideal stabilization allows the specification designer to prescribe with arbitrary degree of precision not only the fault-free program behavior but also its recovery operation. Specifications may or may not mention all possible states. We identify approaches to designing ideal stabilization to both kinds of specifications. For the first kind, we state the necessary condition for an ideally stabilizing solution. On the basis of this condition we prove that there is no ideally stabilizing solution to the leader election problem. We illustrate the utility of the concept by providing examples of well-known programs and proving them ideally stabilizing. Specifically, we prove ideal stabilization of the conflict manager, the alternator, the propagation of information with feedback and the alternating bit protocol.
Proceedings of IEEE AINA 2011, Biopolis, Singapore 2011
http://arxiv.org/abs/1104.5368
Maximum Metric Spanning Tree made Byzantine Tolerant
Proceedings of DISC 2011, Rome, Italy 2011
edite:1332792400342
Pragmatic Self-Stabilization of Atomic Memory in Message-Passing Systems
A fault-tolerant and 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 pragmatic 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.
Proceedings of SSS 2011, Grenoble, France 2011
http://www.oldcitypublishing.com/FullText/AHSWNfulltext/AHSWN11.1-2fulltext/AHSWNv11n1-2p1-34Mitton.pdf http://www.oldcitypublishing.com/pdf/182
Self-stabilization in Self-organized Multihop Wireless Networks
In large scale multihop wireless networks, flat architectures are typically not scalable. Clustering was introduced to support self-organization and enable hierarchical routing. When dealing with multihop wireless networks, robustness is a crucial issue due to the dynamism of such networks. Several algorithms have been designed for clustering but to date, none of them has investigated the self-stabilization features of the resulting structure. In this paper, we show that a clustering algorithm that have previously exhibited good robustness properties, is actually self-stabilizing. We propose several enhancements to the scheme to reduce the stabilization time and thus improve stability in a dynamic environment. The key technique to these enhancements is a localized self-stabilizing algorithm for Directed Acyclic Graph (DAG) construction. We provide extensive studies (both theoretical and experimental) that show that our approach enables efficient yet adaptive clustering in wireless multihop networks.
Vol. 1-2 11, pp. 1-34 2011
http://arxiv.org/abs/1106.0113
The BG-simulation for Byzantine Mobile Robots
This paper investigates the task solvability of mobile robot systems subject to Byzantine faults. We first consider the gathering problem, which requires all robots to meet in finite time at a non-predefined location. It is known that the solvability of Byzantine gathering strongly depends on a number of system attributes, such as synchrony, the number of Byzantine robots, scheduling strategy, obliviousness, orientation of local coordinate systems and so on. However, the complete characterization of the attributes making Byzantine gathering solvable still remains open. In this paper, we show strong impossibility results of Byzantine gathering. Namely, we prove that Byzantine gathering is impossible even if we assume one Byzantine fault, an atomic execution system, the n-bounded centralized scheduler, non-oblivious robots, instantaneous movements and a common orientation of local coordinate systems (where n denote the number of correct robots). Those hypotheses are much weaker than used in previous work, inducing a much stronger impossibility result. At the core of our impossibility result is a reduction from the distributed consensus problem in asynchronous shared-memory systems. In more details, we newly construct a generic reduction scheme based on the distributed BG-simulation. Interestingly, because of its versatility, we can easily extend our impossibility result for general pattern formation problems.
2011
edite:1332792427462
A Framework for Secure and Private P2P Publish/Subscribe
12th International Symposium Stabilization, Safety, and Security of Distributed Systems, SSS 2010
edite:1332792433493
Advanced Faults Patterns for WSN Dependability Benchmarking
Wireless sensor networks are typically deployed in uncon- trolled environments that have high impact on the individ- ual nodes' reliability and ability to sustain effective service for a particular application, not to mention the failure probability that increases with the size of the network itself. The high cost induced by the deployment of WSN at large scale largely prevents the use of hardware and software based fault injection, leaving simulation-based tool the only remaining option. To date, most of simulation tools for WSN do not provide extensive modules for dependability benchmarking, which leaves the protocol designers to use either external fault-injection tools of modifying the code of the application to ``simulate'' faults. Those two factors makes using realistic fault patterns difficult and might impact the real-time behavior of the applications. In this paper, we propose a new model for describing advanced fault patterns, that subsumes previously used models for characterizing faulty behaviors. We implement the model in the WSNet simulator as an intermediate layer that is distinct from any layer in the protocol stack. Our modified WSNet is then used for extensive dependability benchmarking using typical WSN application, matching both real-life fault patterns and specific attacks that evolve over time.
Proceedings of ACM MSWiM 2010, Bodrum, Turkey 2010
edite:1332792445543
Brief Announcement: Monotonic Stabilization
Proceedings of PODC 2010, Zurich, Switzerland 2010
edite:1332792445544
Brief Announcement: Sharing Memory in a Self-stabilizing Manner
24th International Symposium Distributed Computing DISC 2010
edite:1332792447562
Communications Efficaces et Auto-Stabilisation
Dans cet article, nous introduisons le concept d'efficacité des communications dans les algorithmes auto-stabilisants. Nous définissons plusieurs mesures permettant de juger de cette efficacité. Nous en étudions les limites. Enfin, nous illustrons notre approche en proposant deux algorithmes auto-stabilisants ayant de bonnes propriétés d'efficacité des communications.
Proceedings of Algotel 2010, Belle-Dune, France 2010
edite:1332792449565
Connectivity-Preserving Scattering of Mobile Robots with Limited Visibility
SSS 2010
edite:1332792449566
Construction auto-stabilisante d'arbre couvrant en dépit d'actions malicieuses
Un protocole auto-stabilisant est par nature tol'erant aux fautes transitoires (i.e. de dur'ee finie). Ces derni`eres ann'ees ont vu apparaitre une nouvelle classe de protocoles qui, en plus d'etre auto-stabilisants, tol`erent un nombre limit'e de fautes permanentes. Dans cet article, nous nous int'eressons aux protocoles auto-stabilisants tol'erant des fautes permanentes tr`es s'ev`eres : les fautes byzantines. Nous montrons que, pour certains probl`emes n'admettant pas de solution strictement stabilisante (NA02), il existe toutefois des solutions tol'erant des fautes byzantines si nous d'efinissons un crit`ere de tol'erance moins contraignant.
Proceedings of Algotel 2010, Belle-Dune, France 2010
edite:1332792456623
Exclusive Perpetual Ring Exploration without Chirality
24th International Symposium Distributed Computing DISC 2010
edite:1332792467689
Loop-Free Super-Stabilizing Spanning Tree Construction
12th International Symposium Stabilization, Safety, and Security of Distributed Systems, SSS 2010
http://hal.inria.fr/inria-00487091/PDF/DuboisMasuzawaTixeuil.pdf
On Byzantine Containment Properties of the min 1 Protocol
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. %X We consider the well known problem of constructing a breadth-first spanning tree in this context. Combining these two properties proves difficult: we demonstrate that it is impossible to contain the impact of Byzantine nodes in a strictly or strongly stabilizing manner. We then adopt the weaker scheme of topology-aware strict stabilization and we present a similar weakening of strong stabilization. We prove that the classical min 1 protocol has optimal Byzantine containment properties with respect to these criteria.
Proceedings of SSS 2010, New York, NY, USA 2010
edite:1332792479726
On Byzantine Containment Properties of the \it in 1 Protocol
12th International Symposium Stabilization, Safety, and Security of Distributed Systems, SSS 2010
edite:1332792483739
Optimal Byzantine-resilient convergence in uni-dimensional robot networks
Vol. 411, No. 34-36, pp. 3154-3168 2010
edite:1332792483740
Optimal Byzantine-resilient Convergence in Unidimensional Robot Networks
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. %X Even though convergence and the classical distributed approximate agreement problem (that requires correct processes to decide, for some constant epsilon, values distance epsilon 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. %X In more details, 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 f Byzantine robots for (2f 1)-sized robot networks in fully synchronous ATOM networks, while the second proposed algorithm tolerates f Byzantine robots for (3f 1)-sized robot networks in non-atomic CORDA networks. The resilience of these two algorithms is proved to be optimal. %X
Vol. 34-36 411, pp. 3154-3168 2010
edite:1332792484742
Optimal Deterministic Ring Exploration with Oblivious Asynchronous Robots
17th International Colloquium Structural Information and Communication Complexity, SIROCCO 2010
edite:1332792488775
Probabilistic Self-stabilizing Vertex Coloring in Unidirectional Anonymous Networks
ICDCN 2010
edite:1332792491797
Reliability, Availibility, and Security, 3rd International Workshop (WRAS 2010)
WRAS 2010
edite:1332792493802
Robocast: Asynchronous Communication in Robot Networks
Proceedings of OPODIS 2010, Tozeur, Tunisia 2010
edite:1332792494809
SAFE-OS: a Secure and Usable Desktop Operating System
Containment of application execution is a key security feature of operating systems. Without strong containment, an attacker who compromises one process may take control of the whole machine. Virtualization technology has been widely used in server systems to strongly isolate various applications or services in different virtual machines; its usage in desktop systems which are much more interactive (interactions with the user and between applications) is a challenging task. In this paper we describe SAFE-OS, a desktop operating system using virtualization technology. SAFE-OS provides a high level of isolation between processes while maintaining a standard user interface that abstracts the underlying complexity.
Proceedings of CRiSIS 2010, Montréal, Canada 2010
http://arxiv.org/abs/0912.0134
Self-Stabilizing Byzantine Asynchronous Unison
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 less than strongly fair scheduler or for system topologies with maximum node degree greater than two. We present a self-stabilizing Byzantine-tolerant solution to asynchronous unison for chain and ring topologies. Our algorithm has minimum possible containment radius and optimal stabilization time.
Proceedings of OPODIS 2010, Tozeur, Tunisia 2010
edite:1332792501834
Stabilizing Locally Maximizable Tasks in Unidirectional Networks is Hard
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 locally maximizable task (such as constructing a maximal independent set, a maximal matching, or a grundy coloring) in uniform unidirectional networks of arbitrary shape. On the negative side, we present evidence that in uniform networks, deterministic self-stabilization of this problem is impossible. Also, the silence property (i.e. having communication fixed from some point in every execution) is impossible to guarantee, either for deterministic or for probabilistic variants of protocols. %X On the positive side, we present a series of generic protocols that can be instantiated for all considered locally maximizable tasks. First, we design a deterministic protocol for 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.
Procedings of IEEE ICDCS 2010 2010
edite:1332792507864
The Impact of Topology on Byzantine Containment in Stabilization
24th International Symposium Distributed Computing DISC 2010
edite:1332792511889
Universal Loop-Free Super-Stabilization
We propose an univesal scheme to design loop-free and super-stabilizing protocols for constructing spanning trees optimizing any tree metrics (not only those that are isomorphic to a shortest path tree). %X Our scheme combines a novel super-stabilizing loop-free BFS with an existing self-stabilizing spanning tree that optimizes a given metric. The composition result preserves the best properties of both worlds: super-stabilization, loop-freedom, and optimization of the original metric without any stabilization time penalty. As case study we apply our composition mechanism to two well known metric-dependent spanning trees: the maximum-flow tree and the minimum degree spanning tree.
Proceedings of SSS 2010, New York, NY, USA 2010
edite:1332792514908
XS-WSNet : Extreme-scale Wireless Sensor Simulation
Recent advances in wireless sensor networks show an expansion both in the size of the network and in the variety of the applications that are to be executed. In this context, wireless network simulators play a key role in the design, development and testing of new wireless sensor netorks applications and protocols. Most of the currently available wireless sensor network simulators work well for small to medium sized networks yet fail to scale to really large networks, mainly due to their single desktop machine architecture and its limited resources. %X In this paper, we present XS-WSNet, a wireless sensor network simulator that is designed with extreme scalability as a first objective. First, we distribute the simulated wireless sensor network nodes on a variety of actual machines that communicate through a wired network. A large-scale simultation is then emulated by several smaller scale simulations that run concurrently and collaboratively. Contrary to previous approaches, we do not tightly synchronize the various distributed components of the simulator, inducing more asynchrony and non-determinism to the application to be tested. Our implementation of XS-WSNet is fully evaluated in various contexts using a scalable benchmark application. Against its single machine version, the distributed simulator provides sensible matching results, exhibits both scale-up and speed-up of the simulation, and performs with linear slowdown with up to ten million simulated nodes.
Proceedings of WOWMOM 2010, Montreal, Canada 2010
edite:1332792520935
A New Self-Stabilizing Maximal Matching Algorithm
2009
edite:1332792520936
A New Self-stabilizing Minimum Spanning Tree Construction with Loop-Free Property
DISC 2009
http://www.crcpress.com/product/isbn/9781584888185
Algorithms and Theory of Computation Handbook, Second Edition
CRC Press, Taylor & Francis Group 2009
edite:1332792531994
Brief Announcement: Dynamic FTSS in Asynchronous Systems: The Case of Unison
DISC 2009
edite:1332792531998
Byzantine Convergence in Robot Networks: The Price of Asynchrony
OPODIS 2009
http://www.springerlink.com/content/43650j61h3h2u106/
Byzantine Convergence in Robots Networks: The Price of Asynchrony
We study the convergence problem in fully asynchronous, uni-dimensional robot networks that are prone to Byzantine (i.e. malicious) failures. In these settings, oblivious anonymous robots with arbitrary initial positions are required to eventually converge to an a apriori unknown position despite a subset of them exhibiting Byzantine behavior. Our contribution is twofold. We propose a deterministic algorithm that solves the problem in the most generic settings: fully asynchronous robots that operate in the non-atomic CORDA model. Our algorithm provides convergence in 5f 1-sized networks where f is the upper bound on the number of Byzantine robots. Additionally, we prove that 5f 1 is a lower bound whenever robot scheduling is fully asynchronous. This constrasts with previous results in partially synchronous robots networks, where 3f 1 robots are necessary and sufficient.
Proceedings of OPODIS 2009, Nimes, France 2009
edite:13327925311000
Byzantine-Resilient Convergence in Oblivious Robot Networks
ICDCN 2009
http://arxiv.org/abs/0811.3760
Communication Efficiency in Self-Stabilizing Silent Protocols
Self-stabilization is a general paradigm to provide forward recovery capabilities to distributed systems and networks. Intuitively, a protocol is self-stabilizing if it is able to recover without external intervention from any catastrophic transient failure. In this paper, our focus is to lower the communication complexity of self-stabilizing protocols below the need of checking every neighbor forever. In more details, the contribution of the paper is threefold: (i) We provide new complexity measures for communication efficiency of self-stabilizing protocols, especially in the stabilized phase or when there are no faults, (ii) On the negative side, we show that for non-trivial problems such as coloring, maximal matching, and maximal independent set, it is impossible to get (deterministic or probabilistic) self-stabilizing solutions where every participant communicates with less than every neighbor in the stabilized phase, and (iii) On the positive side, we present protocols for coloring, maximal matching, and maximal independent set such that a fraction of the participants communicates with exactly one neighbor in the stabilized phase.
Proceedings of the IEEE International Conference on Distributed Computing Systems (ICDCS 2009), Montreal, Canada 2009
http://doi.ieeecomputersociety.org/10.1109/TPDS.2009.25 http://arxiv.org/abs/cs/0611116
Discovering Network Topology in the Presence of Byzantine Nodes
We study the problem of Byzantine-robust topology discovery in an arbitrary asynchronous network. We formally state the weak and strong versions of the problem. The weak version requires that either each node discovers the topology of the network or at least one node detects the presence of a faulty node. The strong version requires that each node discovers the topology regardless of faults. We focus on non-cryptographic solutions to these problems. We explore their bounds. We prove that the weak topology discovery problem is solvable only if the connectivity of the network exceeds the number of faults in the system. Similarly, we show that the strong version of the problem is solvable only if the network connectivity is more than twice the number of faults. We present solutions to both versions of the problem. Our solutions match the established graph connectivity bounds. The programs are terminating, they do not require the individual nodes to know either the diameter or the size of the network. The message complexity of both programs is low polynomial with respect to the network size.
Vol. 12 20, pp. 1777-1789 2009
edite:13327925421076
Exploration Optimale Probabiliste d'un Anneau par des Robots Asynchrones et Amnésiques
$11^\mboxi\`emes$ rencontres francophones sur les aspects algorithmiques des t\'el\'ecommunications (Algotel 2009), Carry-Le-Rouet, France 2009
http://hal.inria.fr/inria-00383351
Exploration Optimale Probabiliste d'un Anneau par des Robots Semi-Synchrones et Amnésiques
Nous considérons une cohorte de k robots mobiles identiques, amnésiques et semi-synchrones, capables de percevoir leur environnement mais pas de communiquer, qui évoluent sur des chemins contraints. Les résultats précédents dans ce contexte montre que les situations initiales symétriques induisent des bornes inférieures élevées quand les probl`emes doivent etre résolus par des robots déterministes. Nous initions l'étude des bornes et solutions probabilistes dans le meme contexte, et considérons le probl`eme de l'exploration d'anneaux anonymes et non orientés de taille n quelconque. Il est connu que Theta(log n) robots sont nécessaires et suffisants pour résoudre le probl`eme avec k robots déterministes, quand k et n sont premiers entre eux. Nous montrons que quatre robots probabilistes identiques sont nécessaires et suffisants pour résoudre le meme probl`eme, tout en supprimant la contrainte de coprimalité. Nos résultats positifs sont constructifs.
Proceedings of Algotel 2009 2009
edite:13327925551199
Optimal Byzantine Resilient Convergence in Asynchronous Robots Networks
SSS 2009
edite:13327925551190
On Bootstrapping Topology Knowledge in Anonymous Networks
2009
http://www.springerlink.com/content/y85737504p828377/
Optimal Byzantine Resilient Convergence in Asynchronous Robot Networks
We propose the first deterministic algorithm that tolerates up to f byzantine faults in 3f 1-sized networks and performs in the asynchronous CORDA model. Our solution matches the previously established lower bound for the semi-synchronous ATOM model on the number of tolerated Byzantine robots. Our algorithm works under bounded scheduling assumptions for oblivious robots moving in a uni-dimensional space.
Proceedings of SSS 2009., Lyon, France 2009
http://arxiv.org/abs/0905.3967
Optimal byzantine resilient convergence in oblivious robot networks
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. We draw a connection between the convergence problem in robot networks, and the distributed approximate agreement problem (that requires correct processes to decide, for some constant epsilon, values distance epsilon apart and within the range of initial proposed values). Surprisingly, even though specifications are similar, the convergence implementation in robot networks requires specific assumptions about synchrony and Byzantine resilience. In more details, 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 a deterministic convergence algorithm for robot networks and analyze its correctness and complexity in various synchrony settings. The proposed algorithm tolerates f Byzantine robots for (2f 1)-sized robot networks in fully synchronous networks, (3f 1)-sized in semi-synchronous networks. These bounds are optimal for the class of cautious algorithms, which guarantee that correct robots always move inside the range of positions of the correct robots.
2009
edite:13327925551201
Optimal deterministic self-stabilizing vertex coloring in unidirectional anonymous networks
IPDPS 2009
http://hal.inria.fr/inria-00360305/fr/
Optimal Probabilistic Ring Exploration by Asynchronous Oblivious Robots
We consider a team of k identical, oblivious, asynchronous mobile robots that are able to sense (i.e., view) their environment, yet are unable to communicate, and evolve on a constrained path. Previous results in this weak scenario show that initial symmetry yields high lower bounds when problems are to be solved by deterministic robots. In this paper, we initiate research on probabilistic bounds and solutions in this context, and focus on the exploration problem of anonymous unoriented rings of any size. It is known that Theta(log n) robots are necessary and sufficient to solve the problem with k deterministic robots, provided that k and n are coprime. By contrast, we show that four identical probabilistic robots are necessary and sufficient to solve the same problem, also removing the coprime constraint. Our positive results are constructive.
Proceedings of Sirocco 2009, Piran, Slovenia 2009
edite:13327925551204
Optimal Probabilistic Ring Exploration by Semi-Synchronous Oblivious Robots
16th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2009), Piran, Slovenia 2009
edite:13327925601241
Reliability, Availibility, and Security, 2nd International Workshop (WRAS 2009)
WRAS 2009
edite:13327925611255
Self-stabilizing Philosophers with Generic Conflicts
2009
edite:13327925621266
Snap-Stabilization in Message-Passing Systems
International Conference on Distributed Computing and Networking (ICDCN 2009) 2009
http://hal.inria.fr/inria-00383350
Stabilisation Instantanée dans les Syst`emes `a Passage de Messages
Nous abordons le probl`eme de la stabilisation instantanée dans les syst`emes répartis `a passage de messages. Notre contribution est double. Tout d'abord, nous montrons que la stabilisation instantanée est impossible pour la plupart des probl`emes dans de tels syst`emes si nous supposons que la capacité des canaux de communication est finie mais non bornée. Nous montrons ensuite que la stabilisation instantanée devient réalisable si nous connaissons une borne sur la capacité des canaux de communication. Cette derni`ere contribution est constructive : nous proposons les deux premiers protocoles répartis instantanément stabilisants dans le mod`ele `a passage de messages.
Proceedings of Algotel 2009 2009
http://arxiv.org/abs/0903.3106
Stabilizing Maximal Independent Set in Unidirectional Networks is Hard
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 maximal independent set in uniform unidirectional networks of arbitrary shape. On the negative side, we present evidence that in uniform networks, deterministic self-stabilization of this problem is impossible. Also, the silence property (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.
2009
http://hal.inria.fr/inria-00384649
Sur le Coloriage Auto-stabilisant dans les Réseaux Unidirectionnels Anonymes
Nous considérons des réseaux unidirectionnels anonymes. Nous démontrons que contrairement aux réseaux bidirectionnels, l'auto-stabilisation de taches locales peut y etre aussi difficile que l'auto-stabilisation de taches globales. Pour ce faire, nous prenons comme exemple le probl`eme du coloriage des noeuds d'un réseau. Plus précisément, nous démontrons que le coloriage auto-stabilisant est intrins`equement aussi difficile `a résoudre de mani`ere déterministe qu'une tache globale. Nous proposons ensuite une approche probabiliste pour retrouver une complexité locale.
Proceedings of Algotel 2009 2009
oai:tel.archives-ouvertes.fr:tel-00124848
Vers l'auto-stabilisation des systèmes à grande échelle
Vers l'auto-stabilisation des systèmes à grande échelle.
habilitation à diriger des recherches 2006-05-22
oai:hal.archives-ouvertes.fr:hal-00569219
Self-stabilizing Algorithms
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.
Algorithms and theory of computation handbookscientific book chapter 2009
oai:tel.archives-ouvertes.fr:tel-00124843
Auto-stabilisation Efficace
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.
PhD thesis 2000-01-14
oai:hal.archives-ouvertes.fr:inria-00589390
Asynchronous mobile robot gathering from symmetric configurations without global multiplicity detection
We consider a set of k autonomous robots that are endowed with visibility sensors (but that are otherwise unable to communicate) and motion actuators. Those robots must collaborate to reach a sin- gle vertex that is unknown beforehand, and to remain there hereafter. Previous works on gathering in ring-shaped networks suggest that there exists a tradeoff between the size of the set of potential initial configurations, and the power of the sensing capabilities of the robots (i.e. the larger the initial configura- tion set, the most powerful the sensor needs to be). We prove that there is no such trade off. We propose a gathering protocol for an odd number of robots in a ring-shaped network that allows symmetric but not periodic configurations as initial configurations, yet uses only local weak multiplicity detection. Robots are assumed to be anonymous and oblivious, and the execution model is the non-atomic CORDA model with asynchronous fair scheduling. Our protocol allows the largest set of initial configurations (with respect to impossibility results) yet uses the weakest multiplicity detector to date. The time complexity of our protocol is O(n2), where n denotes the size of the ring. Compared to previous work that also uses local weak multiplicity detection, we do not have the constraint that k < n/2 (here, we simply have 2 < k < n − 3).
research report 2011-04-28
oai:hal.archives-ouvertes.fr:inria-00589234
Maximum Metric Spanning Tree made Byzantine Tolerant
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. This paper focus on systems that are both self-stabilizing and Byzantine tolerant. We consider the well known problem of constructing a maximum metric tree in this context. Combining these two properties is known to induce many impossibility results. In this paper, we provide first two impossibility results about the construction of maximum metric tree in presence of transients and (permanent) Byzantine faults. Then, we provide a new self-stabilizing protocol that provides optimal containment of an arbitrary number of Byzantine faults.
research report 2011-04-28