Optimal Probabilistic Ring Exploration by Asynchronous Oblivious Robots (2009)
Devismes, Stéphane, Petit, Franck, Tixeuil, Sébastien
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...
Optimal Probabilistic Ring Exploration by Asynchronous Oblivious Robots (2009)
Devismes, Stéphane, Petit, Franck, Tixeuil, Sébastien
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...
Optimal Probabilistic Ring Exploration by Asynchronous Oblivious Robots (2009)
Devismes, Stéphane, Petit, Franck, Tixeuil, Sébastien
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...
Sur le Coloriage Auto-stabilisant dans les Réseaux Unidirectionnels Anonymes (2009)
Bernard, Samuel, Devismes, Stéphane, Paroux, Katy, Tixeuil, Sébastien
Nous considérons des réseaux unidirectionnels anonymes. Nous démontrons que contrairement aux réseaux bidirectionnels, l'auto-stabilisation de tâches locales peut y être aussi difficile que...
Exploration Optimale Probabiliste d'un Anneau \\par des Robots Semi-Synchrones et Amnésiques (2009)
Devismes, Stéphane, Petit, Franck, Tixeuil, Sébastien
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...
Stabilisation instantanée dans les systèmes à passage de messages (2009)
Delaët, Sylvie, Devismes, Stéphane, Nesterenko, Mikhail, Tixeuil, Sébastien
Nous abordons le problème de la \emph{stabilisation instantanée} dans les systèmes répartis à passage de messages. Notre contribution est double. Tout d'abord, nous montrons que la stabilisation...
Quand le consensus est plus simple que la diffusion fiable (2009)
Delporte-Gallet, Carole, Devismes, Stéphane, Fauconnier, Hugues, Petit, Franck, Toueg, Sam
Nous nous intéressons à l'impact de la limitation de la mémoire sur des problèmes algorithmiques distribués classiques dans le contexte de systèmes asynchrones sujets aux pannes franches.
Sur le Coloriage Auto-stabilisant dans les Réseaux Unidirectionnels Anonymes (2009)
Bernard, Samuel, Devismes, Stéphane, Paroux, Katy, Tixeuil, Sébastien
Nous considérons des réseaux unidirectionnels anonymes. Nous démontrons que contrairement aux réseaux bidirectionnels, l'auto-stabilisation de tâches locales peut y être aussi difficile que...
Exploration Optimale Probabiliste d'un Anneau \\par des Robots Semi-Synchrones et Amnésiques (2009)
Devismes, Stéphane, Petit, Franck, Tixeuil, Sébastien
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...
Stabilisation instantanée dans les systèmes à passage de messages (2009)
Delaët, Sylvie, Devismes, Stéphane, Nesterenko, Mikhail, Tixeuil, Sébastien
Nous abordons le problème de la \emph{stabilisation instantanée} dans les systèmes répartis à passage de messages. Notre contribution est double. Tout d'abord, nous montrons que la stabilisation...
Quand le consensus est plus simple que la diffusion fiable (2009)
Delporte-Gallet, Carole, Devismes, Stéphane, Fauconnier, Hugues, Petit, Franck, Toueg, Sam
Nous nous intéressons à l'impact de la limitation de la mémoire sur des problèmes algorithmiques distribués classiques dans le contexte de systèmes asynchrones sujets aux pannes franches.
Self-stabilizing K-out-of-L exclusion on tree network (2008)
Datta, Ajoy, Devismes, Stéphane, Horn, Florian, Larmore, Lawrence
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...
Self-stabilizing K-out-of-L exclusion on tree network (2008)
Datta, Ajoy, Devismes, Stéphane, Horn, Florian, Larmore, Lawrence
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...
Self-stabilizing K-out-of-L exclusion on tree network (2008)
Datta, Ajoy, Devismes, Stéphane, Horn, Florian, Larmore, Lawrence
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...
Self-stabilizing K-out-of-L exclusion on tree network (2008)
Datta, Ajoy, Devismes, Stéphane, Horn, Florian, Larmore, Lawrence
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...
Self-stabilizing K-out-of-L exclusion on tree network (2008)
Datta, Ajoy, Devismes, Stéphane, Horn, Florian, Larmore, Lawrence
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...
Self-stabilizing K-out-of-L exclusion on tree network (2008)
Datta, Ajoy, Devismes, Stéphane, Horn, Florian, Larmore, Lawrence
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...
Self-stabilizing K-out-of-L exclusion on tree network (2008)
Datta, Ajoy K., Devismes, Stéphane, Horn, Florian, Larmore, Lawrence L.
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...
Communication Efficiency in Self-stabilizing Silent Protocols (2008)
Devismes, Stéphane, Masuzawa, Toshimitsu, Tixeuil, Sébastien
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...
Self-Stabilizing-out-of- ¡ Exclusion (2008)
Ajoy K. Datta, Stéphane Devismes, Florian Horn, Lawrence L. Larmore
In this paper, self-stabilizing asynchronous distributed algorithms are given for the¥-out-of-¦exclusion problem, a generalization of the mutual exclusion problem, in which there are§units of a...
Bounds for self-stabilization in unidirectional networks (2008)
Bernard, Samuel, Devismes, Stéphane, Tixeuil, Sébastien
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...
Bounds for self-stabilization in unidirectional networks (2008)
Bernard, Samuel, Devismes, Stéphane, Tixeuil, Sébastien
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...
Bounds for self-stabilization in unidirectional networks (2008)
Bernard, Samuel, Devismes, Stéphane, Potop-Butucaru, Maria Gradinariu, Tixeuil, Sébastien
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...
Snap-Stabilization in Message-Passing Systems (2008)
Delaët, Sylvie, Devismes, Stéphane, Nesterenko, Mikhail, Tixeuil, Sébastien
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...
Snap-Stabilization in Message-Passing Systems (2008)
Delaët, Sylvie, Devismes, Stéphane, Nesterenko, Mikhail, Tixeuil, Sébastien
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...
Snap-Stabilization in Message-Passing Systems (2008)
Delaët, Sylvie, Devismes, Stéphane, Nesterenko, Mikhail, Tixeuil, Sébastien
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...
A Lighter Generic Protocol for Snap-Stabilization (2008)
Alain Cournier, Stéphane Devismes, Vincent Villain, Jules Verne
A snap-stabilizing protocol, starting from any arbitrary initial configuration, always behaves according to its specification. In [11], we propose a protocol that snap-stabilizes self-stabilizing...
Snap-Stabilization in Message-Passing Systems (2008)
Delaët, Sylvie, Devismes, Stéphane, Nesterenko, Mikhail, Tixeuil, Sébastien
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...
Snap-Stabilization in Message-Passing Systems (2008)
Delaët, Sylvie, Devismes, Stéphane, Nesterenko, Mikhail, Tixeuil, Sébastien
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...
Bounds for self-stabilization in unidirectional networks (2008)
Bernard, Samuel, Devismes, Stéphane, Tixeuil, Sébastien
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...
Bounds for self-stabilization in unidirectional networks (2008)
Bernard, Samuel, Devismes, Stéphane, Tixeuil, Sébastien
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...
Consensus is Easier Than Reliable Broadcast (2008)
Delporte-Gallet, Carole, Devismes, Stéphane, Fauconnier, Hugues, Petit, Franck, Toueg, Sam
We consider asynchronous distributed systems with message losses and process crashes. We study the impact of finite process memory on the solution to consensus, repeated consensus and reliable...
Consensus is Easier Than Reliable Broadcast (2008)
Delporte-Gallet, Carole, Devismes, Stéphane, Fauconnier, Hugues, Petit, Franck, Toueg, Sam
We consider asynchronous distributed systems with message losses and process crashes. We study the impact of finite process memory on the solution to consensus, repeated consensus and reliable...
Communication Efficiency in Self-stabilizing Silent Protocols (2008)
Devismes, Stéphane, Masuzawa, Toshimitsu, Tixeuil, Sébastien
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...
Communication Efficiency in Self-stabilizing Silent Protocols (2008)
Devismes, Stéphane, Masuzawa, Toshimitsu, Tixeuil, Sébastien
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...
Self-stabilizing K-out-of-L exclusion on tree network (2008)
Datta, Ajoy, Devismes, Stéphane, Horn, Florian, Larmore, Lawrence
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...
Self-stabilizing K-out-of-L exclusion on tree network (2008)
Datta, Ajoy, Devismes, Stéphane, Horn, Florian, Larmore, Lawrence
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...
Weak vs. Self vs. Probabilistic Stabilization (2007)
Devismes, Stéphane, Tixeuil, Sébastien, Yamashita, Masafumi
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...
Quelques Contributions à la Stabilisation Instantanée (2007)
Dans cette thèse, nous nous sommes intéressés au concept de stabilisation instantanée. Ainsi, nous avons tout d'abord proposé deux solutions instantanément stabilisantes au problème de...
Robust Stabilizing Leader Election (2007)
Delporte-Gallet, Carole, Devismes, Stéphane, Fauconnier, Hugues
In this paper, we mix two well-known approaches of the fault-tolerance: robustness and stabilization. Robustness is the aptitude of an algorithm to withstand permanent failures such as process...
Weak vs. Self vs. Probabilistic Stabilization (2007)
Devismes, Stéphane, Tixeuil, Sébastien, Yamashita, Masafumi
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...
Weak vs. Self vs. Probabilistic Stabilization (2007)
Devismes, Stéphane, Tixeuil, Sébastien, Yamashita, Masafumi
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...
Robust Stabilizing Leader Election (2007)
Delporte-Gallet, Carole, Devismes, Stéphane, Fauconnier, Hugues
In this paper, we mix two well-known approaches of the fault-tolerance: robustness and stabilization. Robustness is the aptitude of an algorithm to withstand permanent failures such as process...
Quelques Contributions à la Stabilisation Instantanée (2006)
Dans cette thèse, nous nous sommes intéressés au concept de stabilisation instantanée. Ainsi, nous avons tout d'abord proposé deux solutions instantanément stabilisantes au problème de...
Quelques Contributions à la Stabilisation Instantanée (2006)
Dans cette thèse, nous nous sommes intéressés au concept de stabilisation instantanée. Ainsi, nous avons tout d'abord proposé deux solutions instantanément stabilisantes au problème de...
Quelques Contributions à la Stabilisation Instantanée (2006)
Dans cette thèse, nous nous sommes intéressés au concept de stabilisation instantanée. Ainsi, nous avons tout d'abord proposé deux solutions instantanément stabilisantes au problème de...
Quelques Contributions à la Stabilisation Instantanée (2006)
Dans cette thèse, nous nous sommes intéressés au concept de stabilisation instantanée. Ainsi, nous avons tout d'abord proposé deux solutions instantanément stabilisantes au problème de...
Quelques Contributions à la Stabilisation Instantanée (2006)
Dans cette thèse, nous nous sommes intéressés au concept de stabilisation instantanée. Ainsi, nous avons tout d'abord proposé deux solutions instantanément stabilisantes au problème de...
From Self- to Snap- Stabilization (2006)
Alain Cournier, Stéphane Devismes, Jules Verne
A snap-stabilizing protocol, starting from any arbitrary initial configuration, always behaves according to its specification. In this paper, we propose a light semi-automatic method allowing to...
Snap-stabilizing pif and useless computations (2006)
Alain Cournier, Stéphane Devismes, Vincent Villain, Jules Verne
A snap-stabilizing protocol, starting from any arbitrary initial configuration, always behaves according to its specification. In other words, a snap-stabilizing protocol is a self-stabilizing...
Snap-Stabilizing Depth-First Search on Arbitrary Networks (2006)
Cournier, Alain, Devismes, Stéphane, Petit, Franck, Villain, Vincent
A snap-stabilizing protocol, starting from any arbitrary initial configuration, always behaves according to its specification. In this paper, we present the first snap-stabilizing depth-first search...
Snap-Stabilizing Depth-First Search on Arbitrary Networks (2006)
Cournier, Alain, Devismes, Stéphane, Petit, Franck, Villain, Vincent
A snap-stabilizing protocol, starting from any arbitrary initial configuration, always behaves according to its specification. In this paper, we present the first snap-stabilizing depth-first search...
A silent self-stabilizing algorithm for finding cut-nodes and bridges (2005)
Stéphane Devismes, Jules Verne
In this paper, we present a silent algorithm for finding cut-nodes and bridges in arbitrary rooted networks. This algorithm must be composed with an algorithm from Collin and Dolev. This latter...
A snap-stabilizing dfs with a lower space requirement (2005)
Alain Cournier, Stéphane Devismes, Vincent Villain, Jules Verne
A snap-stabilizing protocol, starting from any arbitrary initial configuration, always behaves according to its specification. In [1], we presented the first snap-stabilizing depth-first search ( ...
Snap-stabilizing depth-first search on arbitrary networks (2004)
Alain Cournier, Stéphane Devismes, Franck Petit, Vincent Villain
A snap-stabilizing protocol, starting from any arbitrary initial configuration, always behaves according to its specification. In this paper, we present the first snap-stabilizing depth-first search...