Author name cluster

Alain Cournier

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers

1 author row

TCS Journal 2024 Journal Article

Self-stabilizing synchronous unison in directed networks

Karine Altisen
Alain Cournier
Geoffrey Defalque
Stéphane Devismes

Self-stabilization is a general paradigm that characterizes the ability of a distributed system to recover from transient faults. Since its introduction by Dijkstra in 1974, self-stabilization has been successfully applied to efficiently solve many networking tasks. However, most of the literature focuses on bidirectional networks. Now, in today's networks such as WSNs, some communication channels may be one-way only. Considering such network topologies, a. k. a. directed graphs, makes self-stabilization more complicated, and sometimes even impossible. In this paper, we investigate the gap in terms of requirements and efficiency when considering a directed graph instead of an undirected one as network topology for a self-stabilizing algorithm. Our case study is a variant of a synchronous unison algorithm proposed by Arora et al. ; the synchronous unison being a clock synchronization problem.

Details DOI

I&C Journal 2019 Journal Article

The first fully polynomial stabilizing algorithm for BFS tree construction

Alain Cournier
Stéphane Rovedakis
Vincent Villain

The construction of a spanning tree is a fundamental task in distributed systems which allows to resolve other tasks (i. e. , routing, mutual exclusion, network reset). In this paper, we are interested in the problem of constructing a Breadth First Search (BFS) tree. Stabilization is a versatile technique which ensures that the system recovers a correct behavior from an arbitrary global state resulting from transient faults. A fully polynomial algorithm has a round complexity in O ( d a ) and a step complexity in O ( n b ) where d and n are the diameter and the number of nodes of the network and a and b are constants. We present the first fully polynomial stabilizing algorithm constructing a BFS tree under a distributed daemon. Moreover, as far as we know, it is also the first fully polynomial stabilizing algorithm for spanning tree construction. Its round complexity is in Θ ( d 2 ) and its step complexity is in O ( n 6 ).

Details DOI

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.

Details DOI

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.

Details DOI

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.

Details DOI

TCS Journal 2011 Journal Article

How to improve snap-stabilizing point-to-point communication space complexity?

Alain Cournier
Swan Dubois
Vincent Villain

A snap-stabilizing protocol, starting from any configuration, always behaves according to its specification. In this paper, we are interested in the message forwarding problem in a message-switched network in which the system resources must be managed in order to deliver messages to any processor of the network. To this end, we use the information provided by a routing algorithm. In the context of an arbitrary initialization (due to stabilization), this information may be corrupted. In Cournier et al. (2009) [1], we show that there exist snap-stabilizing algorithms for this problem (in the state model). This implies that we can request the system to begin forwarding messages without losses even if routing information is initially corrupted. In this paper, we propose another snap-stabilizing algorithm for this problem which improves the space complexity of the one in Cournier et al. (2009) [1].

Details DOI

TAAS Journal 2009 Journal Article

Light enabling snap-stabilization of fundamental protocols

Alain Cournier
Stephane Devismes
Vincent Villain

In this article, we show that some fundamental self- and snap-stabilizing wave protocols (e.g., token circulation, PIF, etc.) implicitly assume a very light property that we call BreakingIn. We prove that BreakingIn is strictly induced by self- and snap-stabilization. Combined with a transformer, BreakingIn allows to easily turn the non-fault-tolerant versions of those protocols into snap-stabilizing versions. Unlike the previous solutions, the transformed protocols are very efficient and work at least with the same daemon as the initial versions extended to satisfy BreakingIn. Finally, we show how to use an additional property of the transformer to design snap-stabilizing extensions of those fundamental protocols like Mutual Exclusion.

Details DOI