We present the first polynomial self-stabilizing algorithm for finding a (2/3)-approximation of a maximum matching in a general graph. The previous best known algorithm has been presented by Manne et al. and has a sub-exponential time complexity under the distributed adversarial daemon. Our new algorithm is an adaptation of the Manne et al. algorithm and works under the same daemon, but with a time complexity in O(n^3) moves. Moreover, our algorithm only needs one more boolean variable than the previous one, thus as in the Manne et al. algorithm, it only requires a constant amount of memory space (three identifiers and two booleans per node).

Recently, virtual backbones have been extensively used in wireless ad-hoc networks for various applications such as routing, route maintenance, broadcasting or scheduling. In wireless ad-hoc and sensor networks, a Connected Dominating Set (CDS) is useful as a virtual backbone due to the absence of fixed infrastructure or centralized management. Most of CDS construction methods seek to minimize the size of the backbone. Nevertheless, other constraints than reducing the number of nodes can be considered. In that case, it is more interesting to consider nodes' weights (according to a specific purpose) and to reduce the total backbone's weight. This construction is called a Low Weight Connected Dominating Set (LWCDS). In this paper, we present a self-stabilizing distributed algorithm for the construction of a LWCDS. The self-stabilizing property confers to our algorithm the ability to recover in a finite time after a transient fault. Our algorithm is evaluated through extensive simulations that show the efficiency of our solution in different contexts and the large possible applications of our algorithm. We also introduce two new evaluation criteria to evaluate the algorithms of CDS construction in the specific context of mobility.

The energy is a critical resource in Wireless Sensor Networks that impacts on networks lifetime. In this paper, we propose a distributed self-stabilizing algorithm of topology control to preserve energy in case of communications by broadcast. The topology control is achieved by the reduction of the transmission power of the nodes in the network. The self-stabilizing property is a very desirable property in Wireless Sensor Networks that guarantees to reach a correct behavior in a finite number of steps, regardless of its initial state. Our solution is validated by extensive simulations. The obtained results show the efficiency of our solution in case of communication by broadcast.

Wireless Sensor Networks lifetime mainly depends on energy saving efficiency. In this paper, we propose an energy-efficient self-stabilizing topology control protocol for WSN. We reduce the transmission power of each node so as to maintain network connectivity while saving maximum energy. Besides, we propose an approximation algorithm for minimum weighted connected dominating set that builds a virtual backbone formed by sensors with maximum energy. This backbone is used for efficient routing purpose. Through our simulation results, we show the efficiency of our proposed algorithm.

We propose a fully decentralized algorithm that constructs and maintains clusters over a network. This algorithm maintains a stable size within the clusters among a network subject to frequent connection and disconnection. We use the notion of a circulating token that collects data (called a circulating word). This token moves according to a random walk scheme. The aim of the algorithm is to adapt solutions that use random walks and circulating words to large scale networks.

We introduce a new model for distributed algorithms designed for large scale systems that need a low-overhead solution to allow the processes to communicate with each other. We assume that every process can communicate with any other process provided it knows its identifier, which is usually the case in e.g. a peer to peer system, and that nodes may arrive or leave at any time. To cope with the large number of processes, we limit the memory usage of each process to a small constant number of variables, combining this with previous results concerning failure detectors and resource discovery. We illustrate the model with a self-stabilizing algorithm that builds and maintains a spanning tree topology. We provide a formal proof of the algorithm and the results of experiments on a cluster.

A long-term trend in high-performance computing is the increasing number of nodes in parallel computing platforms, which entails a higher failure probability. Fault tolerant programming environments should be used to guarantee the safe execution of critical applications. Research in fault tolerant MPI has led to the development of several fault tolerant MPI environments. Different approaches are being proposed using a variety of fault tolerant message passing protocols based on coordinated checkpointing or message logging. The most popular approach is with coordinated checkpointing. In the literature, two different concepts of coordinated checkpointing have been proposed: blocking and nonblocking. However they have never been compared quantitatively and their respective scalability remains unknown. The contribution of this paper is to provide the first comparison between these two approaches and a study of their scalability. We have implemented the two approaches within the MPICH environments and evaluate their performance using the NAS parallel benchmarks.