Papers by Christian Boulinier
Bookmarks Related papers MentionsView impact
We introduce a simple tool called the wavelet (or, r-wavelet) scheme. Wavelets deals with coordin... more We introduce a simple tool called the wavelet (or, r-wavelet) scheme. Wavelets deals with coordination among processes which are at most r hops away of each other. We present a selfstabilizing solution for this scheme. Our solution requires no underlying structure and works in arbritrary anonymous networks, i.e., no process identifier is required. Moreover, our solution works under any (even unfair) daemon. Next, we use the wavelet scheme to design self-stabilizing layer clocks. We show that they provide an efficient device in the design of local coordination problems at distance r, i.e., r-barrier synchronization and r-local resource allocation (LRA) such as r-local mutual exclusion (LME), r-group mutual exclusion (GME), and r-Reader/Writers. Some solutions to the r-LRA problem (e.g., r-LME) also provide transformers to transform algorithms written assuming any r-central daemon into algorithms working with any distributed daemon.
Bookmarks Related papers MentionsView impact
Lecture Notes in Computer Science, 2006
ABSTRACT We address the self-stabilizing unison problem in tree networks. We propose two self-sta... more ABSTRACT We address the self-stabilizing unison problem in tree networks. We propose two self-stabilizing unison protocols without any reset correcting system. The first one, called Protocol SU_Min, being scheduled by a synchronous daemon, is self-stabilizing to synchronous unison in at most D steps, where D is the diameter of the network. The second one, Protocol WU_Min, being scheduled by an asynchronous daemon, is self-stabilizing to asynchronous unison in at most D rounds. Moreover, both are optimal in space. The amount of required space is independent of any local or global information on the tree. Furthermore, they work on dynamic trees networks, in which the topology may change during the execution.
Bookmarks Related papers MentionsView impact
2008 IEEE International Symposium on Parallel and Distributed Processing, 2008
Bookmarks Related papers MentionsView impact
Lecture Notes in Computer Science
ABSTRACT We propose the first snap-stabilizing wave algorithm for anonymous networks. In the wors... more ABSTRACT We propose the first snap-stabilizing wave algorithm for anonymous networks. In the worst case, a process decides in O(n + D) time units, where n and D are the number of process and the diameter of the network, respectively. The proposed algorithm uses a self-stabilizing underlying unison protocol. If the underlying unison is stabilized when a process request a wave, then a decide event occurs in an optimal time, i.e., O(D) time units. The proposed solution is generic in the sense that, it can be used for any static or dynamic scheme which is feasible in an anonymous network. In particular, as an application of our scheme, we provide a snap-stabilizing causal atomic broadcast for anonymous networks, which can be used as a pipeline of messages.
Bookmarks Related papers MentionsView impact
Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, 2004
We propose a general self-stabilizing scheme for solving any synchronization problem whose safety... more We propose a general self-stabilizing scheme for solving any synchronization problem whose safety specification can be defined using a local property. We demonstrate the versatility of our scheme by showing that very memory-efficient solutions to many well-known problems (e.g., asynchronous phase clock, local mutual exclusion, local reader-writers, and local group mutual exclusion) can be derived using the proposed framework. We
Bookmarks Related papers MentionsView impact
Computing Research Repository - CORR, 2007
How to pass from local to global scales in anonymous networks? In such networks, how to organize ... more How to pass from local to global scales in anonymous networks? In such networks, how to organize a self-stabilizing propagation of information with feedback? From Angluin's results, the deterministic leader election is impossible in general anonymous networks. Thus, it is impossible to build a rooted spanning tree. In this paper we show how to use Unison to design a self- stabilizing barrier synchronization in an anonymous network. We show that the communication structure of this barrier synchronization designs a self-stabilizing wave stream, or pipelined wave, in anonymous networks. We introduce two variants of waves: Strong Wave and Wavelet. Strong waves can be used to solve the idempotent r-operator parametrized problem, which implies well known problems like depth-first search tree construction - this instance requires identities for the processors. Wavelets deal with ρ-distance computation. We show how to use Unison to design a self-stabilizing strong wave stream, and wave...
Bookmarks Related papers MentionsView impact
Algorithmica, 2007
Bookmarks Related papers MentionsView impact
Uploads
Papers by Christian Boulinier