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.

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.

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.

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.

Weighted voting is a conventional approach to improving the performance of replicated systems based on commonly-used majority quorum systems in heterogeneous environments. In long-lived systems, a weight reassignment protocol is required to reassign weights over time in order to accommodate performance variations accordingly. The weight reassignment protocol should be consensus-free in asynchronous failure-prone systems because of the impossibility of solving consensus in such systems. This paper presents an efficient consensus-free weight reassignment protocol for atomic storage systems in heterogeneous, dynamic, and asynchronous messagepassing systems. An experimental evaluation shows that the proposed protocol improves the performance of atomic read/write storage implemented by majority quorum systems compared with previous solutions.

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.

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.

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.

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.

Computer architecture and high performance computingThis special issue of Concurrency and Computation Practice and Experience gathers eleven selected research articles that were previously presented at the Brazilian "XVII Simpósio em Sistemas Computacionais de Alto Desempenho," WSCAD 2016, held in conjunction with 28th International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2015, Florianópolis, SC, Brazil, from the 19th to the 21st October 2015.Since 2000, this workshop has presented important and interesting research in the fields of computer architectures, high performance computing, and distributed systems.The scope of the current special issue is broad and representative of the multidisciplinary nature of high performance and distributed computing, covering a wide range of subjects such as architecture issues, compiler optimization, analysis of HPC applications, job scheduling, and energy efficiency.The title of the first paper is "An efficient virtual system clock for the wireless Raspberry Pi computer platform," by Diego L. C. Dutra, Edilson C. Corrêa, and Claudio L. Amorim [1].In this paper, the authors present the design and experimental evaluation of an implementation of the RVEC virtual system clock in the Linux kernel for the EE (Energy-Efficient) Wireless Raspberry Pi (RasPi) platform.In the RasPi platform, the use of DVFS (Dynamic Voltage and Frequency) for reducing the energy consumption hinders the direct use of the cycle count of the ARM11 processor core for building an efficient system clock.Therefore, a distinct feature of RVEC is to obviate this obstacle, such that it can make use of the cycle count circuit for precise and accurate time measurements, concurrently with the use of DVFS by the operating system of the ARM11 processor core.In the second contribution, entitled "Portability with efficiency of the advection of BRAMS between multi-core and many-core architectures," the authors, Manoel Baptista Silva Junior, Jairo Panetta, and Stephan Stephany [2], show the feasibility of writing a single portable code embedding both interfaces (the OpenMP programming interface and OpenACC).It presents acceptable efficiency when executed on nodes with multi-core or many-core architecture.The code chosen as a case study is the advection of scalars, a part of the dynamics of the regional atmospheric model Brazilian Regional Atmospheric Modeling System (BRAMS).The dynamics of this model is hard to parallelize due to data dependencies between adjacent grid points.Single-node executions of the advections of scalars for different grid sizes using OpenMP or OpenACC yielded similar speed-ups, showing the feasibility of the proposed approach.In the third contribution, entitled "SMT-based context-bounded model checking for CUDA programs," the authors (

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.

A quorum system is a collection of process sets (quorums) which intersect among themselves. Quorums are used by many distributed applications such as mutual exclusion, data replication, and for the dissemination of information. This work presents an autonomic solution to build a majority quorum system that is self-adaptive by dymically reconfiguring itself if processes fail. Processes can fail by crashing and crashes are permanent. The proposed solution is defined over a VCube - a virtual hypercube-like topology [1], and uses failure information from the VCube's monitoring system. Each quorum is built so that any quorum has a majority of the faulty-free processes of the system. Upon the detection of a failure, the quorum system reconfigures automatically, tolerating up to n-1 crashed processes. Experimental results confirm the efficiency of the proposed algorithm compared with other solutions of the literature.

In the aftermath of a natural or industrial disaster, locating individuals is crucial. However, disasters can cause extensive damage to the network infrastructures and a generalized loss of communication among survivors. In this article, we present a network support solution that provides a post-disaster geolocation-collecting service that relies on inter mobile device connections. On top of this dynamically built network, survivors' mobile devices exchange information about geolocation of others they have encountered. Such information is routed towards predefined data collection centers using either the DTN Epidemic or Spray and Wait DTN protocol. Experiments were conducted on the ONE simulator and performance evaluation results confirm the effectiveness of our proposal.

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.

Summary Data abundance poses the need for powerful and easy‐to‐use tools that support processing large amounts of data. MapReduce has been increasingly adopted for over a decade by many companies, and more recently, it has attracted the attention of an increasing number of researchers in several areas. One main advantage is that the complex details of parallel processing, such as complex network programming, task scheduling, data placement, and fault tolerance, are hidden in a conceptually simple framework. MapReduce is supported by mature software technologies for deployment in data centers such as Hadoop. As MapReduce becomes popular for high‐performance applications, many questions arise concerning its performance and efficiency. In this paper, we demonstrated formally lower bounds on the isoefficiency function for MapReduce applications, when these applications can be modeled as BSP jobs. We also demonstrate how communication and synchronization costs can be dominant for MapReduce computations and discuss the conditions under which such scalability limits are valid. To our knowledge, this is the first study that demonstrates scalability bounds for MapReduce applications. We also discuss how some MapReduce implementations such as Hadoop can mitigate such costs to approach linear, or near‐to‐linear speedups. Copyright © 2015 John Wiley & Sons, Ltd.

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 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.

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.

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.

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 mutual exclusion is a basic building block of distributed systems that coordinates the access to critical shared resources. This work introduces a novel permission-based k-mutual exclusion algorithm for distributed systems with crash faults. Processes monitor each other and organize themselves on an adaptive virtual topology that is based on the hypercube and presents several logarithmic properties. Mutual exclusion is deployed on top of this monitoring system. Processes communicate through spanning trees which are created with a fully distributed strategy that tolerates faults by using process state information provided by the underlying monitoring system. Both the mutual exclusion and the distributed spanning tree algorithm are formally specified. The strategy is proven to guarantee the safety and liveness of the concurrent access of n processes to k critical resources. Experimental results are presented, showing that the algorithm performs efficiently even when up to n-1 processes are faulty.

We propose in this paper a new algorithm that, when called by existing token ring-based algorithms of parallel and distributed applications, easily renders the token tolerant to losses in presence of node crashes. At most k consecutive node crashes are tolerated in the ring. Our algorithm scales very well since a node monitors the liveness of at most k other nodes and neither a global election algorithm nor broadcast primitives are used to regenerate a new token. It is thus very effective in terms of latency cost. Finally, a study of the probability of having at most k consecutive node crashes in the presence of f failures and a discussion of how to extend our algorithm to other logical topologies are also presented.

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.

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.

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.

International audience

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.

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.

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.