Stephane Devismes - VERIMAG - IMAG

Stephane Devismes
Are you Stephane Devismes?

Claim your profile, edit publications, add additional information:

Contact Details

Stephane Devismes

Pubs By Year

Pub Categories

Computer Science - Distributed; Parallel; and Cluster Computing (10)
Computer Science - Networking and Internet Architecture (6)
Computer Science - Data Structures and Algorithms (4)
Computer Science - Computational Complexity (3)
Computer Science - Robotics (2)
Computer Science - Performance (1)
Computer Science - Logic in Computer Science (1)
Computer Science - Discrete Mathematics (1)

Publications Authored By Stephane Devismes

We deal with the problem of maintaining a shortest-path tree rooted at some process r in a network that may be disconnected after topological changes. The goal is then to maintain a shortest-path tree rooted at r in its connected component, Vr, and make all processes of other components detecting that r is not part of their connected component. We propose, in the composite atomicity model, a silent self-stabilizing algorithm for this problem working in semi-anonymous networks, where edges have strictly positive weights. Read More

We propose a general framework to build certified proofs of distributed self-stabilizing algorithms with the proof assistant Coq. We first define in Coq the locally shared memory model with composite atomicity, the most commonly used model in the self-stabilizing area. We then validate our framework by certifying a non trivial part of an existing silent self-stabilizing algorithm which builds a k-clustering of the network. Read More

In this paper, we revisit two fundamental results of the self-stabilizing literature about silent BFS spanning tree constructions: the Dolev et al algorithm and the Huang and Chen's algorithm. More precisely, we propose in the composite atomicity model three straightforward adaptations inspired from those algorithms. We then present a deep study of these three algorithms. Read More

We consider a team of {\em autonomous weak robots} that are endowed with visibility sensors and motion actuators. Autonomous means that the team cannot rely on any kind of central coordination mechanism or scheduler. By weak we mean that the robots are devoid of (1) any (observable) IDs allowing to differentiate them (anonymous), (2) means of communication allowing them to communicate directly, and (3) any way to remember any previous observation nor computation performed in any previous step (oblivious). Read More

We consider asynchronous message-passing systems in which some links are timely and processes may crash. Each run defines a timeliness graph among correct processes: (p; q) is an edge of the timeliness graph if the link from p to q is timely (that is, there is bound on communication delays from p to q). The main goal of this paper is to approximate this timeliness graph by graphs having some properties (such as being trees, rings, . Read More

We consider a team of $k$ identical, oblivious, asynchronous mobile robots that are able to sense (\emph{i.e.}, view) their environment, yet are unable to communicate, and evolve on a constrained path. Read More

In this paper, we address the problem of K-out-of-L exclusion, a generalization of the mutual exclusion problem, in which there are $\ell$ units of a shared resource, and any process can request up to $\mathtt k$ units ($1\leq\mathtt k\leq\ell$). We propose the first deterministic self-stabilizing distributed K-out-of-L exclusion protocol in message-passing systems for asynchronous oriented tree networks which assumes bounded local memory for each process. Read More

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 \emph{below} the need of checking every neighbor forever. Read More

A distributed algorithm is self-stabilizing if after faults and attacks hit the system and place it in some arbitrary global state, the systems recovers from this catastrophic situation without external intervention in finite time. Unidirectional networks preclude many common techniques in self-stabilization from being used, such as preserving local predicates. In this paper, we investigate the intrinsic complexity of achieving self-stabilization in unidirectional networks, and focus on the classical vertex coloring problem. Read More

In this paper, we tackle the open problem of snap-stabilization in message-passing systems. Snap-stabilization is a nice approach to design protocols that withstand transient faults. Compared to the well-known self-stabilizing approach, snap-stabilization guarantees that the effect of faults is contained immediately after faults cease to occur. Read More

Self-stabilization is a strong property that guarantees that a network always resume correct behavior starting from an arbitrary initial state. Weaker guarantees have later been introduced to cope with impossibility results: probabilistic stabilization only gives probabilistic convergence to a correct behavior. Also, weak stabilization only gives the possibility of convergence. Read More