International audience

Stream Processing Systems (SPSs) are designed to process continuous streams of events, often under highly variable input rates. Although prior work has explored dynamic operator replication, many existing approaches lack generalizability and perform suboptimally across diverse scenarios. In this article, we present MMP-SPS, a predictive self-adaptive framework that extends extends our prior PA-SPS system by introducing a multi-window control loop, support for multiple prediction models, and online model selection via RMSE-based evaluation and multi-armed bandits. Targeting environments with high-volume and fluctuating data streams, such as social media analytics and network traffic monitoring, the framework dynamically selects the most suitable model based on real-time workload characteristics using a reinforcement learning (RL) strategy. To prove the validity of our system, we deployed an implementation of MMP-SPS based on Apache Storm, and we evaluated it on Google Cloud Platform against real-world datasets. Experimental results show substantial improvements in latency, throughput, and resource utilization compared to static and single-model baselines. These findings underscore the potential of multi-model predictive adaptation for scalable and robust stream processing under dynamic conditions.

Some applications, like round-based consensus algorithms, require all the nodes from a system to send a message to the same node (the leader) at the same time. In a Mobile Ad-Hoc Network (MANET), this situation is likely to cause collisions and the loss of the messages converging to the leader. The loss of messages is critical in such a situation, since the leader needs to receive a quorum of messages to make a decision. This pattern of communications, called convergecast, can be trivially implemented with a unicast primitive. However, we show that a popular MANET unicast algorithm like Optimized Link State Routing (OLSR) loses a lot of messages, even in the presence of MAC-level collision avoidance mechanisms like CSMA/CA. We propose a new convergecast algorithm that locally schedules answers to a query in a fully distributed manner, in order to avoid their colliding with each other, and that aggregates these answers in order to further decrease the probability of collisions. We show that our algorithm creates far fewer collisions and retries than OLSR, allowing applications like consensus algorithms to reach their quorum sooner.

In the cloud computing context, several applications run concurrently over the same underlying physical infrastructure. Phase-based algorithms are key building blocks for many distributed applications such as DBMS or transaction validation services. Indeed, these applications rely on consensus or atomic validation solved by phase-based algorithms (Paxos, ZAB, two-phase commit, etc.). In each phase, at least one participant broadcasts a message and waits for the responses from a subset of the recipients before starting the next phase. For a given phase-based algorithm, it is then possible to predict future communications for each node. Based on this observation, we propose a generic and low-intrusive solution to save network bandwidth in a cloud context by aggregating messages sent by several applications in an opportunistic way. We propose a new API to easily apply our mechanism with applications using phase-based algorithms. The core of this API is the overloading of the send primitive, where the users can define a tradeoff between message saving and latency degradation. We evaluate our mechanisms using multiple instances of the same algorithm (three variants of the Paxos consensus and the Zookeeper Atomic Broadcast algorithm) running concurrently. Our results show that a good tuning of the new send primitive saves up to 30% of bandwidth with only a 5% degradation in latency.

This paper summarizes the PhD thesis and the 10 associated publications on the optimization of network slice placement in large-scale distributed infrastructures by focusing on online heuristics and approaches based on Deep Reinforcement Learning (DRL). First, we rely on Integer Linear Programming (ILP) to propose a data model for on-Edge and on-network slice placement. Second, we leverage an approach called Power of Two Choices (P2C) to propose an online heuristic adapted to support placement on large-scale distributed infrastructures while incorporating Edge-specific constraints like latency. Finally, we investigate the use of Machine Learning (ML) methods, specifically DRL, to increase the scalability and automation of network slice placement by considering a multi-objective optimization approach to the problem. We will go through the extensive evaluation work that provide encouraging results about the advantages of the proposed approaches when used in realistic network scenarios.

In the cloud computing context, several applications run concurrently over the same underlying physical infrastructure. Phase-based algorithms are key building blocks for many distributed applications such as DBMS or transaction validation services. Indeed, these applications rely on consensus or atomic validation solved by phase-based algorithms (Paxos, ZAB, two-phase commit …). In each phase, at least one participant broadcasts a message and waits for the responses from a subset of the recipients before starting the next phase. For a given phase-based algorithm, it is then possible to predict future communications for each node. Based on this observation, we propose a generic and low-intrusive solution to save network bandwidth in a cloud context by aggregating messages sent by applications in an opportunistic way. We propose a new API to easily apply our mechanism with applications using phase-based algorithms. The core of this API is the overloading of the send primitive where the users can define a trade-off between message saving and latency degradation. We evaluate our mechanisms using multiple instances of the same algorithm (3 variants of the Paxos consensus and the Zookeeper Atomic Broadcast algorithm) running concurrently. Our results show that a good tuning of the new send primitive saves a large amount of bandwidth with little latency degradation.

Fog Computing is a paradigm aiming to decentralize the Cloud by geographically distributing away computation, storage and network resources as well as related services. This notably reduces bottlenecks and data movement. However, managing Fog resources is a major challenge because the targeted systems are large, geographically distributed, unreliable and very dynamic. Cloud systems are generally managed via centralized autonomic controllers automatically optimizing both application QoS and resource usage. To leverage the self-management of Fog resources, we propose to orchestrate a fleet of autonomic controllers in a decentralized manner, each with a local view of its own resources. In this paper, we present our SeMaFoR (Self-Management of Fog Resources) vision that aims at collaboratively operating Fog resources. SeMaFoR is a generic approach made of three cornerstones: an Architecture Description Language for the Fog, a collaborative and consensual decision-making process, and an automatic coordination mechanism for reconfiguration.

Cloud providers offer several types of Virtual Machines (VMs) in diverse markets, with different guarantees in terms of availability and reliability. Among them, the most popular market models are the on-demand and the spot. On-demand VMs are allocated for a fixed cost per time, and their availability is ensured during the whole execution. On the other hand, in the spot market, VMs are offered with a huge discount, but their availability fluctuates according to cloud’s current demand that can terminate or hibernate a spot VM at any time. Furthermore, to cope with workload variations, cloud providers have also introduced the concept of burstable VMs, which can burst up their CPU performance during a limited period of time. In this work, we present the Burst Hibernation-Aware Dynamic Scheduler (Burst-HADS), a framework that executes Bag-of-Tasks applications with deadline constraints by exploiting both spot and on-demand burstable VMs, aiming at minimizing both the monetary cost and the execution time. Performance results on Amazon EC2 show that Burst-HADS reduces the monetary cost and meets the application deadline even in spot hibernation scenarios, when compared to other approaches from the related literature which uses only spot and non-burstable on-demand instances.

Mobile Ad-Hoc Networks (MANETs) assume no previous network infrastructure and wireless communication between mobile and heterogeneous nodes. An efficient broadcast protocol is therefore paramount. When some neighborhood information is available beforehand through discovery, building a virtual overlay like MultiPoint Relay (MPR) can help improve reliability and decrease cost in messages. However, MPR overlays tend to unfairly stress specific nodes who happen to be well-connected, causing their premature death. We propose the alternating MPR protocol that strives to build several disjoint relay sets for each node, allowing broadcast messages to use each of them in turn. Our simulation of the full network stack of systems of various densities shows that alternating MPR spreads energy costs more evenly across the system, without harming reliability and at little cost in number of messages, allowing battery-powered nodes to survive longer.

Under the coordination of a central server, Federate Learning (FL) enables a set of clients to collaboratively train a global machine learning model without exchanging their local data. When such clients have powerful machines, it is called cross-silo FL, and they store their data in private repositories denoted silos. We are interested in this paper in cross-silo FL where silos are geographically located in different regions of multi-cloud providers. Thus, aiming at minimizing financial costs and execution times of a cross-silo FL application, we propose a model based on a scheduling problem mathematical formulation, which receives as input both the application parameters and the cloud providers' resource features where clients' data are stored and renders the best assignment of clients and server to virtual machines. This formulation is part of a framework proposal to execute FL applications in different cloud providers. Taking as a use case a Tumor-Infiltrating Lymphocytes Classification problem, an FL application whose clients' datasets spread over different cloud providers' data repositories, evaluation results show that our model is scalable and improves the execution time and financial costs of the FL application by up to 53.70% and 48.34% in a scenario with 50 clients, executing in around 200 seconds, when compared to results where VMs are randomly selected. Experimental results with client silos in different Google (GCP) and Amazon (AWS) cloud regions also confirmed the effectiveness of our proposed model in a real multi-cloud environment.

Stream Processing Systems (SPSs) can present significant fluctuation in input rate. To address this issue, some existing solutions propose reconfiguring the SPS by replicating its operators. However, such reconfiguration usually induces a high system downtime cost. Moreover, reconfiguration decisions are based only on resource utilization without balancing the load between replicas. We propose in this paper a predictive SPS that dynamically defines the necessary number of replicas of each operator based not only on the current resource utilization and input rate variation but also on the events that, due to the operator's overloading, could not be processed yet and are, thus, kept in the operator's queue. In addition, our SPS implements a load balancer that distributes incoming events more evenly among replicas of an operator. Our solution has been integrated into Storm. To avoid system reconfiguration downtime, our SPS preallocates a pool of replicas where each of them can be activated or deactivated based on per operator input load predictions. Using real traffic traces with different applications, we have conducted experiments on Google Cloud Platform (GCP), evaluating our SPS and comparing it with Storm and DABS-Storm.

Network Slice placement with the problem of allocation of resources from a virtualized substrate network is an optimization problem which can be formulated as a multi-objective Integer Linear Programming (ILP) problem. However, to cope with the complexity of such a continuous task and seeking for optimality and automation, the use of Machine Learning (ML) techniques appear as a promising approach. We introduce a hybrid placement solution based on Deep Reinforcement Learning (DRL) and a dedicated optimization heuristic based on the “Power of Two Choices” principle. The DRL algorithm uses the so-called Asynchronous Advantage Actor Critic (A3C) algorithm for fast learning, and Graph Convolutional Networks (GCN) to automate feature extraction from the physical substrate network. The proposed Heuristically-Assisted DRL (HA-DRL) allows for the acceleration of the learning process and substantial gain in resource usage when compared against other state-of-the-art approaches, as evidenced by evaluation results.

We consider online learning for optimal network slice placement under the assumption that slice requests arrive according to a non-stationary Poisson process. We propose a framework based on Deep Reinforcement Learning (DRL) combined with a heuristic to design algorithms. We specifically design two pure-DRL algorithms and two families of hybrid DRL-heuristic algorithms. To validate their performance, we perform extensive simulations in the context of a large-scale operator infrastructure. The evaluation results show that the proposed hybrid DRL-heuristic algorithms require three orders of magnitude of learning episodes less than pure-DRL to achieve convergence. This result indicates that the proposed hybrid DRL-heuristic approach is more reliable than pure-DRL in a real non-stationary network scenario.

We propose to demonstrate a network slice placement optimization solution based on Deep Reinforcement Learning (DRL), referred to as Heuristically-controlled DRL, which uses a heuristic to control the DRL algorithm convergence. The solution is adapted to realistic networks with large scale and under non-stationary traffic conditions (namely, the network load). We demonstrate the applicability of the proposed solution and its higher and stable performance over a non-controlled DRL-based solution. Demonstration scenarios include full online learning with multiple volatile network slice placement request arrivals.

This paper presents CEL, a new distributed eventual leader election algorithm for dynamic networks, which exploits topological information to improve the choice of a central leader and reduce message exchanges. The algorithm has a cross-layer neighbors detection, with a neighbor-aware mechanism, to improve the sharing of topological knowledge and elect a central leader faster. It uses a self-pruning mechanism based on topological knowledge, combined with probabilistic gossip, to improve the performance of broadcast propagation. Evaluations were conducted on the OMNeT++ environment, simulating re-alistic MANET with interference, collision, and messages loss. Using different parameters values, we have compared CEL to Gomez-Calzado et al. algorithm [1], on the Random Walk and the Truncated Levy Walk mobility models. The results show better performances than [1], including fewer messages sent, shortest paths to the leader, and a more stable algorithm.

Stream processing systems (SPS) have to deal with highly dynamic scenarios where its adaptation is mandatory in order to accomplish realistic applications requirements. In this work, we propose a new adaptive SPS for real-time processing that, based on input data rate variation, dynamically adapts the number of active operator replicas. Our SPS extends Storm by pre-allocating, for each operator, a set of inactive replicas which are activated (or deactivated) when necessary without the Storm reconfiguration cost. We exploit the MAPE model and define a new metric that aggregates the value of multiple metrics to dynamically changes the number of replicas of an operator. We deploy our SPS over Google Cloud Platform and results confirm that our metric can tolerate highly dynamic conditions, improving resource usage while preserving high throughput and low latency.

FIFO broadcast provides application ordering semantics of messages broadcast by the same sender and have been mostly implemented on top of unreliable static networks. In this article, we propose a round-based FIFO broadcast algorithm with both termination detection and bounded message size for dynamic networks with recurrent connectivity (Class$\mathcal{TC}^{\mathcal{R}}$of Time-varying Graph formalism [1]). Initially, processes only know the number of processes$N$in the system and their identifier. Due to the dynamics of the network links, messages can be lost. Since no unbounded timestamp is used to identify a message, its size is bounded to$2N+O(log(N))+msgSize$bits where msgSize is the bound size in bits of the broadcast data. We also present a FIFO atomic broadcast algorithm for dynamic networks with recurrent connectivity that uses the proposed FIFO broadcast and deliver primitives. This algorithm provides causal total order broadcast primitives.

The protein structure prediction is one of the key problems in Structural Bioinformatics. The protein function is directly related to its conformation and the folding can provide to researchers better understandings about the protein roles in the cell. Several computational methods have been proposed over the last decades to tackle the problem. In this paper, we propose an ab initio algorithm with database information for the protein structure prediction problem. We do so by designing some versions of a multi-agent system that use concepts of dynamic distributed evolutionary algorithms to speed up and improve the optimization by better adapting the algorithm to the target protein. The dynamic strategy consists of auto-adapting the number of optimization agents according to the needs and current status of the optimization process. The system is able to scale in/out itself depending on some diversity criteria. The algorithms also take advantage of structural knowledge from the Protein Data Bank to better guide the search and constraint the state space. To validate our computational strategies, we tested them on a set of eight protein sequences. The obtained results were topologically compatible with the experimental correspondent ones, thus corroborating the promising performance of the strategies.

We propose an online heuristic algorithm for the problem of network slice placement optimization. The solution is adapted to support placement on large scale networks and integrates Edge-specific and URLLC constraints. We rely on an approach called the "Power of Two Choices" to build the heuristic. The evaluation results show the good performance of the heuristic that solves the problem in few seconds under a large scale scenario. The heuristic also improves the acceptance ratio of network slice placement requests when compared against a deterministic online Integer Linear Programming (ILP) solution.

Network Slicing has its roots in Network Function Virtualization (NFV) allowing high flexibility in the delivery of end-to-end network services. To achieve Network Slicing promises on efficiency, Network Slice Providers have to ensure optimized resource utilization and to guarantee Quality of Service when managing the life-cycle of a Network Slice. We focus in this paper on Network Slice Placement, intimately related to the VNF Placement and Chaining problem. In contrary to most studies related to VNF placement, we deal with the most complete and complex Network Slice topologies and we pay special attention to the geographic location of Network Slice Users. We propose a data model adapted to Integer Linear Programming. Extensive numerical experiments assess the relevance of taking into account the user location constraints.

This paper proposes an algorithm that eventually elects a leader for each connected component of a dynamic network where nodes can move or fail by crash. A node only communicates with nodes in its transmission range and locally keeps a global view, denoted topological knowledge, of the communication graph of the network and its dynamic evolution. Every change in the topology or in nodes membership is detected by one or more nodes and propagated over the network, updating thus the topological knowledge of the nodes. As the choice of the leader has an impact on the performance of applications that use an eventual leader election service, our algorithm, thanks to nodes topological knowledge, exploits the closeness centrality as the criterion for electing a leader. Experiments were conducted on top of PeerSim simulator [1], comparing our algorithm to a representative flooding algorithm. Performance results show that our algorithm outperforms the flooding one when considering leader choice stability, number of messages, and average distance to the leader.

Cloud platforms offer different types of virtual machines which ensure different guarantees in terms of availability and volatility, provisioning the same resource through multiple pricing models. For instance, in Amazon EC2 cloud, the user pays per hour for on-demand instances while spot instances are unused resources available for a lower price. Despite the monetary advantages, a spot instance can be terminated or hibernated by EC2 at any moment. Using both hibernationprone spot instances (for cost sake) and on-demand instances, we propose in this paper a static scheduling for applications which are composed of independent tasks (bag-of-task) with deadline constraints. However, if a spot instance hibernates and it does not resume within a time which guarantees the application's deadline, a temporal failure takes place. Our scheduling, thus, aims at minimizing monetary costs of bag-of-tasks applications in EC2 cloud, respecting its deadline and avoiding temporal failures. Performance results with task execution traces, configuration of Amazon EC2 virtual machines, and EC2 market history confirms the effectiveness of our scheduling and that it tolerates temporal failures.

A causal broadcast ensures that messages are delivered to all nodes (processes) preserving causal relation of the messages. In this paper, we propose a causal broadcast protocol for distributed systems whose nodes are logically organized in a virtual hypercube-like topology called VCube. Messages are broadcast by dynamically building spanning trees rooted in the message's source node. By using multiple trees, the contention bottleneck problem of a single root spanning tree approach is avoided. Furthermore, different trees can intersect at some node. Hence, by taking advantage of both the out-of-order reception of causally related messages at a node and these paths intersections, a node can delay to one or more of its children in the tree, the forwarding of the messages whose some causal dependencies it knows that the children in question can not satisfy yet. Such a delay does not induce any overhead. Experimental evaluation conducted on top of PeerSim simulator confirms the communication effectiveness of our causal broadcast protocol in terms of latency and message traffic reduction.

We consider a single machine, a set of unit-time jobs, and a set of unit-time errors. We assume that the time-slot at which each error will occur is not known in advance but, for every error, there exists an uncertainty area during which the error will take place. In order to find if the error occurs in a specific time-slot, it is necessary to issue a query to it. In this work, we study two problems: (i) the error-query scheduling problem, whose aim is to reveal enough error-free slots with the minimum number of queries, and (ii) the lexicographic error-query scheduling problem where we seek the earliest error-free slots with the minimum number of queries. We consider both the off-line and the on-line versions of the above problems. In the former, the whole instance and its characteristics are known in advance and we give a polynomial-time algorithm for the error-query scheduling problem. In the latter, the adversary has the power to decide, in an on-line way, the time-slot of appearance for each error. We propose then both lower bounds and algorithms whose competitive ratios asymptotically match these lower bounds.

This paper presents a new unreliable failure detector, called the Impact failure detector (FD), that, contrarily to the majority of traditional FDs, outputs a trust level value which expresses the degree of confidence in the system. An impact factor is assigned to each process and the trust level is equal to the sum of the impact factors of the processes not suspected of failure. Moreover, a threshold parameter defines a lower bound value for the trust level, over which the confidence in the system is ensured. In particular, we defined a flexibility property that denotes the capacity of the Impact FD to tolerate a certain margin of failures or false suspicions, i.e. its capacity of considering different sets of responses that lead the system to trusted states. The Impact FD is suitable for systems that present node redundancy, heterogeneity of nodes, clustering feature and allow a margin of failures which does not degrade the confidence in the system. The paper also includes a timer-based distributed algorithm which implements an Impact FD, as well as its proof of correctness, for systems whose links are lossy asynchronous or for those whose all (or some) links are eventually timely. Performance evaluation results, based on PlanetLab (Planetlab. http://www.planet-lab.org. ‘Online. Access date: 16 September 2016’) traces, confirm the degree of flexible applicability of our FD and that, due to the accepted margin of failure, both failures and false suspicions are more tolerated when compared to traditional unreliable FDs.

An emerging usage is to rely on mobile devices (Smartphones or tablets) for large-scale events. They can be used for many applications like live voting or chatting, but also to access all the data related to an event. However, in such case, handling mobile devices trying to access data simultaneously is difficult. A Wi-Fi access point can only handle a limited amount of devices. Current solutions, relying on pre-loading data on the devices or over-sizing the network equipments are not satisfying and are not even always possible. We propose an approach that leverages the capability of mobile devices to interact directly through device-to-device (D2D) communications. Our solution can be tuned to choose the right level of parallelization to cope with radio interferences, it also provides the ability to adjust the trade-off between efficiency and energy consumption. We evaluate our approach using a discrete event simulator. The simulation results show that our approach using D2D communications brings a 30% gains.

The search for service providers (e.g., ambulance, fire truck, etc.) after a disaster, must take place within a short time. Therefore, service discovery protocol which looks for providers that can attend victims, respecting time constraints, is crucial. In such a situation, a commonly solution for ensuring network connectivity between victims and providers is ad hoc networks (MANET), composed by battery-operated mobile nodes of persons (victims or not). However, an efficient service discovery protocol must care about energy consumption of mobile nodes and also prevent useless movement of providers. These are the aims of the Resource Reservation Protocol (ΔRRP), presented in this paper. Applying both Gauss-Markov [1] and Mission Critical Mobility [2] models to characterize human mobility, performance evaluation results on the Network Simulator NS2 confirm the effectiveness of ΔRRP protocol when compared to other protocols.

While virtualization only introduces a small overhead on machines with few cores, this is not the case on larger ones. Most of the overhead on the latter machines is caused by the Non-Uniform Memory Access (NUMA) architecture they are using. In order to reduce this overhead, this paper shows how NUMA placement heuristics can be implemented inside Xen. With an evaluation of 29 applications on a 48-core machine, we show that the NUMA placement heuristics can multiply the performance of 9 applications by more than 2.

In the last few years, there has been an explosive growth of the number of mobile devices. This has come with a plethora of new applications and usages. Among these new usages, there are many occasions for which a content has to be disseminated to a large number of mobile devices (e.g., large-scale events providing a multi-media support, video streaming, \ldots). To cope with network bandwidth limitations, new approaches, leveraging device-to-device (D2D) communications have emerged. Obviously, one of the main problem that D2D-based approaches have to face is the energy consumption. Furthermore, there is usually a huge heterogeneity among the devices: some may benefit of a good, fully charged battery while others may have only a couple of hours left before a power failure; the network bandwidth can also differ a lot. In this paper, based on a previous work, we propose an approach to take into account devices heterogeneity while disseminating data using D2D communications. Our simulations show that it is possible to spare the weakest batteries without wearing too much the good ones nor degrading too much the performance. Furthermore, taking into account the devices bandwidth capabilities can help to increase the dissemination speed.

In this paper we present VCube-PS, a topic-based Publish/Subscribe system built on the top of a virtual hypercube-like topology. Membership information and published messages to subscribers (members) of a topic group are broadcast over dynamically built spanning trees rooted at the message's source. For a given topic, delivery of published messages respects causal order. Performance results of experiments conducted on the PeerSim simulator confirm the efficiency of VCube-PS in terms of scalability, latency, number, and size of messages when compared to a single rooted, not dynamically, tree built approach.

The failure detector abstraction has been used to solve agreement problems in asynchronous systems prone to crash failures, but so far it has mostly been used in static and complete networks. This paper aims to adapt existing failure detectors in order to solve agreement problems in unknown, dynamic systems. We are specifically interested in the k-set agreement problem. The problem of k-set agreement is a generalization of consensus where processes can decide up to k different values. Although some solutions to this problem have been proposed in dynamic networks, they rely on communication synchrony or make strong assumptions on the number of process failures. In this paper we consider unknown dynamic systems modeled using the formalism of Time-Varying Graphs, and extend the definition of the existing$\Pi \Sigma _{x,y}$failure detector to obtain the$\Pi \Sigma _{\bot, x,y}$failure detector, which is sufficient to solve k-set agreement in our model. We then provide an implementation of this new failure detector using connectivity and message pattern assumptions. Finally, we present an algorithm using$\Pi \Sigma _{\bot, x,y}$to solve k-set agreement.

The proliferation of GPS-enabled devices leads to the massive generation of geotagged data sets recently known as Big Location Data. It allows users to explore and analyse data in space and time, and requires an architecture that scales with the insertions and location-temporal queries workload from thousands to millions of users. Most large scale key-value data storage solutions only provide a single one-dimensional index which does not natively support efficient multidimensional queries. In this paper, we propose GeoTrie, a scalable architecture built by coalescing any number of machines organized on top of a Distributed Hash Table. The key idea of our approach is to provide a distributed global index which scales with the number of nodes and provides natural load balancing for insertions and location-temporal range queries. We assess our solution using the largest public multimedia data set released by Yahoo! which includes millions of geotagged multimedia files.

Building an infrastructure for Exascale applications requires, in addition to many other key components, a stable and efficient failure detector. This paper describes the design and evaluation of a robust failure detector, able to maintain and distribute the correct list of alive resources within proven and scalable bounds. The detection and distribution of the fault information follow different overlay topologies that together guarantee minimal disturbance to the applications. A virtual observation ring minimizes the overhead by allowing each node to be observed by another single node, providing an unobtrusive behavior. The propagation stage is using a non-uniform variant of a reliable broadcast over a circulant graph overlay network, and guarantees a logarithmic fault propagation. Extensive simulations, together with experiments on the Titan ORNL supercomputer, show that the algorithm performs extremely well, and exhibits all the desired properties of an Exascale-ready algorithm.

Distributed Prefix Tree indexing structures on top of peer-to-peer overlays provide a scalable solution to support range queries and proximity queries for Big Data applications. However, the latency of current maintenance protocols impacts very negatively on main operations like data insertions. This paper presents a new maintenance protocol that anticipates every data insertion on provisional child nodes. A performance evaluation conducted on the Prefix Hash Tree and Free Split shows that Free Split significantly reduces maintenance overheads, and therefore improves query response time.

Due to the nature of ubiquitous systems, nodes (e.g., Sensors) are frequently prone to failures. Such systems must, therefore, present self-healing capabilities in order to detect failures and make the necessary adjustments to prevent their impact on applications. In such a context, this work proposes a new and flexible unreliable failure detector, denoted as the Impact failure detector (FD), for self-healing system in ubiquitous environments. The output of the Impact FD concerns the confidence in the system as a whole. By expressing the relevance of each node by an impact factor value as well as a margin of acceptable failures of the system, the Impact FD enables the user to tune the failure detection configuration in accordance with the requirements of the application: in some scenarios, the failure of low impact or redundant nodes does not jeopardize the confidence in the system, while the crash of a high impact factor one may seriously affect it. Either a softer or stricter monitoring is thus possible. The performance evaluation results using real Planet Lab traces confirm the degree of flexible applicability of our failure detector and, that due to the margin of failure, the number of false responses may be reduced when it is compared with traditional unreliable failure detectors.

Generalized distributed mutual exclusion algorithms allow processes to concurrently access a set of shared resources. However, they must ensure an exclusive access to each resource. In order to avoid deadlocks, many of them are based on the strong assumption of a prior knowledge about conflicts between processes' requests. Some other approaches, which do not require such a knowledge, exploit broadcast mechanisms or a global lock, degrading message complexity and synchronization cost. We propose in this paper a new solution for shared resources allocation which reduces the communication between non-conflicting processes without a prior knowledge of processes conflicts. Performance evaluation results show that our solution improves resource use rate by a factor up to 20 compared to a global lock based algorithm.

Failure detection is a crucial service for dependable distributed systems. Traditional failure detector implementations usually target homogeneous and static configurations, as their performance relies heavily on the connectivity of each network node. In this paper we propose a new approach towards the implementation of failure detectors for large and dynamic networks: we study reputation systems as a means to detect failures. The reputation mechanism allows efficient node cooperation via the sharing of views about other nodes. Our experimental results show that a simple prototype of a reputation-based detection service performs better than other known adaptive failure detectors, with improved flexibility. It can thus be used in a dynamic environment with a large and variable number of nodes.

Failure detection plays a central role in the engineering of distributed systems. Furthermore, many applications have timing constraints and require failure detectors that provide quality of service (QoS) with some quantitative timeliness guarantees. Therefore, they need failure detectors that are fast and accurate. We introduce the Two-Windows Failure Detector (2W-FD), an algorithm able to react to sudden changes in network conditions, property that currently existing algorithms do not satisfy. We ran tests on real traces and compared the 2W-FD to state-of-art algorithms. Our results show that our algorithm presents the best performance in terms of speed and accuracy in unstable scenarios.

This work proposes a new and flexible unreliable failure detector, denoted Impact Failure Detector (FD), whose output gives the trust level of a set of processes. By expressing the relevance of each node by an impact factor value as well as an acceptable margin of failure in the system, the Impact FD enables the user to tune the failure detection configuration in accordance with the requirements of the application: in some scenarios, the failure of low impact or redundant nodes does not jeopardize the confidence in the system, while the crash resulting from a high impact factor may seriously affect it. Either a softer or stricter monitoring is thus possible. Performance evaluation results using real PlanetLab [1] traces confirm the degree of flexibility of our failure detector and that, due to the margin of failure, the number of false responses may be reduced when it is compared with traditional unreliable failure detectors.

Spatio-temporal range queries over Big Location Data aim to extract and analyze relevant data items generated around a given location and time. They require concurrent processing of massive and dynamic data flows. Current solutions for Big Location Data are ill-suited for continuous spatio-temporal processing because (i) most of them follow a batch processing model and (ii) they rely on spatial indexing structures maintained on a central master server. In this paper, we propose a scalable architecture for continuous spatio-temporal range queries built by coalescing multiple computing nodes on top of a Distributed Hash Table. The key component of our architecture is a distributed spatio-temporal indexing structure which exhibits low insertion and low index maintenance costs. We assess our solution with a public data set released by Yahoo! which comprises millions of geotagged multimedia files.

The k-set agreement problem is a generalization of the consensus problem where processes can decide up to k different values. Very few papers have tackled this problem in dynamic networks, and to the best of our knowledge, every algorithm proposed so far for k-set agreement in dynamic networks assumed synchronous communications or made strong failure pattern assumptions. Exploiting the formalism of the Time-Varying Graph model, this paper proposes a new quorum-based failure detector for solving k-set agreement in dynamic networks with asynchronous communications. We present two algorithms that implement this new failure detector using graph connectivity and message pattern assumptions. We also provide an algorithm for solving k-set agreement using our new failure detector.

Distributed storage systems have to ensure data availability and durability despite the occurrence of failures. To do so, many of them rely on replication mechanisms. We show that the layout of the data block copies on the nodes, chiefly the way the copies are scattered, has a major impact on the reparation speed and thus on the data loss ratio. In this paper, we propose an approach that provides the ability: (i) to finely tune the proportion of common content stored by the nodes, and (ii) to control the storage load distribution while creating new data block copies. We propose a simulation model that allows us to present a long-term study of the impact of the data block copies layout and the system's storage load on the data loss ratio.

In its classical form, a consistent replicated service requires all replicas to witness the same evolution of the service state. Assuming a message-passing environment with a majority of correct processes, the necessary and sufficient information about failures for implementing a general state machine replication scheme ensuring consistency is captured by the Ω failure detector.

Tolerating Byzantine failures in the context of cloud computing is costly. Traditional BFT protocols induce a fixed degree of replication for computations and are therefore wasteful. This paper explores probabilistic Byzantine tolerance, in which computation tasks are replicated on dynamic replication sets whose size is determined based on ensuring probabilistic thresholds of correctness. The probabilistic assessment of a trustworthy output by selecting reputable nodes allows a significant reduction in the number of nodes involved in each computation task. The paper further studies several reputation management policies, including the one used by BOINC as well as a couple of novel ones, in terms of their impact of the possible damage inflicted on the system by various Byzantine behavior strategies, and reports some encouraging insights.

With the advent of cloud architectures, virtualization has become a key mechanism. In clouds, virtual machines (VMs) offer both isolation and flexibility. This is the foundation of cloud elasticity, but it induces fragmentation of the physical resources, including memory. While each VM memory needs evolve during time, existing mechanisms used to dynamically adjust VMs memory are inefficient, and it is currently impossible to take benefit of the unused memory of VMs hosted by another host. In this paper we propose Puma, a mechanism that improves I/O intensive applications performance by providing the ability for a VM to entrust clean page-cache pages to other VMs having unsused memory. By reusing the existing page-cache data structures, Puma is very efficient to reclaim the memory lent to another VM. By being distributed, Puma increases the memory consolidation at the scale of a data center. In our evaluations made with TPC-C, TPC-H, BLAST and Postmark, we show that Puma can significantly boost the performance without impacting potential activity peaks on the lender.

Live streaming has become very popular. Many systems, such as justin.tv, have emerged. They aim to collect user live-streams and serve them to the viewers using broadcasting servers. However, the huge variation in the total number of viewers and the great heterogeneity among streams popularity generally implies over-provisioning, leading to an important resource waste. In this paper, we show that there is a trade-off between the number of servers involved to broadcast the streams and the bandwidth usage among the servers. We also stress the importance to predict streams popularity in order to efficiently place them on the servers. We propose POPS: a live streaming service using popularity predictions to map live-streams on the servers.

Cloud Computing provides a convenient means of remote on-demand and pay-per-use access to computing resources. However, its ad hoc management of quality-of-service and SLA poses significant challenges to the performance, dependability and costs of online cloud services. The paper precisely addresses this issue and makes a threefold contribution. First, it introduces a new cloud model, the SLAaaS (SLA aware Service) model. SLAaaS enables a systematic integration of QoS levels and SLA into the cloud. It is orthogonal to other cloud models such as SaaS or PaaS, and may apply to any of them. Second, the paper introduces CSLA, a novel language to describe QoS-oriented SLA associated with cloud services. Third, the paper presents a control theoretic approach to provide performance, dependability and cost guarantees for online cloud services, with time-varying workloads. The proposed approach is validated through case studies and extensive experiments with online services hosted in clouds such as Amazon EC2. The case studies illustrate SLA guarantees for various services such as a MapReduce service, a cluster-based multi-tier e-commerce service, and a low-level locking service.

Content availability has become increasingly important for the Internet video delivery chain. To deliver videos with an outstanding availability and meet the increasing user expectations, content delivery networks (CDNs) must enforce strict QoS metrics, like bitrate and latency, through SLA contracts. Adaptive content replication has been seen as a promising way to achieve this goal. However, it remains unclear how to avoid waste of resources when strict SLA contracts must be enforced. In this work, we introduce Hermes, an adaptive replication scheme based on accurate predictions about the popularity of Internet videos. Simulations using popularity growth curves from YouTube traces suggest that our approach meets user expectations efficiently. Compared to a non-collaborative caching, Hermes reduces storage usage for replication by two orders of magnitude, and under heavy load conditions, it increases the average bitrate provision by roughly 90%. Moreover, it prevents SLA violations through an application-level deadline-aware mechanism.

This paper presents an efficient dissemination algorithm suitable for scale-free random topologies which model some complex real world networks. In these topologies, some sites, denoted hubs, have many more connections than the others. By exploiting then the dissemination power of hubs, we propose a new gossip algorithm where sites directly connected to hubs do not forward received messages. Our algorithm offers a very high reliability and does not require any input parameter value that informs each site if it is a hub or not. Such an information is deduced by every site during the algorithm execution. Compared to well-known probabilistic gossip algorithms, performance simulation results show that our algorithm presents good performance in terms of message complexity and latency.

Distributed priority-based mutual exclusion algorithms may present starvation for low priority requests if the shared resource is continuously asked by high priority requests. To address this problem, several existing algorithms dynamically increment the priority of pending low-priority requests. The drawback of this approach is that it may lead to a great number of priority inversions, i.e., a pending request p is satisfied before another one whose priority is higher than p's. One solution to reduce this number, as we have proposed in [7], is to both postpone priority increments and prevent low priorities from increasing too fast. However, in this case, the response time of low priorities may considerably increase. Therefore, in this article, we propose a new algorithm, denoted "Awareness", which aims at reducing the maximum response time whereas the number of priority violations remains low. To this end, a global view of pending requests of the system is necessary. Performance evaluation results confirm that our new algorithm provides a good tradeoff between response time and number of priority inversions.

Distributed Hash Tables (DHTs) provide the substrate to build scalable and efficient Peer-to-Peer (P2P) networks: distributed systems with the potential to handle massive amounts of data on a very large scale. However, traditional DHTs provide very poor support for range queries. In this article we present a search mechanism that efficiently supports range queries over a ring-like DHT structure using a prefix tree index. Load balancing is improved by delegating the routing of queries to the nodes that store data, and by updating neighbor information through an optimistic approach. Our solution reduces latency and message traffic in environments where queries are more frequent than data insertion operations. We evaluate the performance of the system through simulations and show that our solution in not affected by data skewness.

In Cloud Computing, Service Level Agreement (SLA) is a contract that defines a level and a type of QoS between a cloud provider and a client. Since applications in a Cloud share resources, we propose two tree-based distributed mutual exclusion algorithms that support the SLA concept. The first one is a modified version of the priority-based Kanrar-Chaki algorithm [1] while the second one is a novel algorithm, based on Raymond algorithm [2], where a deadline is associated with every request. In both cases, our aim is to improve Critical Section execution rate and to reduce the number of SLA violations, which, for the first algorithm represents the number of priority inversions (i.e. a higher priority request is satisfied after a lower one) and for the second one, the number of requests whose deadline is not respected. Performance evaluation results show that our solutions significantly reduce SLA violations avoiding message overhead.

Delivering on-demand web content to end-users in order to carry out strict QoS metrics is not a trivial task for globally distributed network providers. This task becomes still harder when content popularity varies over the time and the SLA definitions have to include both transfer rate and latency metrics. Current worldwide content delivery approaches and datacenter infrastructures rely on cumbersome replication schemes that are agnostic to edge-network resources, and damage content provision. In this work we present AREN, an novel replication scheme for cloud storage on edge networks. AREN relies on a collaborative cache strategy and bandwidth reservation to adapt the replication degree according to strict SLA contracts and content popularity growth. We have evaluated the performances of replication schemes on edge networks using Caju, a content distribution system for edge networks. Compared to a non-collaborative caching, evaluations show that AREN prevents nearly 99.8% of all SLA violations when the storage system is heavily loaded. We also show that AREN provides a sevenfold decrease in the amount of storage usage for replicas, and it increases by roughly 20% the aggregate bandwidth, hence accelerating content delivery.

We present a thorough performance comparison of three widely used probabilistic gossip algorithms over well-known random graphs. These graphs represent some large-scale network topologies: Bernoulli (or Erdos-Rényi) graph, random geometric graph, and scale-free graph. In order to conduct such a fair comparison, particularly in terms of reliability, we propose a new parameter, called effectual fan out. For a given topology and gossip algorithm, the effectual fan out characterizes the mean dissemination power of infected sites. For large-scale networks, the effectual fan out has thus a strong linear correlation with message complexity. It enables to make an accurate analysis of the behavior of a gossip algorithm over a topology. Furthermore, it simplifies the theoretical comparison of different gossip algorithms on the topology. Based on extensive experiments on top of OMNet++ simulator, which make use of the effectual fan out, we discuss the impact of topologies and gossip algorithms on performance, and how to combine them to have the best gain in terms of reliability.

The distributed computing scenario is rapidly evolving for integrating self-organizing and dynamic wireless networks. Unreliable failure detectors (FDs) are classical mechanisms that provide information about process failures and can help systems to cope with the high dynamics of these networks. A number of failure detection algorithms have been proposed so far. Nonetheless, most of them assume a global knowledge about the membership as well as a fully communication connectivity; additionally, they are time-based, requiring that eventually some bound on the message transmission will permanently hold. These assumptions are no longer appropriate to the new scenario. This paper presents a new FD protocol that implements a new class of detectors, namely ⋄ Sℳ, which adapts the properties of the ⋄ S class to a dynamic network with an unknown membership. It has the interesting feature of being time-free, so that it does not rely on timers to detect failures; moreover, it tolerates the mobility of nodes and message losses.

DHT-based P2P systems provide a fault-tolerant and scalable means to store data blocks in a fully distributed way. Unfortunately, recent studies have shown that if connection/disconnection frequency is too high, data blocks may be lost. This is true for most of the current DHT-based systems' implementations. To deal with this problem, it is necessary to build more efficient replication and maintenance mechanisms. In this article, we study the effect of churn on PAST, an existing DHT-based P2P system. We then propose solutions to enhance churn tolerance and evaluate them through discrete event simulation.

Distributed Hash Tables (DHTs) provide the substrate to build large scale distributed applications over Peer-to-Peer networks. A major limitation of DHTs is that they only support exact-match queries. In order to offer range queries over a DHT it is necessary to build additional indexing structures. Prefix-based indexes, such as Prefix Hash Tree (PHT), are interesting approaches for building distributed indexes on top of DHTs. Nevertheless, the lookup operation of these indexes usually generates a high amount of unnecessary traffic overhead which degrades system performance by increasing response time. In this paper, we propose a novel distributed cache system called Tabu Prefix Table Cache (TPT-C), aiming at improving the performance of the Prefix-trees. We have implemented our solution over PHT, and the results confirm that our searching approach reduces up to a 70% the search latency and traffic overhead.

Large-scale distributed systems gather thousands of peers spread all over the world. Such systems need to offer good routing performances regardless of their size and despite high churn rates. To achieve that requirement, the system must add appropriate shortcuts to its logical graph (overlay). However, to choose efficient shortcuts, peers need to obtain information about the overlay topology. In case of heterogeneous peer distributions, retrieving such information is not straightforward. Moreover, due to churn, the topology rapidly evolves, making gathered information obsolete. State of- the-art systems either avoid the problem by enforcing peers to adopt a uniform distribution or only partially fulfill these requirements. To cope with this problem, we propose DONUT, a mechanism to build a local map that approximates the peer distribution, allowing the peer to accurately estimate graph distance to other peers with a local algorithm. The evaluation performed with real latency and churn traces shows that our map increases the routing process efficiency by at least 20% compared to the state-of-the-art techniques. It points out that each map is lightweight and can be efficiently propagated through the network by consuming less than 10 bps on each peer.

Distributed R-tree overlays emerged as an alternative for efficiently implementing DHT-free publish/subscribe communication primitives. Overlays using R-tree index structures offer logarithmic delivery garantis, guarantee zero false negatives and considerably reduce the number of false positives. In this paper we extend the distributed R-trees (DR-trees) in order to reduce event delivery latency. Our optimizations target both the structural organization of the DR-Trees and the publication policies. The contribution of the current work steams in an extensive evaluation of the novel structure along four parameters: latency, load, scalability and the rate of false positives. The enhanced structure performs better than the traditional distributed R-tree in terms of delivery latency. Additionally, it does not alter the performances related to the scalability, nor the load balancing of the tree, and neither the rate of false positives and negatives filtered by a node.

Mobile ad-hoc networks, MANETs, are self-organized and very dynamic systems where processes have no global knowledge of the system. In this paper, we propose a model that characterizes the dynamics of MANETs in the sense that it considers that paths between nodes are dynamically built and the system can have infinitely many processes but the network may present finite stable partitions. We also propose an algorithm that implements an eventually perfect partition participant detector PD which eventually detects the participant nodes of stable partitions.

We present in this paper a fault tolerant permission-based k-mutual exclusion algorithm, which is an extension of Raymond's algorithm. Tolerating up to n-1 failures, our algorithm keeps its effectiveness despite failures. It uses information provided by unreliable failure detectors to dynamically detect crashes of nodes. Performance evaluation experiments show the performance of our algorithm compared to Raymond's when faults are injected.

In mobile environment, nodes can move around and voluntarily leave or join the network. Furthermore, they can crash or be disconnected from the network due to the absence of network signals. Therefore, failure, disconnection and mobility may create partitions in wireless networks which should be detected for fault and disconnection tolerance reasons. We present in this article an architecture of local and distributed detectors for mobile networks that detect failures, disconnections, and partitions. It is basically composed of three unreliable detectors: a heartbeat failure detector, a vector-based disconnection detector, and an eventually perfect partition detector.

We propose a new composition approach to mutual exclusion algorithms for applications spread over a grid which is composed of a federation of clusters. Taking into account the heterogeneity of communication latency, our hierarchical architecture combines intra and inter cluster algorithms. We focus on token-based algorithms and study different compositions of algorithms. Performance evaluation tests have been conducted on a national grid testbed whose results show that our approach is scalable and that the choice of the most suitable inter cluster algorithm depends on the behavior of the application.

Distributed hash tables (DHTs) provide a means to build a completely decentralized, large-scale persistent storage service from the individual storage capacities contributed by each node of the peer-to-peer overlay. However, persistence can only be achieved if nodes are highly available, that is, if they stay most of the time connected to the overlay. In this paper we present an incentives-based mechanism to increase the availability of DHT nodes, thereby providing better data persistence for DHT users. High availability increases a node's reputation, which translates into access to more DHT resources and a better quality-of-service. The mechanism required for tracking a node's reputation is completely decentralized, and is based on certificates reporting a node's availability which are generated and signed by the node's neighbors. An audit mechanism deters collusive neighbors from generating fake certificates to take advantage of the system.

This paper presents an efficient and fair fault-tolerant token-based algorithm for achieving mutual exclusion. It is an extension of the Naimi-Trehel algorithm that uses a distributed queue of token requests and a dynamic tree. In case of failures, our algorithm tries to recover the requests' queue by gathering intact portions of the one which existed just before the failure. Thus, fairness of token requests is preserved despite failures. Furthermore, the use of broadcast is minimized when rebuilding the dynamic tree. Experiment results with different fault injection scenarios show that our approach presents a fast failure recovery and low message broadcast overhead

Mutual exclusion is a basic block of distributed synchronization algorithms. One of the challenges in highly distributed environments (like peer-to-peer or Grid configurations) is to provide scalable synchronizations taking into account the hierarchical network topology. This paper proposes hierarchical mutual exclusion algorithms. These algorithms are extensions of the Naimi-Trehel token algorithm, reducing the cost of latency and the number of message exchanges between far hosts. We propose three main extensions : (1) hierarchical proxy-based approach; (2) aggregation of requests; and (3) token preemption by closer hosts. We compared the performance of these algorithms on an emulated Grid testbed. We study the impact of each of the extensions, showing that the combination of them can greatly improve performance of the original algorithm.

Quorum systems are well-known tools that improve the performance and the availability of distributed systems. In this paper we explore their use as a means to achieve low response time for network services that are replicated and accessed over computing grids. To that end, we propose both a quorum construction and a quorum-based state-machine replication algorithm that tolerates crash failures in a partially synchronous model. We show through the evaluation of a real implementation that although simple, this quorum construction and replication algorithm exhibits a response time 20% lower than that of a regular active replication algorithm in appropriate conditions.

International audience

This paper presents DARX, our framework for building applications that provide adaptive fault tolerance. It relies on the fact that multi-agent platforms constitute a very strong basis for decentralized software that is both flexible and scalable, and makes the assumption that the relative importance of each agent varies during the course of the computation. DARX regroups solutions which facilitate the creation of multi-agent applications in a large-scale context. Its most important feature is adaptive replication: replication strategies are applied on a per-agent basis with respect to transient environment characteristics such as the importance of the agent for the computation, the network load or the mean time between failures. Firstly, the interwoven concerns of multi-agent systems and fault-tolerant solutions are put forward. An overview of the DARX architecture follows, as well as an evaluation of its performances. We conclude, after outlining the promising outcomes, by presenting prospective work.

Chandra and Toueg (1996) introduced the concept of unreliable failure detectors, They showed how, by adding these detectors to an asynchronous system, it is possible to solve the Consensus problem. In this paper, we propose a new implementation of a failure detector. This implementation is a variant of the heartbeat failure detector which is adaptable and can support scalable applications. In this implementation we dissociate two aspects: a basic estimation of the expected arrival date to provide a short detection time, and an adaptation of the quality of service according to application needs. The latter is based on two principles: an adaptation layer and a heuristic to adapt the sending period of "I am alive" messages.

In a previous article, we presented a per cluster logical cache strategy for a software distributed shared memory (SDSM) system for interconnects of loosely-coupled machine clusters. We assume that inter-cluster links are slower than intra-cluster ones. We propose an adaptive strategy that aims at increasing the efficiency of our first cache solution. By exploiting sharing access pattern of applications related to locality within the same cluster, the adaptive cache reduces the number of messages generated by our previous cache solution. Performance evaluation results show that the former outperforms the latter. We also present a new barrier algorithm, which is integrated with the adaptive cache and more adapted to the communication latency hierarchy of the platform.

As interconnected local-area workstation networks are widely available, the idea of offering a software distributed shared memory (SDSM) layer across them is quite an attractive alternative for compute-intensive applications. However, the higher cost of sending a message over an inter-cluster link than over an intracluster can limit applications' performance on a multicluster SDSM system. In this paper, we present the extensions that we have added to TreadMarks SDSM in order to adapt it to a loosely-coupled cluster-based platform. We have implemented a logical per-cluster cache in order to exploit cluster locality. By accessing its local cache, a processor can share data previously requested by another processor of its cluster, thereby hiding the cost of inter-cluster communication.

This paper presents the design, implementation and performance evaluation of a software fault manager for distributed applications. Dubbed Star, it uses the natural redundancy existing in networks of workstations to offer a high level of fault tolerance. Fault management is transparent to the supported parallel applications. To improve the response time of fault-tolerant applications, Star implements non-blocking and incremental checkpointing to perform an efficient backup of process state. Moreover, Star is application independent, highly configurable. Star actually runs on top of SunOs and is easily portable to UNIX™-like operating systems. The current implementation is based on independent checkpointing and message logging. Measurements show the efficiency and the limits of this implementation. The challenge is to show that a software approach to fault tolerance can efficiently be implemented in a standard networked environment. © 1998 John Wiley & Sons, Ltd.

This paper presents the performance evaluation of a software fault manager for distributed applications. Dubbed STAR, it uses the natural redundancy existing in networks of workstations to offer a high level of fault tolerance. Fault management is transparent to the supported parallel applications. STAR is application independent, highly configurable and easily portable to UNIX-like operating systems. The current implementation is based on independent checkpointing and message logging. Measurements show the efficiency and the limits of this implementation. The challenge is to show that a software approach to fault tolerance can efficiently be implemented in a standard networked environment.