Modern systems featuring multiple sockets suffer from the non-uniformity of performance of their memory accesses. Accessing memory of a remote node can lead to doubled latencies and halved bandwidth. This is particularly critical for I/O-intensive applications relying on the Linux page cache, where locality is paramount. Existing solutions migrating threads or memory across nodes fail to address the issue with highly parallel workloads, where a small working set is constantly accessed by multiple threads across nodes.

International audience

Hierarchies are fundamental structures across various disciplines, modelling hierarchical relationships in computer science, biology, social networks, and logistics. However, dynamic and concurrent updates in real-world systems necessitate synchronisation techniques for maintaining data consistency despite concurrent access. This paper explores a novel approach called CALock to synchronise operations on hierarchies by utilising a labelling scheme that facilitates multi-granularity locking. Our approach addresses both concurrent data reads and writes as well as structural modifications. CALock exploits the hierarchical topology via a new labelling scheme to identify the common ancestors of vertices. This enables a thread to identify an appropriate lock granule for its lock request. Leveraging variable lock granularity optimises operations across the hierarchy while ensuring consistency and performance. We provide a detailed discussion of the CALock labelling and the locking algorithm, prove its properties, and evaluate it experimentally. CALock remains competitive with previous labelling schemes on static hierarchies and has better concurrency and throughput when structural modifications change the hierarchy. In particular, CALock improves throughput by up to 4.5 times and lock response time by up to 1.5 times for workloads that contain structural modifications.

Abstract In the evolving landscape of SAT solving, leveraging parallel computation has become increasingly significant. The portfolio strategy, combined with clause sharing, has emerged as the leading approach for both local and distributed parallelization on CPUs. Frameworks such as Mallob exemplify the effectiveness of this strategy by providing a straightforward method to deploy portfolio parallel solvers across various computing environments. Similarly, the "Image missing" framework specializes in local parallelization, offering diverse strategies for task sharing and parallel execution. This enables the adoption of complex hybrid local parallelization techniques, including portfolio, divide-and-conquer, and cube-and-conquer methods. This paper presents "Image missing" , a new extension of the "Image missing" framework to include the distributed portfolio strategy and clause sharing. Our enhancement aims to broaden "Image missing" ’s functionality, enabling more effective and comprehensive distributed SAT solving methodologies.

This article presents a new image segmentation algorithm based on a Split & Merge approach. By nature, the execution time of Split & Merge algorithms is data-dependent, as their halting conditions are tied to the homogeneity of each region. While previous algorithms made the Split step less sensitive to input data, the execution time of the more complex Merge step remains highly sensitive to image content. This paper tackles the sensitivity and performance problems from a system and architecture perspective. Memory reallocations due to array fusions are eliminated with the introduction of a TTA (Three Table Array) structure in the Merge step. As iterating over entries in this structure causes a loss of memory locality, we propose two new mechanisms that implement a software cache to mitigate this. An experimental study on an embedded system (Nvidia Jetson Xavier NX) has shown our Merge algorithm to be 10.6 times faster than the state-of-the-art Split & Merge algorithm for $960 \times 720$ images. Moreover, the execution time of our algorithm is also more resistant to image characteristics.

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.

Designed 40 years ago, DNS is still a core component of internet: billions of DNS queries are processed each day to resolve domain names to IP addresses. Originally designed for performances and scalability, its transport protocol is unen-crypted, leading to security flaws. Recently, secure protocols have emerged, but the question of their scalability and sustainability remains open. In this paper we study the cost of switching from the legacy DNS transport to the newer ones, by first characterising the shape of the traffic between clients and secured public resolvers. Then, we replicate said traffic, to measure the added cost of each protocol. We found that, while connections usually stayed open, many closures and openings were made in some cases. Comparing these profiles over different DNS transports, we observe that switching from the legacy protocol to a more secure one can lead to an important performance penalty.

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.

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.

Recent research and bug reports have shown that work conservation, the property that a core is idle only if no other core is overloaded, is not guaranteed by Linux's CFS or FreeBSD's ULE multicore schedulers. Indeed, multicore schedulers are challenging to specify and verify: they must operate under stringent performance requirements, while handling very large numbers of concurrent operations on threads. As a consequence, the verification of correctness properties of schedulers has not yet been considered.

The container mechanism amortizes costs by consolidating several servers onto the same machine, while keeping them mutually isolated. Specifically, to ensure performance isolation, Linux relies on memory limits. These limits are static, despite the fact that application needs are dynamic; this results in poor performance. To solve this issue, MemOpLight uses dynamic application feedback to rebalance physical memory allocation between containers focusing on under- performing ones. This paper presents the issues, explains the design of MemOpLight, and validates it experimentally. Our approach increases total satisfaction by 13% compared to the default.

The container mechanism supports server consolidation; to ensure memory performance isolation, Linux relies on static memory limits. However, this results in poor performance, because an application needs are dynamic. In this article we will show current problems with memory consolidation for containers in Linux.

Memory interferences may introduce important slowdowns in applications running on COTS multi-core processors. They are caused by concurrent accesses to shared hardware resources of the memory system. The induced delays are difficult to predict, making memory interferences a major obstacle to the adoption of COTS multi-core processors in real-time systems. In this article, we propose an experimental characterization of applications' memory consumption to determine their sensitivity to memory interferences. Thanks to a new set of microbenchmarks, we show the lack of precision of a purely quantitative characterization. To improve accuracy, we define new metrics quantifying qualitative aspects of memory consumption and implement a profiling tool using the VALGRIND framework. In addition, our profiling tool produces high resolution profiles allowing us to clearly distinguish the various phases in applications' behavior. Using our microbenchmarks and our new characterization, we train a state-of-the-art regressor. The validation on applications from the M I B ENCH and the PARSEC suites indicates significant gain in prediction accuracy compared to a purely quantitative characterization.

The complexity of computer architectures has risen since the early years of the Linux kernel: Simultaneous Multi-Threading (SMT), multicore processing, and frequency scaling with complex algorithms such as Intel® Turbo Boost have all become omnipresent. In order to keep up with hardware innovations, the Linux scheduler has been rewritten several times, and many hardware-related heuristics have been added. Despite this, we show in this paper that a fundamental problem was never identified: the POSIX process creation model, i.e., fork/wait, can behave inefficiently on current multicore architectures due to frequency scaling. We investigate this issue through a simple case study: the compilation of the Linux kernel source tree. To do this, we develop SchedLog, a low-overhead scheduler tracing tool, and SchedDisplay, a scriptable tool to graphically analyze SchedLog's traces efficiently.

This work proposes to leverage the programming capabilities offered by eBPF with the high-performance of the XDP hook to execute KVS applications as kernel modules. With this design, the application is executed as a cache module in the kernel space. Our preliminary evaluation results show improvements of up to 30% of the number of processed get requests with UDP protocol. Moreover, this work discusses the eBPF limitations that prevent from full implementation of in-kernel KVS cache application.

Over the last decade, parallel SATisfiability solving has been widely studied from both theoretical and practical aspects. There are two main approaches. First, divide-and-conquer ( D&C ) splits the search space, each solver being in charge of a particular subspace. The second one, portfolio launches multiple solvers in parallel, and the first to find a solution ends the computation. However although D&C based approaches seem to be the natural way to work in parallel, portfolio ones experimentally provide better performances. An explanation resides on the difficulties to use the native formulation of the SAT problem ( i.e., the CNF form) to compute an a priori good search space partitioning ( i.e., all parallel solvers process their subspaces in comparable computational time). To avoid this, dynamic load balancing of the search subspaces is implemented. Unfortunately, this is difficult to compare load balancing strategies since state-of-the-art SAT solvers appropriately dealing with these aspects are hardly adaptable to various strategies than the ones they have been designed for. This paper aims at providing a way to overcome this problem by proposing an implementation and evaluation of different types of divide-and-conquer inspired from the literature. These are relying on the Painless framework, which provides concurrent facilities to elaborate such parallel SAT solvers. Comparison of the various strategies are then discussed.

Operating systems have been shown to waste machine resources by leaving cores idle while work is ready to be scheduled. This results in suboptimal performance for user applications, and wasted power.

The thriving success of the Cloud Industry greatly relies on the fact that virtual resources are as good as bare metal resources when it comes to ensuring a given level of quality of service. Thanks to the isolation provided by virtualisation techniques based on hypervisors, a big physical resource can be spatially multiplexed into smaller virtual resources which are easier to sell. Unfortunately, virtual machines have quickly shown their limit in terms of temporal multiplexing. It has been demonstrated that reclaiming the unused memory of a VM is a tedious task, infeasible in production. Today, containerization opens up a wide range of multiplexing opportunities that were not accessible through machine virtualization. However, in this article, we demonstrate, through a reproducible experiment, that the current implementation of memory consolidation can deteriorate the performance of applications deployed in Linux kernel containers. Indeed, we observed that when a new container boots, the memory of active containers is reclaimed while unused memory is still available in other containers that are inactive. To tackle these performance drop in active containers, we have rethought the hierarchical memory reclaim mechanism of the Linux kernel. We have implemented inside the kernel our new approach that tracks the container that has made a memory demand the least recently. Our evaluations show that our approach provides the ability to reclaim memory without disturbing performances.

Complex embedded systems today commonly involve a mix of real-time and best-effort applications. The recent emergence of low-cost multicore processors raises the possibility of running both kinds of applications on a single machine, with virtualization ensuring isolation. Nevertheless, memory contention can introduce other sources of delay, that can lead to missed deadlines. In this paper, we present a combined offline/online memory bandwidth monitoring approach. Our approach estimates and limits the impact of the memory contention incurred by the best-effort applications on the execution time of the real-time application. We show that our approach is compatible with the hardware counters provided by current small commodity multicore processors. Using our approach, the system designer can limit the overhead on the real-time application to under 5% of its expected execution time, while still enabling progress of the best-effort applications.

On contemporary cache-coherent Non-Uniform Memory Access (ccNUMA) architectures, applications with a large memory footprint suffer from the cost of the garbage collector (GC), because, as the GC scans the reference graph, it makes many remote memory accesses, saturating the interconnect between memory nodes. We address this problem with NumaGiC, a GC with a mostly-distributed design. In order to maximise memory access locality during collection, a GC thread avoids accessing a different memory node, instead notifying a remote GC thread with a message; nonetheless, NumaGiC avoids the drawbacks of a pure distributed design, which tends to decrease parallelism. We compare NumaGiC with Parallel Scavenge and NAPS on two different ccNUMA architectures running on the Hotspot Java Virtual Machine of OpenJDK 7. On Spark and Neo4j, two industry-strength analytics applications, with heap sizes ranging from 160GB to 350GB, and on SPECjbb2013 and SPECjbb2005, ourgc improves overall performance by up to 45% over NAPS (up to 94% over Parallel Scavenge), and increases the performance of the collector itself by up to 3.6x over NAPS (up to 5.4x over Parallel Scavenge).

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.

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.

Large-scale multicore architectures create new challenges for garbage collectors (GCs). In particular, throughput-oriented stop-the-world algorithms demonstrate good performance with a small number of cores, but have been shown to degrade badly beyond approximately 8 cores on a 48-core with OpenJDK 7. This negative result raises the question whether the stop-the-world design has intrinsic limitations that would require a radically different approach. Our study suggests that the answer is no, and that there is no compelling scalability reason to discard the existing highly-optimised throughput-oriented GC code on contemporary hardware. This paper studies the default throughput-oriented garbage collector of OpenJDK 7, called Parallel Scavenge. We identify its bottlenecks, and show how to eliminate them using well-established parallel programming techniques. On the SPECjbb2005, SPECjvm2008 and DaCapo 9.12 benchmarks, the improved GC matches the performance of Parallel Scavenge at low core count, but scales well, up to 48~cores.

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.

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.

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.

In the context of multicore programming, pipeline parallelism is a solution to easily transform a sequential program into a parallel one without requiring a whole rewriting of the code. The OpenMP stream-computing extension presented by Pop and Cohen proposes an extension of OpenMP to handle pipeline parallelism. However, their communication algorithm relies on Multiple-producer-Multiple-Consumer queues, while pipelined applications mostly deal with linear chains of communication, i.e., with only a single producer and a single consumer. To improve the performance of the OpenMP stream-extension, we propose to add a more specialized Single-Producer-Single-Consumer communication algorithm called Batch Queue and to select it for one-to-one communication. Our evaluation shows that Batch Queue is then able to improve the throughput up to a factor 2 on an 8-core machine both for example application and real applications. Our study shows therefore that using specialized and efficient communication algorithms can have a significant impact on the overall performance of pipelined applications.

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.

Managed Runtime Environments (MRE) are increasingly used for application servers that use large multi-core hardware. We find that the garbage collector is critical for overall performance in this setting. We explore the costs and scalability of the garbage collectors on a contemporary 48-core multiprocessor machine. We present experimental evaluation of the parallel and concurrent garbage collectors present in OpenJDK, a widely-used Java virtual machine. We show that garbage collection represents a substantial amount of an application's execution time, and does not scale well as the number of cores increases. We attempt to identify some critical scalability bottlenecks for garbage collectors.

Sequential applications can take advantage of multi-core systems by way of pipeline parallelism to improve their performance. In such parallelism, core to core communication overhead is the main limit of speedup. This paper presents BatchQueue, a fast and memory-thrifty core to core communication system based on batch processing of whole cache line. BatchQueue is able to send a 32bit word of data in just 12.5 ns on a Xeon X5472 and only needs 2 full cache lines plus 3 byte-sized variables - each on a different cache line for optimal performance - to work. The characteristics of BatchQueue - high throughput and increased latency resulting from its batch processing - makes it well suited for highly communicative tasks with no real time requirements such as monitoring.

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