Franck Petit

TCS Journal 2026 Journal Article

Guest editorial – Stabilization safety, and security of distributed systems

• Stéphane Devismes
• Franck Petit

TCS Journal 2025 Journal Article

When should you wait before updating? - Toward a robustness refinement

• Swan Dubois
• Laurent Feuilloley
• Franck Petit
• Mikaël Rabie

Consider a dynamic network and a given distributed problem. At any point in time, there might exist several solutions that are equally good with respect to the problem specification, but that are different from an algorithmic perspective, because some could be easier to update than others when the network changes. In other words, one would prefer to have a solution that is more robust to topological changes in the network; and in this direction the best scenario would be that the solution remains correct despite the dynamic of the network. In [1], the authors introduced a very strong robustness criterion: they required that for any removal of edges that maintain the network connected, the solution remains valid. They focus on the maximal independent set problem, and their approach consists in characterizing the graphs in which there exists a robust solution (the existential problem), or even stronger, where any solution is robust (the universal problem). As the robustness criteria are very demanding, few graphs have a robust solution, and even fewer are such that all of their solutions are robust. In this paper, we ask the following question: Can we expect to obtain a relaxed (i. e. , less demanding) version of robustness by limiting the maximum number of edges removals to a specific value k? To answer this question, we consider three classic problems: maximal independent set, minimal dominating set and maximal matching. For the universal problem, the answers for the three cases are surprisingly different. For minimal dominating set, the class does not depend on the number of edges removed. For maximal matching, removing only one edge defines a robust class related to perfect matchings, but for all other bounds k, the class is the same as for an arbitrary number of edge removals. Finally, for maximal independent set, there is a strict hierarchy of classes: the class for the bound k is strictly larger than the class for bound k + 1. For the robustness notion of [1], no characterization of the class for the existential problem is known, only a polynomial-time recognition algorithm. We show that the situation is even worse for bounded k: Even for k=1, we show that the problem of deciding whether a graph has a robust maximal independent set is NP-hard. The same question seems to be at least as difficult for the maximal matching problem.

TCS Journal 2023 Journal Article

Self-stabilizing systems in spite of high dynamics

• Karine Altisen
• Stéphane Devismes
• Anaïs Durand
• Colette Johnen
• Franck Petit

We initiate research on self-stabilization in highly dynamic identified message-passing systems where dynamics is modeled using time-varying graphs (TVGs). More precisely, we address the self-stabilizing leader election problem in three wide classes of TVGs: the class TC B ( Δ ) of TVGs with temporal diameter bounded by Δ, the class TC Q ( Δ ) of TVGs with temporal diameter quasi-bounded by Δ, and the class TC R of TVGs with recurrent connectivity only, where TC B ( Δ ) ⊆ TC Q ( Δ ) ⊆ TC R. We first study conditions under which our problem can be solved. We introduce the notion of size-ambiguity to show that the assumption on the knowledge of the number n of processes is central. Our results reveal that, despite the existence of unique process identifiers, any deterministic self-stabilizing leader election algorithm working on the class TC Q ( Δ ) or TC R cannot be size-ambiguous, justifying why our solutions for those classes assume the exact knowledge of n. We then present three self-stabilizing leader election algorithms for Classes TC B ( Δ ), TC Q ( Δ ), and TC R, respectively. Our algorithm for TC B ( Δ ) stabilizes in at most 3Δ rounds. However, we show that stabilization time cannot be bounded for the leader election problem in TC Q ( Δ ) and TC R. Nevertheless, we circumvent this issue by showing that our solutions are speculative in the sense that their stabilization time in TC B ( Δ ) ( ⊆ TC Q ( Δ ) ⊆ TC R ) is O ( Δ ) rounds.

TCS Journal 2020 Journal Article

Robustness: A new form of heredity motivated by dynamic networks

• Arnaud Casteigts
• Swan Dubois
• Franck Petit
• John M. Robson

We investigate a special case of hereditary property in graphs, referred to as robustness. A property (or structure) is called robust in a graph G if it is inherited by all the connected spanning subgraphs of G. We motivate this definition using two different settings of dynamic networks. The first corresponds to networks of low dynamicity, where some links may be permanently removed so long as the network remains connected. The second corresponds to highly-dynamic networks, where communication links appear and disappear arbitrarily often, subject only to the requirement that the entities are temporally connected in a recurrent fashion (i. e. they can always reach each other through temporal paths). Each context induces a different interpretation of the notion of robustness. We start by motivating the definition and discussing the two interpretations, after what we consider the notion independently from its interpretation, taking as our focus the robustness of maximal independent sets (MIS). A graph may or may not admit a robust MIS. We characterize the set of graphs RMI S ∀ in which all MISs are robust. Then, we turn our attention to the graphs that admit a robust MIS ( RMI S ∃ ). This class has a more complex structure; we give a partial characterization in terms of elementary graph properties, then a complete characterization by means of a (polynomial time) decision algorithm that accepts if and only if a robust MIS exists. This algorithm can be adapted to construct such a solution if one exists.

I&C Journal 2017 Journal Article

Self-stabilizing leader election in polynomial steps

• Karine Altisen
• Alain Cournier
• Stéphane Devismes
• Anaïs Durand
• Franck Petit

We propose a silent self-stabilizing leader election algorithm for bidirectional arbitrary connected identified networks. This algorithm is written in the locally shared memory model under the distributed unfair daemon. It requires no global knowledge on the network. Its stabilization time is in Θ ( n 3 ) steps in the worst case, where n is the number of processes. Its memory requirement is asymptotically optimal, i. e. , Θ ( log ⁡ n ) bits per processes. Its round complexity is of the same order of magnitude — i. e. , Θ ( n ) rounds — as the best existing algorithms designed with similar settings. To the best of our knowledge, this is the first self-stabilizing leader election algorithm for arbitrary identified networks that is proven to achieve a stabilization time polynomial in steps. By contrast, we show that the previous best existing algorithms designed with similar settings stabilize in a non-polynomial number of steps in the worst case.

TCS Journal 2016 Journal Article

The expressive power of snap-stabilization

• Alain Cournier
• Ajoy K. Datta
• Stéphane Devismes
• Franck Petit
• Vincent Villain

A snap-stabilizing algorithm, regardless of the initial configuration of the system, guarantees that it always behaves according to its specification. We consider here the locally shared memory model. In this model, we propose the first snap-stabilizing Propagation of Information with Feedback (PIF) algorithm for rooted networks of arbitrary connected topology which is proven assuming the distributed unfair daemon. Then, we use the proposed PIF algorithm as a key module in designing snap-stabilizing solutions for some fundamental problems in distributed systems, such as Leader Election, Reset, Snapshot, and Termination Detection. Finally, we show that in the locally shared memory model, snap-stabilization is as expressive as self-stabilization by designing a universal transformer to provide a snap-stabilizing version of any algorithm that can be self-stabilized with the transformer of Katz and Perry (1993) [28]. Since by definition a snap-stabilizing algorithm is also self-stabilizing, self- and snap-stabilization have the same expressiveness in the locally shared memory model.

TCS Journal 2013 Journal Article

Deterministic geoleader election in disoriented anonymous systems

• Yoann Dieudonné
• Florence Levé
• Franck Petit
• Vincent Villain

Consider a network made of n nodes scattered in the 2-dimensional space. Nodes are anonymous and disoriented devices being unable to communicate. Anonymous refers to systems made of a priori indistinguishable nodes. By disoriented, we mean that the nodes share no kind of coordinate system nor common sense of direction. Such systems are typically wireless sensor networks or swarms of robots endowed with localization capabilities, for instance visibility sensors or pattern formation maps. We address the Geoleader Election (GE) problem which is to ensure that, solely based on their positions, the nodes deterministically agree on the same position of a single node, called the leader. We provide a complete characterization on the node positions, both for systems with common handedness (chirality) and for systems devoid of a common handedness. The characterization is based on a particular object from combinatorics on words, namely the Lyndon words.

TCS Journal 2013 Journal Article

Optimal probabilistic ring exploration by semi-synchronous oblivious robots

• Stéphane Devismes
• Franck Petit
• Sébastien Tixeuil

We consider a team of k identical, oblivious, and semi-synchronous 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 n. It is known that k = Θ ( log n ) deterministic robots are necessary and sufficient to solve the problem, 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.

TCS Journal 2013 Journal Article

Preface

• Xavier Défago
• Franck Petit
• Vincent Villain

TCS Journal 2013 Journal Article

The snap-stabilizing message forwarding algorithm on tree topologies

• Alain Cournier
• Swan Dubois
• Anissa Lamani
• Franck Petit
• Vincent Villain

In this paper, we consider the message forwarding problem that consists in managing the network resources that are used to forward messages. Previous works on this problem provide solutions that either use a significant number of buffers (that is n buffers per process, where n is the number of processes in the network) making the solution not scalable or reserve all the buffers from the sender to the receiver to forward only one message. The only solution that uses a constant number of buffers per link was introduced in Cournier et al. (2010) [1]. However the solution works only on a chain network. In this paper, we propose a snap-stabilizing algorithm for the message forwarding problem that uses a constant number of buffers per link as in Cournier et al. (2010) [1] but works on tree topologies.

TCS Journal 2012 Journal Article

Self-stabilizing gathering with strong multiplicity detection

• Yoann Dieudonné
• Franck Petit

In this paper, we investigate the possibility to deterministically solve the gathering problem starting from an arbitrary configuration with weak robots, i. e. , anonymous, autonomous, disoriented, oblivious, and devoid of means of communication. By starting from an arbitrary configuration, we mean that robots are not required to be located at distinct positions in the initial configuration. We introduce strong multiplicity detection as the ability for the robots to detect the exact number of robots located at a given position. We show that with strong multiplicity detection, there exists a deterministic algorithm solving the gathering problem starting from an arbitrary configuration for n robots if, and only if, n is odd.

TCS Journal 2011 Journal Article

Stabilization, Safety, and Security of Distributed Systems (SSS 2009)

• Ajoy K. Datta
• Franck Petit
• Rachid Guerraoui

TAAS Journal 2008 Journal Article

Circle formation of weak mobile robots

• Yoann Dieudonné
• Ouiddad Labbani-Igbida
• Franck Petit

We consider distributed systems made of weak mobile robots, that is, mobile devices, equipped with sensors, that are anonymous, autonomous, disoriented, and oblivious. The Circle Formation Problem (CFP) consists of the design of a protocol insuring that, starting from an initial arbitrary configuration where no two robots are at the same position, all the robots eventually form a regular n-gon —the robots take place on the circumference of a circle C with equal spacing between any two adjacent robots on C. CFP is known to be unsolvable by arranging the robots evenly along the circumference of a circle C without leaving C —that is, starting from a configuration where the robots are on the boundary of C. We circumvent this impossibility result by designing a scheme based on concentric circles. This is the first scheme that deterministically solves CFP. We present our method with two different implementations working in the semi-synchronous system (SSM) for any number n ≥ 5 of robots.

ICRA Conference 2008 Conference Paper

On the solvability of the localization problem in robot networks

• Yoann Dieudonné
• Ouiddad Labbani-Igbida
• Franck Petit

This paper contributes to the problem of deterministic localization of robot networks using local and relative observations only. This is an important issue in collective and cooperative robotics where global positioning systems are not available, and the basic premise is the localization ability of the group. We prove that, giving a set of relative observations made by the robots, the unique non ambiguous pose estimation of the robot network in a deterministic way, is a NP-hard problem. This means that no polynomial-time algorithm can deterministically solve the unique pose estimation problem based on relative observations. The consequence is that no guaranty can be provided, in a polynomial time, that the possibly estimated poses of the robots, will correspond to the effective (actual) ones. The proof is based on complexity theory. We build appropriate polynomial-time reductions acting on the localization problem and leading to well known NP-hard problems. The paper gives some tracks to overcome this issue.