État académique
Thèse soutenue le 2000-12-20
Titulaire d'une HDR (ou équivalent) 2010-12-13
Laboratoire: personnel permanent
Direction de thèses (depuis 2007)
Encadrement de thèses (depuis 2007)
Propositions de sujets de thèse
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
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
Communication Optimalement Stabilisante sur Canaux non Fiables et non FIFO
CoRR Proceedings of Algotel 2011 2011
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
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
Enhancing Fault Tolerance of Distributed R-Tree
5th Latin-American Symposium on Dependable Computing 2011
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
Exclusive Perpetual Ring Exploration without Chirality
24th International Symposium Distributed Computing DISC 2010
Probabilistic Self-stabilizing Vertex Coloring in Unidirectional Anonymous Networks
ICDCN 2010
Robocast: Asynchronous Communication in Robot Networks
Proceedings of OPODIS 2010, Tozeur, Tunisia 2010
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
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
A Superstabilizing log(n)-Approximation Algorithm for Dynamic Steiner Trees
This paper proposes a fully dynamic self-stabilizing algorithm for the Steiner tree problem. The Steiner tree problem aims at constructing a Minimum Spanning Tree (MST) over a subset of nodes called Steiner members, or Steiner group usually denoted S. Steiner trees are good candidates to efficiently implement communication primitives such as publish/subscribe or multicast, essential building blocks in the design of middleware architectures for the new emergent networks (e.g. P2P, sensor or adhoc networks). Our algorithm returns a log|S|-approximation of the optimal Steiner tree. It improves over existing solutions in several ways. First, it is fully dynamic, in other words it withstands the dynamism when both the group members and ordinary nodes can join or leave the network. Next, our algorithm is self-stabilizing, that is, it copes with nodes memory corruption. Last but not least, our algorithm is superstabilizing. That is, while converging to a correct configuration (i.e., a Steiner tree) after a modification of the network, it keeps offering the Steiner tree service during the stabilization time to all members that have not been affected by this modification
The 11th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2009) 2009
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
log(n)-approximation d'un arbre de Steiner auto-stabilisant et dynamique
11 èmes Rencontres Francophones sur les aspects Algorithmiques des Télécommunications (AlgoTel 2009) 2009
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.