With the growing interest in blockchains, permissioned approaches to consensus have received increasing attention. Unfortunately, the BFT consensus algorithms that are the backbone of most of these blockchains scale poorly and offer limited throughput. In fact, many state-of-the-art BFT consensus algorithms require a single leader process to receive and validate votes from a quorum of processes and then broadcast the result, which is inherently non-scalable. Recent approaches avoid this bottleneck by using dissemination/aggregation trees to propagate values and collect and validate votes. However, the use of trees increases the round latency, which limits the throughput for deeper trees. In this article, we propose Kauri, a BFT communication abstraction that sustains high throughput as the system size grows by leveraging a novel pipelining technique to perform scalable dissemination and aggregation on trees. Furthermore, when the number of faults is moderate (arguably the most common case in practice), our construction is able to recover from faults in an optimal number of reconfiguration steps. We implemented and experimentally evaluated Kauri with up to 800 processes. Our results show that Kauri outperforms the throughput of state-of-the-art permissioned blockchain protocols, by up to 58x without compromising latency. Interestingly, in some cases, the parallelization provided by Kauri can also decrease the latency.

Federated Learning traditionally relies on differential privacy or cryptographic techniques such as Secure Aggregation and Homomorphic Encryption to protect data during distributed training, but these approaches incur high computational and communication costs. The emergence of hardware-based Trusted Execution Environments, particularly Confidential Virtual Machines (CVMs), offers a practical alternative by enabling secure computation on untrusted cloud infrastructures without algorithmic changes.However, CVM deployments by cloud providers—Google Cloud, Microsoft Azure, and AWS—remain opaque, inconsistent, and difficult to reproduce. This paper analyzes their trust models, attestation mechanisms, and deployment limitations, and introduces EVIDENT, a unified framework for transparent CVM lifecycle management. Furthermore, it supports attested interaction scenarios in which CVMs execute workloads owned by third parties—such as confidential AI inference—under cryptographically verifiable trust conditions.

Transactional Causal Consistency (TCC) is the strongest consistency model compatible with availability and, therefore, it avoids the pitfalls of the CAP theorem while simplifying the programming of cloud applications. Unfortunately, with previous implementations, TCC came at the cost of expensive reads. TCC has been implemented either using conservative approaches, that always require two communication rounds, or using optimistic approaches that, in good cases, require just one round, but in face of skewed workloads, that are common in real applications, can require three communication rounds. In this paper we propose a novel algorithm, named PrompTCC, that in most cases offers reads in just one round and that, even in face of skewed workloads, never takes more than two rounds. As a result, PrompTCC is able to closely approximate the performance of an eventually consistent system while providing stronger guarantees, achieving only 12% throughput and 20% latency penalty in realistic scenarios, outperforming state-of-the-art systems which present up to 37% and 60% throughput and latency degradation respectively.

The use of remote storage has become prevalent both by organizations and individuals. By relying on third-party storage, such as cloud or peer-to-peer storage services, availability, fault tolerance, and low access latency can be attained in a cost-efficient manner. Unfortunately, storage providers may misbehave and violate Service-Level Agreements (SLAs). In this article, we propose a new Proof of Timely-Retrievability (PoTR) that aims at assessing whether a provider is able to retrieve data objects with a latency lower than some SLA-specific threshold δ. We have implemented the PoTR and evaluated two distinct configurations of the proof, one tailored to estimate the average latency experience by clients and the other tailored to assess its variance. We leverage Trusted Execution Environments (e.g., Intel SGX) to ensure that the proof is produced by the node being audited and to reduce the communication between the auditor and the audited node. We have experimentally evaluated our prototypes considering a challenging edge computing setting, where storage services are provided by resource-constrained fog nodes, and the distance between the auditor and the audited node can be large. Despite the noise introduced by edge network delays, we show that the auditor is able to effectively detect SLA violations.

This article focuses on the problem of optimizing the system utility of Machine Learning (ML)-based systems in the presence of ML mispredictions. This is achieved via the use of self-adaptive systems and through the execution of adaptation tactics, such as model retraining , which operate at the level of individual ML components. To address this problem, we propose a probabilistic modeling framework that reasons about the cost/benefit tradeoffs associated with adapting ML components. The key idea of the proposed approach is to decouple the problems of estimating (1) the expected performance improvement after adaptation and (2) the impact of ML adaptation on overall system utility. We apply the proposed framework to engineer a self-adaptive ML-based fraud detection system, which we evaluate using a publicly available, real fraud detection dataset. We initially consider a scenario in which information on the model’s quality is immediately available. Next, we relax this assumption by integrating (and extending) state-of-the-art techniques for estimating the model’s quality in the proposed framework. We show that by predicting the system utility stemming from retraining an ML component, the probabilistic model checker can generate adaptation strategies that are significantly closer to the optimal, as compared against baselines such as periodic or reactive retraining.

In this paper we propose a novel abstraction that we have named Range-Revocable Pseudonyms (RRPs). RRPs are a new class of pseudonyms whose validity can be revoked for any time-range within its original validity period. The key feature of RRPs is that the information provided to revoke a pseudonym for a given time-range cannot be linked with the information provided when using the pseudonym outside the revoked range. We provide an algorithm to implement RRPs using efficient cryptographic primitives where the space complexity of the pseudonym is constant, regardless of the granularity of the revocation range, and the space complexity of the revocation information only grows logarithmically with the granularity; this makes the use of RRPs far more efficient than the use of many short-lived pseudonyms. We have used RRPs to design EDGAR, an access control system for VANET scenarios that offers backward unlinkability. The experimental evaluation of EDGAR shows that, when using RRPs, the revocation can be performed efficiently (even when using time slots as small as 1 second) and that users can authenticate with low latency (0.5-3.5ms ).

The use of remote storage has become prevalent both by organizations and individuals. By relying on third-party storage, such as cloud or peer-to-peer storage services, availability, fault tolerance, and low access latency can be attained in a cost-efficient manner. Unfortunately, storage providers may misbehave and violate Service-Level Agreements (SLAs). In this paper, we propose, implement and evaluate a new Proof of Timely-Retrievability (PoTR) that aims at assessing whether a provider is able to retrieve data objects with a latency lower than some SLA-specific threshold δ. We leverage Trusted Execution Environments (e.g., Intel SGX) to ensure that the proof is produced by the node being audited and to reduce the communication between the auditor and the audited node. We have experimentally evaluated our design considering a challenging edge computing setting, where storage services are provided by resource-constrained fog nodes, and the distance between the auditor and the audited node can be large. Despite the variance in edge network delays, we show that the auditor is able to effectively detect SLA violations.

Edge computing offers support for latencyconstrained applications, by replicating data in the edge. Edge storage systems need to adopt both partial replication, as only data of interest needs to be replicated, and weak consistency models, to avoid the overhead and latency induced by the coordination mechanisms of strong consistency models. In this context, session guarantees are a powerful tool that can be used to simplify the design of edge applications. This paper presents Engage, a storage system that offers efficient support for session guarantees in a partially replicated edge setting. To achieve this, Engage combines the use of vector clocks and distributed metadata propagation services with a payload propagation scheme tailored for the edge. We have implemented Engage and evaluated its performance experimentally. The results show that, when compared with previous proposals, the combination of techniques employed by Engage reduce both the number of false dependencies, that can slow down the system, and the signaling overhead, while improving the freshness of data exposed to clients.

The edge computing paradigm extends cloud computing with storage and processing capacity close to the edge of the network, which can be materialized by using many fog nodes placed in multiple geographic locations. Fog nodes are likely to be vulnerable to tampering, so it is important to protect the functions they provide from attacks. A key building block of many distributed applications is an ordering service that keeps track of cause-effect dependencies among events and that allows events to be processed in an order that respects causality. This article presents the design and implementation of a secure event ordering service for fog nodes. Our service, named Omega, leverages the availability of a Trusted Execution Environment (TEE), based on SGX technology, to offer fog clients guarantees regarding the order in which events are applied and served, even when fog nodes are compromised. We have also built OmegaKV, a key-value store that uses Omega to offer causal consistency. Experimental results show that the ordering service can be secured without violating the latency constraints of time-sensitive edge applications, despite the overhead associated with using a TEE. Omega introduces an additional latency of approximately 4ms, that contrary to cloud based solutions, allows latency values in the 5ms-30ms range, as required by time-sensitive edge applications.

In this paper we study mechanisms that permit to augment the FaaS middleware with support for Transactional Causal Consistency (TCC). At first glance, it may seem that offering TCC to FaaS applications can trivially be achieved, given that the FaaS paadigm does not prevent applications from selecting the storage service with the properties they need. Unfortunately, most TCC storage services ensure consistency only to individual client processes, while a FaaS application is executed by multiple, independent, worker processes. Therefore, there is the need to coordinate the workers, a task that can be a significant source of overhead. We propose a novel architecture to support TCC in FaaS, named FaaSTCC, that significantly reduces the coordination overhead. FaaSTCC achieves this goal by augmenting the workers with a caching layer and by implementing novel mechanisms that maximize the cache usage. First, our storage layer offers to the caching layer a promise, that sets a horizon where the versions retrieved by the cache are guaranteed to be consistent. Second, in FaaSTCC, functions coordinate using snapshot intervals, that support the lazy identification of the read snapshot, increasing the chances of using the cached values. We have implemented and experimentally evaluated FaaSTCC. Our results show that FaaSTCC achieves up to 5x lower average latency and 6x lower tail latency than previous work.

Data storage has been recognized as one of the key tasks for edge/fog computing infrastructures. Keeping replicas of data near the edge has many advantages, including allowing client to be served directly from the fog layer with lower latency and avoiding short-lived data to be shipped in its entirely to the cloud servers. In both cases, edge storage can offer significant bandwidth savings in traffic to and from the cloud datacenterse. However, replica placement on the edge is challenging for multiple reasons. First, objects can be updated by many sources, unlike in classic CDN networks where most updates are centralized. Second, different objects may have different consistency requirements. Third, the number of nodes and objects is very large, which precludes the use of centralized solutions. In this paper, we propose a replica placement algorithm for the edge, named Cathode, that addresses the challenges above. Cathode is decentralized and scalable, providing fast convergence, but also achieving high quality deployments. Furthermore, when making placement decision, it takes into account the data consistency protocol, considering both the cost of update and read operations, leading to different placements for different replica-consistency algorithms. The paper offers an extensive evaluation of Cathode and show that it outperforms previous state-of-the-art replica placement algorithms.

This paper investigates the problem of integrating two powerful abstractions for concurrent programming, namely futures and transactional memory. Our focus is on specifying the semantics of execution of "transactional futures", i.e., futures that execute as atomic transactions and that are spawned/evaluated by other (plain) transactions or transactional futures. We show that, due to the ability of futures to generate parallel computations with complex dependencies, there exist several plausible (i.e., intuitive) alternatives for defining the isolation and atomicity semantics of transactional futures. The alternative semantics we propose explore different trade-offs between ease of use and efficiency. We have implemented the proposed semantics by introducing a graph-based software transactional memory algorithm, which we integrated with a state of the art JAVA-based Software Transactional Memory (STM). We quantify the performance trade-offs associated with the different semantics using an extensive experimental study encompassing a wide range of diverse workloads.

With the growing commercial interest in blockchains, permissioned implementations have received increasing attention. Unfortunately, the BFT consensus algorithms that are the backbone of most of these blockchains scale poorly and offer limited throughput. Many state-of-the-art algorithms require a single leader process to receive and validate votes from a quorum of processes and then broadcast the result, which is inherently non-scalable. Recent approaches avoid this bottleneck by using dissemination/aggregation trees to propagate values and collect and validate votes. However, the use of trees increases the round latency, which ultimately limits the throughput for deeper trees. In this paper we propose Kauri, a BFT communication abstraction that can sustain high throughput as the system size grows, leveraging a novel pipelining technique to perform scalable dissemination and aggregation on trees. Our evaluation shows that Kauri outperforms the throughput of state-of-the-art permissioned blockchain protocols, such as HotStuff, by up to 28x. Interestingly, in many scenarios, the parallelization provided by Kauri can also decrease the latency.

Many censorship circumvention tools rely on trusted proxies that allow users within censored regions to access blocked Internet content by tunneling it through a covert channel (e.g,. piggybacking on Skype video calls). However, building tools that can simultaneously (i) provide good bandwidth capacity for accommodating the typical activities of Internet users, and (ii) be secure against traffic analysis attacks has remained an open problem and a stumbling block to the practical adoption of such tools for censorship evasion.

Edge computing is a paradigm that extends cloud computing with storage and processing capacity close to the edge of the network that can be materialized by using many fog nodes placed in multiple geographic locations. Fog nodes are likely to be vulnerable to tampering, so it is important to secure the functions they provide. A key building block of many distributed applications is an ordering service that keeps track of cause-effect dependencies among events and that allows events to be processed in an order that respects causality. In this paper we present the design and implementation of a secure event ordering service for fog nodes. Our service, named Omegae, leverages the availability of a Trusted Execution Environment (TEE) based on Intel SGX technology to offer fog clients guarantees regarding the order in which events are applied and served, even when fog nodes are compromised. We have also built OmegaKV, a key-value store that uses Omega e to offer causal consistency. Experimental results show that the ordering service can be secured without violating the latency constraints of time-sensitive edge applications, despite the overhead associated with using a TEE.

Today, many applications offload computation and storage to the cloud. Unfortunately, the high network latency between clients and datacenters can impair novel, latency-constrained, applications such as augmented reality. Edge computing has emerged as a potential solution to circumvent this problem. To unleash its full potential, the edge must cache data that is frequently used. However, building a storage service that is able to maintain many (partial) replicas while providing meaningful consistency guarantees to clients that migrate among multiple edge caches is an open challenge. In this paper, we present Gesto, a data storage architecture that enables scalable causal consistency for edge networks. Gesto integrates a novel causality tracking mechanism that relies on multi-part timestamps of constant size, independently on the number of edge caches. As our evaluation shows, this mechanism enables Gesto to simultaneously offer scalability, low read/write latency, high throughput, and, unlike previous work, fast client migrations.

Modern data analytic and machine learning jobs find in the cloud a natural deployment platform to satisfy their notoriously large resource requirements. Yet, to achieve cost efficiency, it is crucial to identify a deployment configuration that satisfies user-defined QoS constraints (e.g., on execution time), while avoiding unnecessary over-provisioning.This paper introduces Lynceus, a new approach for the optimization of cloud-based data analytic jobs that improves over state-of-the-art approaches by enabling significant cost savings both in terms of the final recommended configuration and of the optimization process used to recommend configurations.Unlike existing solutions, Lynceus optimizes in a joint fashion both the cloud-related (i.e., which and how many machines to provision) and the application-level (e.g. the hyper-parameters of a machine learning algorithm) parameters. This allows for a reduction of the cost of recommended configurations by up to 3.7× at the 90-th percentile with respect to existing approaches, which treat the optimization of cloud-related and application- level parameters as two independent problems.Further, Lynceus reduces the cost of the optimization process (i.e., the cloud cost incurred for testing configurations) by up to 11×. Such an improvement is achieved thanks to two mechanisms: i) a timeout approach which allows to abort the exploration of configurations that are deemed suboptimal, while still extracting useful information to guide future explorations and to improve its predictive model - differently from recent works, which either incur the full cost for testing suboptimal configurations or are unable to extract any knowledge from aborted runs; ii) a long-sighted and budget-aware technique that determines which configurations to test by predicting the long-term impact of each exploration - unlike state-of-the-art approaches for the optimization of cloud jobs, which adopt greedy optimization methods.

After the seminal paper by L. Lamport, which introduced (scalar) logical clocks, several other data structures for keeping track of causality in distributed systems have been proposed, including vector and matrix clocks. These are able to capture causal dependencies with more detail but, unfortunately, also consume a substantially larger amount of network bandwidth and storage space than Lamport clocks. This raises the question of whether the benefits of these more complex structures are worth their cost. We address this question in the context of partially replicated systems. We show that for some workloads the use of more expensive clocks does bring significant benefits and that for other workloads no visible benefits can be observed. The paper provides a characterization of the scenarios where each type of clock is more beneficial, helping designers to develop more efficient distributed storage systems.

Although graph-databases have been assuming an increasing relevance in applications that exhibit strong dependability requirements, including tolerance to malicious faults, few works have addressed Byzantine fault tolerance in this particular context, and previous attempts suffer from lack of flexibility and poor performance. This article describes and evaluates Fireplug, a flexible architecture to build robust geo-replicated graph databases. Fireplug can be configured to tolerate from crash to Byzantine faults, both within and across different datacenters. Furthermore, Fireplug is robust to bugs in existing graph database implementations, as it allows to combine multiple graph database instances in a cohesive manner. Thus, Fireplug can support many different deployments, according to the performance/robustness trade-offs imposed by the target application. Our evaluation shows that Fireplug is able implement Byzantine fault tolerance without penalty when compared to the built-in replication mechanism of Neo4j, which only supports crash faults. Additionally, performance optimizations introduced by Fireplug improve the overall performance by up to 900 percent in geo-replicated scenarios.

This paper addresses the key problems that emerge when one attempts to use transient resources to reduce the cost of running time-constrained jobs in the cloud. Previous works fail to address these problems and are either not able to offer significant savings or miss termination deadlines. First, the fact that transient resources can be evicted, requiring the job to be re-started (even if not from scratch) may lead provisioning policies to fall-back to expensive on-demand configurations more often than desirable, or even to miss deadlines. Second, when a job is restarted, the new configuration can be different from the previous, which might make eviction recovery costly, e.g., transferring the state of graph data between the old and new configurations. We present HOURGLASS, a system that addresses these issues by combining two novel techniques: a slack-aware provisioning strategy that selects configurations considering the remaining time before the job's termination deadline, and a fast reload mechanism to quickly recover from evictions. By switching to an on-demand configuration when (but only if) the target deadline is at risk of not being met, we are able to obtain significant cost savings while always meeting the deadlines. Our results show that, unlike previous work, HOURGLASS is able to significantly reduce the operating costs in the order of 60-70% while guaranteeing that deadlines are met.

The emergence of programmable switches has sparked a significant amount of work on new techniques to perform more powerful measurement tasks, for instance, to obtain fine-grained traffic and performance statistics. Previous work has focused on the efficiency of these measurements alone and has neglected flexibility, resulting in solutions that are hard to reuse or repurpose and that often overlap in functionality or goals. In this paper, we propose the use of a set of reusable primitive building blocks that can be composed to express measurement tasks in a concise and simple way. We describe the rationale for the design of our primitives, that we have named MAFIA (Measurements As FIrst-class Artifacts), and using several examples we illustrate how they can be combined to realize a comprehensive range of network measurement tasks. Writing MAFIA code does not require expert knowledge of low-level switch architecture details. Using a prototype implementation of MAFIA, we demonstrate the applicability of our approach and show that the use of our primitives results in compiled code that is comparable in size and resource usage with manually written specialized P4 code, and can be run in current hardware.

This paper addresses the problem of offering reliable causal multicast in a setting where nodes are organized in an overlay network and use this network to disseminate information among each other. The use of overlay networks for this purpose is widely used when the number of nodes is large. For instance, many publish-subscribe systems use an overlay of message brokers to support the exchange of information among publishers and subscribers. To the best of our knowledge, previous multicast algorithms for overlay networks either do not enforce causal order or, in order to do so, require nodes to keep metadata (for instance, sequence numbers) for all senders and are, therefore, inherently non-scalable. In this paper we propose a novel localized algorithm to implement reliable causal multicast, where each node is only required to keep metadata regarding nodes in its neighbourhood (with a radius that is a function of the number of faults that need to be tolerated). Experimental results show that our algorithm can achieve significant improvements over non-localized alternatives, and can even outperform localized algorithms that do not offer causal order.

This paper addresses the problem of self-tuning the parallelism degree in Transactional Memory (TM) systems that support parallel nesting (PN-TM). This problem has been long investigated for TMs not supporting nesting, but, to the best of our knowledge, has never been studied in the context of PN-TMs. Indeed, the problem complexity is inherently exacerbated in PN-TMs, since these require to identify the optimal parallelism degree not only for top-level transactions but also for nested sub-transactions. The increase of the problem dimensionality raises new challenges (e.g., increase of the search space, and proneness to suffer from local maxima), which are unsatisfactorily addressed by self-tuning solutions conceived for flat nesting TMs. We tackle these challenges by proposing AUTOPN, an on-line self-tuning system that combines model-driven learning techniques with localized search heuristics in order to pursue a twofold goal: i) enhance convergence speed by identifying the most promising region of the search space via model-driven techniques, while ii) increasing robustness against modeling errors, via a final local search phase aimed at refining the model's prediction. We further address the problem of tuning the duration of the monitoring windows used to collect feedback on the system's performance, by introducing novel, domain-specific, mechanisms aimed to strike an optimal trade-off between latency and accuracy of the self-tuning process. We integrated AUTOPN with a state of the art PN-TM (JVSTM) and evaluated it via an extensive experimental study. The results of this study highlight that AUTOPN can achieve gains of up to 45× in terms of increased accuracy and 4× faster convergence speed, when compared with several on-line optimization techniques (gradient descent, simulated annealing and genetic algorithm), some of which were already successfully used in the context of flat nesting TMs.

Modern fault-tolerant distributed architectures can be configured to tolerate a wide-range of faults. For instance, Fireplug is a distributed BFT graph database, based on n-version programming, that can be configured to tolerate crash or Byzantine faults, uncorrelated faults in individual machines, correlated faults that affect all replicas running a given software version, or correlated faults that affect an entire datacenter. Interestingly, in such a system, fault handling heavily depends on the type of faults the system is configured to tolerate. To hardwire all possible behaviours in the fault-handling code is inflexible and may even be impractical. In this paper, we explore a different alternative that consists in specifying not only the system configuration, but also the fault-handling behaviour, and how the system adapts to changes in the workload, in a policy language, that is processed externally to the managed system. We show that, using this approach, a single simplified codebase of the managed system can be used effectively to address a wide range of dependability constraints.

Summary This paper presents CoopREP, a system that provides support for fault replication of concurrent programs based on cooperative recording and partial log combination. CoopREP uses partial logging to reduce the amount of information that a given program instance is required to store to support deterministic replay. This allows reducing substantially the overhead imposed by the instrumentation of the code, but raises the problem of finding a combination of logs capable of replaying the fault. CoopREP tackles this issue by introducing several innovative statistical analysis techniques aimed at guiding the search of the partial logs to be combined and needed for the replay phase. CoopREP has been evaluated using both standard benchmarks for multithreaded applications and real‐world applications. The results highlight that CoopREP can successfully replay concurrency bugs involving tens of thousands of memory accesses, while reducing recording overhead with respect to state‐of‐the‐art noncooperative logging schemes by up to 13× (and by 2.4× on average).

This paper presents the design, implementation, and evaluation of Saturn, a metadata service for geo-replicated systems. Saturn can be used in combination with several distributed and replicated data services to ensure that remote operations are made visible in an order that respects causality, a requirement central to many consistency criteria.

Cloud computing has enabled many applications to dynamically accommodate their resources in response to variations in their workloads. Elastic scaling is implemented mostly via reactive techniques that are slow to respond and may induce service degradation during the adaptation period. To avoid those pitfalls, proactive techniques have emerged as an alternative. However, these are typically limited to settings with homogeneous resources. We introduce Augure, a prediction-based controller for live reconfiguration of cloud applications in heterogeneous settings. Augure relies on behavioral patterns of the workload obtained from historical data to feed a proactive adaptation engine. With the help of constraint solvers, Augure's engine finds the combination of (potentially mixed) resource types that best matches the expected evolution of the workload, and derives a plan that minimizes the price billed by the cloud provider and the impact of the reconfiguration on the quality of service provided to clients. We use simulations and a real system implementation to evaluate Augure and compare it to other controllers such as Reactive, Vadara, and Vadara+.

The problem of ensuring consistency in applications that manage replicated data is one of the main challenges of distributed computing. Among the several invariants that may be enforced, ensuring that updates are applied and made visible respecting causality has emerged as a key ingredient among the many consistency criteria and client session guarantees that have been proposed and implemented in the last decade. Techniques to keep track of causal dependencies, and to subsequently ensure that messages are delivered in causal order, have been widely studied. It is today well known that, in order to accurately capture causality one may need to keep a large amounts of metadata, for instance, one vector clock for each data object. This metadata needs to be updated and piggybacked on update messages, such that updates that are received from remote datacenters can be applied locally without violating causality. This metadata can be compressed; ultimately, it is possible to preserve causal order using a single scalar as metadata, i.e., a Lamport’s clock. Unfortunately, when compressing metadada it may become impossible to distinguish if two events are concurrent or causally related. We denote such scenario a false dependency. False dependencies introduce unnecessary delays and impair the latency of update propagation. This problem is exacerbated when one wants to support partial replication. Therefore, when building a geo-replicated large-scale system one is faced with a dilemma: one can use techniques that maintain few metadata and that fail to capture causality accurately, or one can use techniques that require large metadata (to be kept and exchanged) but have precise information about which updates are concurrent. The former usually offer good throughput at the cost of latency, while the latter offer lower latencies sacrificing throughput. This talk reports on Saturn[1] and Eunomia[2], two complementary systems that break this tradeoff by providing simultaneously high-throughput and low latency, even in face of partial replication. The key ingredient to the success of our approach is to decouple the metadata path from the data path and to serialize concurrent events (to reduce metadata), in the metadata path, in a way that minimizes the impact on the latency perceived by clients.

Abstract This paper studies the possibility of using the encrypted video channel of widely used videoconferencing applications, such as Skype, as a carrier for unobservable covert TCP/IP communications. We propose and evaluate different alternatives to encode information in the video stream in order to increase available throughput while preserving the packet-level characteristics of the video stream. We have built a censorship-resistant system, named DeltaShaper, which offers a data-link interface and supports TCP/IP applications that tolerate low throughput / high latency links. Our results show that it is possible to run standard protocols such as FTP, SMTP, or HTTP over Skype video streams.

In decentralized systems, nodes often need to coordinate to access shared resources in a fair manner. One approach to perform such arbitration is to rely on auction mechanisms. Although there is an extensive literature that studies auctions, most of these works assume the existence of a central, trusted auctioneer. Unfortunately, in fully decentralized systems, where the nodes that need to cooperate operate under separate spheres of control, such central trusted entity may not exist. Notable examples of such decentralized systems include community networks, clouds of clouds, cooperative nano data centres, among others. In this paper, we make theoretical and practical contributions to distribute the role of the auctioneer. From the theoretical perspective, we propose a framework of distributed simulations of the auctioneer that are Nash equilibria resilient to coalitions and asynchrony. From the practical perspective, our protocols leverage the distributed nature of the simulations to parallelise the execution. We have implemented a prototype that instantiates the framework for bandwidth allocation in community networks, and evaluated it in a real distributed setting.

Edge-computing is one of the most promising techniques to leverage the excess capacity that exists at users' premises. Unfortunately, edge-computing may be vulnerable to free-riding, i.e., to nodes that attempt to benefit from the system without providing any service in return. Traditional approaches model free-riders as rational nodes that strive to maximize a utility and apply Game Theory concepts to devise mechanisms that deny any utility gain to nodes that deviate from the protocol. These mechanisms impose significant overheads. This paper proposes a new approach that avoids these overheads, which applies concepts of evolutionary game theory. We propose to devise lightweight mechanisms targeted for the optimistic setting where nodes adopt one of a small number of behaviours. If a small fraction of nodes follows alternative behaviours, then the lightweight mechanism should limit the utility gain of these nodesto control the increase in the number of these nodes. This allows altruistic nodes to detect their presence in time to switch to more robust mechanisms before the system reaches a state where the lightweight mechanisms can no longer cope with the existing behaviours. We apply this approach in the context of edge-assisted streaming and propose the use of carefully crafted symmetric overlays to support message dissemination in an environment with free-riders and white-washers. The topology maintenance procedures of our overlay encourage nodes to maintain stable symmetric links. Leveraging the topological properties of the resulting symmetric overlay, direct reciprocity mechanisms deny any utility gain to free-riders and white-washers, while limiting the utility gain of small fractions of nodes that adopt more sophisticated behaviours.

This work investigates how to combine two powerful abstractions to manage concurrent programming: Transactional Memory (TM) and futures. The former hides from programmers the complexity of synchronizing concurrent access to shared data, via the familiar abstraction of atomic transactions. The latter serves to schedule and synchronize the parallel execution of computations whose results are not immediately required. While TM and futures are two widely investigated topics, the problem of how to exploit these two abstractions in synergy is still largely unexplored in the literature. This paper fills this gap by introducing Java Transactional Futures (JTF), a Java-based TM implementation that allows programmers to use futures to coordinate the execution of parallel tasks, while leveraging transactions to synchronize accesses to shared data. JTF provides a simple and intuitive semantic regarding the admissible serialization orders of the futures spawned by transactions, by ensuring that the results produced by a future are always consistent with those that one would obtain by executing the future sequentially. Our experimental results show that the use of futures in a TM allows not only to unlock parallelism within transactions, but also to reduce the cost of conflicts among top-level transactions in high contention workloads.

Communication through the Internet raises privacy and confidentiality concerns. Protocols such as HTTPS may be used to protect the communication, but occasionally vulnerabilities that may allow snooping on packet content are discovered. To address this issue, we present MACHETE, an application-layer multi-path communication mechanism that provides additional confidentiality by splitting data streams in different physical paths. MACHETE has to handle two challenges: sending packets over different paths when Internet's routing imposes a single path between pairs of network interfaces; splitting streams of data sent over TCP connections. MACHETE is the first to exploit MultiPath TCP (MPTCP) for security purposes. It leverages overlay networks and multihoming to handle the first challenge and MPTCP to handle the second. MACHETE establishes an overlay network and scatters the data over the available paths, thus reducing the effectiveness of snooping attacks. Mechanisms are provided to select paths based on path diversity.

Concurrency bugs that stem from schedule-dependent branches are hard to understand and debug, because their root causes imply not only different event orderings, but also changes in the control-flow between failing and non-failing executions. We present Cortex: a system that helps exposing and understanding concurrency bugs that result from schedule-dependent branches, without relying on information from failing executions. Cortex preemptively exposes failing executions by perturbing the order of events and control-flow behavior in non-failing schedules from production runs of a program. By leveraging this information from production runs, Cortex synthesizes executions to guide the search for failing schedules. Production-guided search helps cope with the large execution search space by targeting failing executions that are similar to observed non-failing executions. Evaluation on popular benchmarks shows that Cortex is able to expose failing schedules with only a few perturbations to non-failing executions, and takes a practical amount of time.

We present Symbiosis: a concurrency debugging technique based on novel differential schedule projections (DSPs). A DSP shows the small set of memory operations and dataflows responsible for a failure, as well as a reordering of those elements that avoids the failure. To build a DSP, Symbiosis first generates a full, failing, multithreaded schedule via thread path profiling and symbolic constraint solving. Symbiosis selectively reorders events in the failing schedule to produce a nonfailing, alternate schedule . A DSP reports the ordering and dataflow differences between the failing and nonfailing schedules. Our evaluation on buggy real-world software and benchmarks shows that, in practical time, Symbiosis generates DSPs that both isolate the small fraction of event orders and dataflows responsible for the failure and report which event reorderings prevent failing. In our experiments, DSPs contain 90% fewer events and 96% fewer dataflows than the full failure-inducing schedules. We also conducted a user study that shows that, by allowing developers to focus on only a few events, DSPs reduce the amount of time required to understand the bug’s root cause and find a valid fix.

In this article we introduce GMU, a genuine partial replication protocol for transactional systems, which exploits an innovative, highly scalable, distributed multiversioning scheme. Unlike existing multiversion-based solutions, GMU does not rely on any global logical clock, which may represent a contention point and a major impairment to system scalability. Also, GMU never aborts read-only transactions and spares them from undergoing distributed validation schemes. This makes GMU particularly efficient in presence of read-intensive workloads, as typical of a wide range of real-world applications. GMU guarantees the Extended Update Serializability (EUS) isolation level. This consistency criterion is particularly attractive as it is sufficiently strong to ensure correctness even for very demanding applications (such as TPC-C), but is also weak enough to allow efficient and scalable implementations, such as GMU. Further, unlike several relaxed consistency models proposed in literature, EUS shows simple and intuitive semantics, thus being an attractive consistency model for ordinary programmers. We integrated GMU in a popular open source in-memory transactional data grid, namely Infinispan. On the basis of a wide experimental study performed on heterogeneous platforms and using industry standard benchmarks (namely TPC-C and YCSB), we show that GMU achieves almost linear scalability and that it introduces reduced overhead, with respect to solutions ensuring non-serializable semantics, in a wide range of workloads.

The paper proposes SmartFetch, a storage strategy that relies on a combination of techniques aimed at efficiently supporting selective jobs that are only concerned with a subset of the entire dataset in systems such as Hadoop and Spark. We combine the use of an appropriate data-layout with data indexing tools to improve the data access speed and significantly shorten total job execution time. An extensive experimental evaluation of SmartFetch shows that, by avoiding reading irrelevant blocks, it can provide significant speedups when compared to the basic Hadoop and Spark implementations. Further, our system also outperforms other implementations that use several variants of the techniques we have embedded in SmartFetch.

This paper presents Q-OPT, a system for automatically tuning the configuration of quorum systems in strongly consistent Software Defined Storage (SDS) systems. Q-OPT is able to assign different quorum systems to different items and can be used in a large variety of settings, including systems supporting multiple tenants with different profiles, single tenant systems running applications with different requirements, or systems running a single application that exhibits non-uniform access patterns to data. Q-OPT supports automatic and dynamic reconfiguration, using a combination of complementary techniques, including top-k analysis to prioritise quorum adaptation, machine learning to determine the best quorum configuration, and a non-blocking quorum reconfiguration protocol that preserves consistency during reconfiguration. Q-OPT has been implemented as an extension to one of the most popular open-source SDS, namely Openstack's Swift.

Edge-computing is one of the most promising techniques to leverage the excess capacity that exists at users' premises. Unfortunately, it may be vulnerable to free-riding, i.e., To nodes that attempt to benefit from the infrastructure without providing any service in return. In this short paper we address free-riding in the context of edge-assisted streaming and propose the use of carefully crafted symmetric overlays to support message dissemination and efficient free-rider detection.

We present Symbiosis: a concurrency debugging technique based on novel differential schedule projections (DSPs). A DSP shows the small set of memory operations and data-flows responsible for a failure, as well as a reordering of those elements that avoids the failure. To build a DSP, Symbiosis first generates a full, failing, multithreaded schedule via thread path profiling and symbolic constraint solving. Symbiosis selectively reorders events in the failing schedule to produce a non-failing, alternate schedule. A DSP reports the ordering and data-flow differences between the failing and non-failing schedules. Our evaluation on buggy real-world software and benchmarks shows that, in practical time, Symbiosis generates DSPs that both isolate the small fraction of event orders and data-flows responsible for the failure, and show which event reorderings prevent failing. In our experiments, DSPs contain 81% fewer events and 96% less data-flows than the full failure-inducing schedules. Moreover, by allowing developers to focus on only a few events, DSPs reduce the amount of time required to find a valid fix.

Replication plays an essential role for in-memory distributed transactional platforms, given that it represents the primary means to ensure data durability. Unfortunately, no single replication technique can ensure optimal performance across a wide range of workloads and system configurations. This paper tackles this problem by presenting MORPHR, a framework that allows to automatically adapt the replication protocol of in-memory transactional platforms according to the current operational conditions. MORPHR presents two key innovative aspects. On one hand, it allows to plug in, in a modular fashion, specialized algorithms to regulate the switching between arbitrary replication protocols. On the other hand, MORPHR relies on state of the art machine learning techniques to autonomously determine the best replication in face of varying workloads. We integrated MORPHR in an open-source in-memory NoSQL data grid, and evaluated it by means of an extensive experimental study. The results highlight that MORPHR is accurate in identifying the best replication strategy in presence of complex realistic workloads, and does so with minimal overhead.

Over the last years Transactional Memory (TM) gained growing popularity as a simpler, attractive alternative to classic lock-based synchronization schemes. Recently, the TM landscape has been profoundly changed by the integration of Hardware TM (HTM) in Intel commodity processors, raising a number of questions on the future of TM.

We consider the following natural problem: n failure-prone servers, communicating synchronously through message passing, must assign themselves one-to-one to n distinct items. Existing literature suggests two possible approaches to this problem. First, model it as an instance of tight renaming in synchronous message-passing systems; for deterministic solutions, a tight bound of Θ(log n) communication rounds is known. Second, model the scenario as an instance of randomized load-balancing, for which elegant sub-logarithmic solutions exist. However, careful examination reveals that known load-balancing schemes do not apply to our scenario, because they either do not tolerate faults or do not ensure one-to-one allocation. It is thus natural to ask if sub-logarithmic solutions exist for this apparently simple but intriguing problem.

The advent of multi-core architectures has brought concurrent programming to the forefront of software development. In this context, Transactional Memory (TM) has gained increasing popularity as a simpler, attractive alternative to traditional lock-based synchronization. The recent integration of Hardware TM (HTM) in the last generation of Intel commodity processors turned TM into a mainstream technology, raising a number of questions on its future and that of concurrent programming.

Unstructured P2P networks have been widely used to implement resource location systems that support complex queries semantics. Unfortunately these systems usually rely on search algorithms based on some variant of flooding, which generate a significant amount of duplicate messages. An effective way to minimize the cost of query flooding in unstructured P2P networks is the use of super-peers. On the other hand, super-peers may become overloaded or may fail, and have a negative impact on the performance and connectivity of the overlay. These risks can be circumvented by replicating super-peers. Replication serves the dual purpose of supporting load distribution and fault-tolerance purposes. This paper proposes a novel algorithm to construct an overlay network connecting replicated super-peers. We have called the resulting overlay, Overnesia. The paper also proposes techniques to perform query routing that leverage on the unique properties of Overnesia to effectively distribute the query processing load among replicas.

This article addresses the problem of self-tuning the data placement in replicated key-value stores. The goal is to automatically optimize replica placement in a way that leverages locality patterns in data accesses, such that internode communication is minimized. To do this efficiently is extremely challenging, as one needs not only to find lightweight and scalable ways to identify the right assignment of data replicas to nodes but also to preserve fast data lookup. The article introduces new techniques that address these challenges. The first challenge is addressed by optimizing, in a decentralized way, the placement of the objects generating the largest number of remote operations for each node. The second challenge is addressed by combining the usage of consistent hashing with a novel data structure, which provides efficient probabilistic data placement. These techniques have been integrated in a popular open-source key-value store. The performance results show that the throughput of the optimized system can be six times better than a baseline system employing the widely used static placement based on consistent hashing.

Replication plays an essential role for in-memory distributed transactional platforms, such as NoSQL data grids, given that it represents the primary mean to ensure data durability. Unfortunately, no single replication technique can ensure optimal performance across a wide range of workloads and system configurations. This paper tackles this problem by presenting MORPHR, a framework that allows to automatically adapt the replication protocol of in-memory transactional platforms according to the current operational conditions. MORPHR presents two key innovative aspects. On one hand, it allows to plug in, in a modular fashion, specialized algorithms to regulate the switching between arbitrary replication protocols. On the other hand, MORPHR relies on state of the art machine learning techniques to autonomously determine the optimal replication in face of varying workloads. We integrated MORPHR in a popular open-source in-memory NoSQL data grid, and evaluated it by means of an extensive experimental study. The results highlight that MORPHR is accurate in identifying the optimal replication strategy in presence of complex, realistic workloads, and does so with minimal overhead.

This paper proposes a Geo-distributed key-value datastore, named ChainReaction, that offers causal+ consistency, with high performance, fault-tolerance, and scalability. ChainReaction enforces causal+ consistency which is stronger than eventual consistency by leveraging on a new variant of chain replication. We have experimentally evaluated the benefits of our approach by running the Yahoo! Cloud Serving Benchmark. Experimental results show that ChainReaction has better performance in read intensive workloads while offering competitive performance for other workloads. Also we show that our solution requires less metadata when compared with previous work.

Abstract—Renaming is a fundamental problem in distributed computing, which consists of a set of processes picking distinct names from a given namespace. The paper presents algorithms that solve order-preserving renaming in synchronous message passing systems with Byzantine processes. To the best of our knowledge, this work is the first to address order-preserving renaming in the given model. Although this problem can be solved by using consensus, it is known that renaming is “weaker ” than consensus, therefore we are mainly concerned with the efficiency of performing renaming and make three contributions in this direction. We present an order-preserving renaming algorithm for N> 3t with target namespace of size N+t−1 and logarithmic step complexity (where N is the number of processes and t is an upper bound on the number of faults). Similarly to the existing crash-tolerant solution, our algorithm employs the ideas from the approximate agreement problem. We show that our algorithm has constant step complexity if N> t2 + 2t and achieves tight namespace of size N. Finally, we present an algorithm that solves order-preserving renaming in just 2 communication steps, if N> 2t2 + t. I.

This paper addresses the problem of maintaining replicated data in large scale P2P systems. Although this topic has been extensively studied in the literature, to maintain replicated data in this setting, in an efficient manner, still remains a significant challenge. This paper proposes novel policies to address this problem and evaluates their performance against different criteria, such as monitoring costs, data transfer costs, and load unbalance costs. We show that one of these new policies significantly outperforms previous work. Interestingly, this policy is based on a somehow counter-intuitive approach, that uses less reliable nodes to store the most accessed data items. The insights to derive this policy were obtained from an in depth analysis of existing solutions, that is also captured in the paper.

In this paper we present Roller chain, a novel Distributed Hash Table that offers efficient data storage through the combination of gossip-based and structured overlay networks. The unstructured component maintains clusters of fully connected nodes, where each cluster acts as a virtual node in the structured component. This architecture simplifies the management of data replication and balances the load among nodes in the system. We have implemented a prototype of Roller chain that we have used to experimentally validate its performance against other state of the art solutions.

In this paper we consider the fundamental problems of renaming and order-preserving renaming [1] in a synchronous message passing system with Byzantine failures. We study the feasibility of solving these problems using randomized algorithms under both non-rushing and rushing adversaries. We first show that there is a randomized algorithm that solves renaming efficiently for any t < N under the non-rushing adversary (N is the number of processes, and t is the maximum number of Byzantine processes). This result establishes a separation between randomized and deterministic renaming, since it is known that there are no efficient deterministic algorithms for t≥N/3. Our algorithm terminates in O(log N) rounds w.h.p. We next consider the renaming problem in the harder setting with the rushing adversary. Interestingly, we show that in this setting the algorithm also works with t = 1 but fails for larger t. We then give an algorithm that works with any t < N by relying on cryptographic commitment. Finally, we turn our attention to the problem of order-preserving renaming, which requires the new names to preserve the order of the initial identifiers. For this problem, we prove a tight t < N/3 bound that holds for both deterministic and randomized algorithms.

The problem of self-optimization and adaptation in the context of customizable systems is becoming increasingly important with the emergence of complex software systems and unpredictable execution environments. Here, a general framework for automatically deciding on when and how to adapt a system whenever it deviates from the desired behavior is presented. In this framework, the system's target behavior is described as a high-level policy that establishes goals for a set of performance indicators. The decision process is based on information provided independently for each component that describes the available adaptations, their impact on performance indicators, and any limitations or requirements. The technique consists of both offline and online phases. Offline, rules are generated specifying component adaptations that may help to achieve the established goals when a given change in the execution context occurs. Online, the corresponding rules are evaluated when a change occurs to choose which adaptations to perform. Experimental results using a prototype framework in the context of a web-based application demonstrate the effectiveness of this approach.

This paper presents CoopREP, a system that provides support for fault replication of concurrent programs, based on cooperative recording and partial log combination. CoopREP employs partial recording to reduce the amount of information that a given program instance is required to store in order to support deterministic replay. This allows to substantially reduce the overhead imposed by the instrumentation of the code, but raises the problem of finding the combination of logs capable of replaying the fault. CoopREP tackles this issue by introducing several innovative statistical analysis techniques aimed at guiding the search of partial logs to be combined and used during the replay phase. CoopREP has been evaluated using both standard benchmarks for multi-threaded applications and a real-world application. The results highlight that CoopREP can successfully replay concurrency bugs involving tens of thousands of memory accesses, reducing logging overhead with respect to state of the art non-cooperative logging schemes by up to 50 times in computationally intensive applications.

In this article we introduce GMU, a genuine partial replication protocol for transactional systems, which exploits an innovative, highly scalable, distributed multiversioning scheme. Unlike existing multiversion-based solutions, GMU does not rely on a global logical clock, which represents a contention point and can limit system scalability. Also, GMU never aborts read-only transactions and spares them from distributed validation schemes. This makes GMU particularly efficient in presence of read-intensive workloads, as typical of a wide range of real-world applications. GMU guarantees the Extended Update Serializability (EUS) isolation level. This consistency criterion is particularly attractive as it is sufficiently strong to ensure correctness even for very demanding applications (such as TPC-C), but is also weak enough to allow efficient and scalable implementations, such as GMU. Further, unlike several relaxed consistency models proposed in literature, EUS has simple and intuitive semantics, thus being an attractive, scalable consistency model for ordinary programmers. We integrated the GMU protocol in a popular open source in-memory transactional data grid, namely Infinispan. On the basis of a large scale experimental study performed on heterogeneous experimental platforms and using industry standard benchmarks (namely TPC-C and YCSB), we show that GMU achieves linear scalability and that it introduces negligible overheads (less than 10%), with respect to solutions ensuring non-serializable semantics, in a wide range of workloads.

Renaming is a fundamental problem in distributed computing which consists in a set of processors picking distinct names from a given namespace. We are interested in a stronger variant of the problem in which the processors have to pick new names according to the initial order of their original ids.

This paper introduces SPECULA, a novel replication protocol for Software Transactional Memory (STM) systems that seeks maximum overlap between transaction execution and replica synchronization phases via speculative processing techniques. By removing the replica synchronization phase from the critical path of execution of transactions, SPECULA allows threads to speculatively pipeline the execution of both transactional and/or non-transactional code. The core of SPECULA is a multi-version concurrency control algorithm that supports speculative transaction processing while ensuring the strong consistency criteria that are desirable in non-sand-boxed environments like STMs. Via an experimental study, based on a fully-fledged prototype and on both synthetic and standard STM benchmarks, we demonstrate that SPECULA can achieve speedups of up to one order of magnitude with respect to state-of-the-art non-speculative replication techniques.

Gossip, or epidemic, protocols have emerged as a highly scalable and resilient approach to implement several application level services such as reliable multicast, data aggregation, publish-subscribe, among others. All these protocols organize nodes in an unstructured random overlay network. In many cases, it is interesting to bias the random overlay in order to optimize some efficiency criteria, for instance, to reduce the stretch of the overlay routing. In this paper, we propose X-BOT, a new protocol that allows to bias the topology of an unstructured gossip overlay network. X-BOT is completely decentralized and, unlike previous approaches, preserves several key properties of the original (nonbiased) overlay (most notably, the node degree and consequently, the overlay connectivity). Experimental results show that X-BOT can generate more efficient overlays than previous approaches independently of the underlying physical network topology.

This paper addresses the self-management of in-memory distributed data grid platforms. A growing number of applications rely in these platforms to speed up access to large sets of data. However, they are complex to manage due to the diversity of configuration and load profiles. The proposed approach employs an adaptation policy expressed in terms of high-level goals to facilitate the task of the system manager, and address the complexity issues posed by the management of multiple configurations. The approach is validated experimentally using the open-source RedHat's Infinispan platform.

This paper addresses the problem of multipath routing in hybrid wireless mesh networks. We study the use of clustering algorithms to facilitate the discovery and deployment of non-interfering multipath routes in these settings. In this context we propose a novel combination of clustering and routing techniques aiming at minimizing interferences between transmissions of neighbouring nodes. We provide a comparative evaluation results and show that our solution offers an interesting tradeoff between the signalling cost, the time required to set up and maintain paths, and the properties of the discovered paths.

Multicast is an important building block for many applications in MANETs, including data dissemination, service discovery, publish-subscribe, among others. Therefore, it has been widely studied and many solutions can be found in the literature. However, most existing multicast protocols are tailored to a specific type of mobility pattern and therefore are unable to excel in face of heterogeneous topology stability conditions. This paper proposes and evaluates TSAMP, a Topology Stability-Aware Multicast Protocol for MANETs that exploits locally perceived mobility conditions in order to promote the use of stable routes, when available.

Software Transactional Memory (STM) has emerged a powerful abstraction for managing access to shared data. Therefore, it is no surprise that a handful of different STM replication schemes have been proposed in the last recent years. In this context, we propose an architecture that facilitates the integration and execution of multiple replication techniques in a single, coherent, middleware infrastructure. This paves the way towards the development of autonomic mechanisms, able to select in runtime the most appropriate replication technique for the workload at hand.

Nowadays, distributed in-memory caches are increasingly used as a way to improve the performance of applications that require frequent access to large amounts of data. In order to maximize performance and scalability, these platforms typically rely on weakly consistent partial replication mechanisms. These schemes partition the data across the nodes and ensure a predefined (and typically very small) replication degree, thus maximizing the global memory capacity of the platform and ensuring that the cost to ensure replica consistency remains constant as the scale of the platform grows. Moreover, even though several of these platforms provide transactional support, they typically sacrifice consistency, ensuring guarantees that are weaker than classic 1-copy serializability, but that allow for more efficient implementations. This paper proposes and evaluates two partial replication techniques, providing different (weak) consistency guarantees, but having in common the reliance on total order multicast primitives to serialize transactions without incurring in distributed deadlocks, a main source of inefficiency of classical two-phase commit (2PC) based replication mechanisms. We integrate the proposed replication schemes into Infinispan, a prominent open-source distributed in-memory cache, which represents the reference clustering solution for the well-known JBoss AS platform. Our performance evaluation highlights speed-ups of up to 40× when using the proposed algorithms with respect to the native Infinispan replication mechanism, which relies on classic 2PC-based replication.

Being much simpler to compose and verify than classical lock based synchronization schemes, Software Transactional Memories (STMs) have emerged as an attractive paradigm for supporting concurrent access to in-memory storage systems. This paper is focused on the issue of how to replicate STMs to enhance both their performance and dependability. This is an extremely challenging problem, since the communication/processing ratio in STMs is typically several orders of magnitude higher than in conventional database systems, thus amplifying the relative cost of replication.

The Sybil Attack is a serious threat to the secure and dependable operation of wireless ad hoc networks. This paper proposes an algorithm to provide each correct node in an one-hop wireless network with a quorum of non-Sybil identities from the neighbourhood. The quorums provided to different correct nodes may differ, but their intersection is composed by a majority of correct identities, with an arbitrarily close to 1 probability. Therefore, the quorums may be used for different purposes, such as voting. The algorithm is based on the combination of different resource tests, to efficiently detect (and exclude) Sybil identities.

In this paper we investigate the problem of speculative processing in a replicated transactional system layered on top of an optimistic atomic broadcast service. We consider a realistic model in which transactions' read/write sets are not known a-priori, and transactions' data access patterns may vary depending on the observed snapshot. We formalize a set of correctness and optimality properties aimed at ensuring that transactions are not activated on inconsistent snapshots, as well as the minimality and completeness of the set of explored serialization orders. Finally, an optimal speculative transaction replication protocol is presented.

In recent years the world has witnessed many catastrophic events where the intervention of first responders was required to manage massive disaster scenarios. To be effective, emergency management teams must be able to coordinate and communicate efficiently. To the best of our knowledge no solution has been proposed to support the communication and coordination of these teams in an integrated fashion. In this paper we propose MUSTUS, an architecture that provides communication mechanisms and coordination primitives, based on the interaction through a tuple space, whose semantics are specifically designed to support the needs of emergency management applications.

Recently there has been an effort to build scalable and reliable application-level multicast solutions that combine the resilience of pure gossip-based with the efficiency of tree-based schemes. However, such solutions assume that participants have unlimited resources, for instance, that they can send an unbounded number of messages to mask network omissions. Such scenario is not realistic, specially for streaming protocols, where messages can be transmitted at a very high rate and have a small temporal validity. In this paper, we propose RASM, a scalable distributed protocol for application-level multicast. Our protocol is based on the combination of gossip-based and tree-based multicast schemes. Unlike previous approaches, which strive to combine gossip-based and tree-based schemes, our solution takes into consideration the reliability of components: nodes and communication links can fail, unexpectedly, ceasing their operation and dropping messages, respectively. Experimental results show that our scheme offers better reliability than previous solutions with low overhead.

We define the problem of speculative processing in a replicated transactional system layered on top of an optimistic atomic broadcast service. A realistic model is considered in which transactions' read and write sets are not a priori known and transactions' data access patterns may vary depending on the observed snapshot. We formalize a set of correctness and optimality properties ensuring the minimality and completeness of the set of explored serialization orders within the replicated transactional system.

One way to efficiently disseminate information in a P2P overlay is to rely on a spanning tree. However, in a tree, interior nodes support a much higher load than leaf nodes. Also, the failure of a single node can break the tree, impairing the reliability of the dissemination protocol. These problems can be addressed by using multiple trees, such that each node is interior in just a few trees and a leaf node in the remaining, the multiple trees approach allows to achieve load distribution and also to send redundant information for fault-tolerance. This paper proposes Thicket, a decentralized algorithm to efficiently build and maintain such multiple trees over a single unstructured overlay network. The algorithm has been implemented and is extensively evaluated using simulation in a P2P overlay with 10.000 nodes.

Topological worms, such as those that propagate by following links in an overlay network, have the potential to spread faster than traditional random scanning worms because they have knowledge of a subset of the overlay nodes, and choose these nodes to propagate themselves; and also because they can avoid traditional detection mechanisms. Furthermore, this worm propagation strategy is likely to become prevalent as the deployment of networks with a sparse address space, such as IPv6, makes the traditional random scanning strategy futile. We present a novel approach for containing topological worms based on the fact that some overlay nodes may not have common vulnerabilities, due to their platform diversity. By reorganizing the overlay graph, it is possible to contain topological worms in small islands of nodes with common vulnerabilities that only have knowledge of themselves or nodes running on distinct platforms. We also present the design of Verme, a peer-to-peer overlay based on Chord that follows this approach, and VerDi, a DHT layer built on top of the Verme routing overlay. Simulations show that Verme and VerDi have a low overhead when compared to Chord's corresponding layers, and that our new overlay design helps containing, or at least slowing down the propagation of topological worms.

In this paper we define the weak mutual exclusion (WME) problem. Analogously to classical distributed mutual exclusion (DME), WME serializes the accesses to a shared resource. Differently from DME, however, the WME abstraction regulates the access to a replicated shared resource, whose copies are locally maintained by every participating process. Also, in WME, processes suspected to have crashed are possibly ejected from the critical section. We prove that, unlike DME, WME is solvable in a partially synchronous model, i.e. a system where the bounds on communication latency and on relative process speeds are not known in advance, or are known but only hold after an unknown time. Finally, we demonstrate that diam P is the weakest failure detector for solving WME, and present an algorithm that solves WME using diam P with a majority of correct processes.

The Weak Mutual Exclusion (WME) is a recently proposed abstraction which, analogously to classical Distributed Mutual Exclusion (DME), permits to serialize concurrent accesses to a shared resource. Unlike DME, however, the WME abstraction regulates the access to a replicated shared resource and is solvable in the presence of less restrictive synchrony assumptions, i.e. in an asynchronous system augmented with an eventually perfect failure detector. This paper presents an efficient WME algorithm which outperforms previous solutions in terms of both communication latency and message complexity, while relying on minimal synchrony assumptions.

At current date the problem of how to build distributed and replicated software transactional memory (STM) to enhance both dependability and performance is still largely unexplored. This paper fills this gap by presenting D2STM, a replicated STM whose consistency is ensured in a transparent manner, even in the presence of failures. Strong consistency is enforced at transaction commit time by a non-blocking distributed certification scheme, which we name BFC (bloom filter certification). BFC exploits a novel bloom filter-based encoding mechanism that permits to significantly reduce the overheads of replica coordination at the cost of a user tunable increase in the probability of transaction abort. Through an extensive experimental study based on standard STM benchmarks we show that the BFC scheme permits to achieve remarkable performance gains even for negligible (e.g. 1%) increases of the transaction abort rate.

Gossip, or epidemic, protocols have emerged as a highly scalable and resilient approach to implement several application level services such as reliable multicast, data aggregation, publish-subscribe, among others. All these protocols organize nodes in an unstructured random overlay network. In many cases, it is interesting to bias the random overlay in order to optimize some efficiency criteria, for instance, to reduce the stretch of the overlay routing. In this paper we propose X-BOT, a new protocol that allows to bias the topology of an unstructured gossip overlay network. X-BOT is completely decentralized and, unlike previous approaches, preserves several key properties of the original (non-biased) overlay (most notably, the node degree and consequently, the overlay connectivity). Experimental results show that X-BOT can generate more efficient overlays than previous approaches.

Abstract Replication of data items among different nodes of a wireless infrastructure‐less network may be an efficient technique to increase data availability and improve data access latency. This paper proposes a novel algorithm to distribute data items among nodes in these networks. The goal of the algorithm is to deploy the replicas of the data items in such a way that they are sufficiently distant from each other to prevent excessive redundancy but, simultaneously, they remain close enough to each participant, such that data retrieval can be achieved using a small number of messages. The paper describes the algorithm and provides its performance evaluation for different configurations. Copyright © 2008 John Wiley & Sons, Ltd.

This paper proposes a novel database replication algorithm that offers strong consistency (linearizable semantics) and allows reads and non-conflicting writes to execute in parallel in multiple replicas. The proposed algorithm supports the use of quorums to trade the availability/efficiency of read and write operations, making a bridge between consensus-based and quorum based solutions for database replication. Furthermore, the algorithm offers better performance for linearizable read-only transactions with a negligible impact on write transactions.

In epidemic or gossip-based multicast protocols, each node simply relays each message to some random neighbors, such that all destinations receive it at least once with high probability. In sharp contrast, structured multicast protocols explicitly build and use a spanning tree to take advantage of efficient paths, and aim at having each message received exactly once. Unfortunately, when failures occur, the tree must be rebuilt. Gossiping thus provides simplicity and resilience at the expense of performance and resource efficiency. In this paper we propose a novel technique that exploits knowledge about the environment to schedule payload transmission when gossiping. The resulting protocol retains the desirable qualities of gossip, but approximates the performance of structured multicast. In some sense, instead of imposing structure by construction, we let it emerge from the operation of the gossip protocol. Experimental evaluation shows that this approach is effective even when knowledge about the environment is only approximate.

Gossip, or epidemic, protocols have emerged as a powerful strategy to implement highly scalable and resilient reliable broadcast primitives. Due to scalability reasons, each participant in a gossip protocol maintains a partial view of the system. The reliability of the gossip protocol depends upon some critical properties of these views, such as degree distribution and clustering coefficient. Several algorithms have been proposed to maintain partial views for gossip protocols. In this paper, we show that under a high number of faults, these algorithms take a long time to restore the desirable view properties. To address this problem, we present HyParView, a new membership protocol to support gossip-based broadcast that ensures high levels of reliability even in the presence of high rates of node failure. The HyParView protocol is based on a novel approach that relies in the use of two distinct partial views, which are maintained with different goals by different strategies.

Tutorials are an important part of the DSN program. They provide an opportunity for attendees to acquire a basic understanding of, and familiarity with, several state of the art topics related to the dependability, security and resilience of systems and networks. Tutorial proposals providing guidance on how technology can be applied successfully in practical systems were particularly encouraged.

Database replication has been a common feature in database management systems (DBMSs) for a long time. In particular, asynchronous or lazy propagation of updates provides a simple yet efficient way of increasing performance and data availability and is widely available across the DBMS product spectrum. High end systems additionally offer sophisticated conflict resolution and data propagation options as well as, synchronous replication based on distributed locking and two-phase commit protocols. This paper presents GORDA architecture and programming interface (GAPI), that enables different replication strategies to be implemented once and deployed in multiple DBMSs. This is achieved by proposing a reflective interface to transaction processing instead of relying on-client interfaces or ad-hoc server extensions. The proposed approach is thus cost-effective, in enabling reuse of replication protocols or components in multiple DBMSs, as well as potentially efficient, as it allows close coupling with DBMS internals.

There is an inherent trade-off between epidemic and deterministic tree-based broadcast primitives. Tree-based approaches have a small message complexity in steady-state but are very fragile in the presence of faults. Gossip, or epidemic, protocols have a higher message complexity but also offer much higher resilience. This paper proposes an integrated broadcast scheme that combines both approaches. We use a low cost scheme to build and maintain broadcast trees embedded on a gossip-based overlay. The protocol sends the message payload preferably via tree branches but uses the remaining links of the gossip overlay for fast recovery and expedite tree healing. Experimental evaluation presented in the paper shows that our new strategy has a low overhead and that is able to support large number of faults while maintaining a high reliability.

Internet-based communication is currently in a hype. People utilize Internet services more and more to communicate with each other, e.g., via VoIP or chat. The next step would be to reutilize the same applications to achieve ubiquitous communication, anytime and anywhere, also where network support is not available, such as in ad-hoc networks. Existing Internet protocols must be modified for working in the ad-hoc server-less environment. The session initiation protocol (SIP) is a fundamental element in the Internet for establishing multimedia communication sessions. However, SIP cannot be used in ad-hoc networks, as it relies on the support of SIP servers in the network; e.g, in ad-hoc networks it is not possible to locate SIP users since the assistance of a dedicated SIP server is missing. A solution for this problem is presented in this paper which describes and evaluates a fully decentralized mechanism for locating SIP users in ad-hoc networks

In ubiquitous networks, the multiple devices carried by an user may unintentionally expose information about her habits or preferences. This information leakage can compromise the users' right to privacy. A common approach to increase privacy is to hide the user real identity under a pseudonym. Unfortunately, pseudonyms may interfere with the reputation systems that are often used to assert the reliability of the information provided by the participants in the network. This paper presents a framework for combining anonymity with reputation and shows that it can be configured to provide a desired degree of balance between these two conflicting goals. The proposed solution leverages on well-known cryptographic techniques, such as public key infrastructure and blind signatures

Flooding is an expensive operation that is often required in the operation of mobile ad hoc networks (MANETs). In this paper, we present a novel algorithm to reduce the overhead imposed by flooding operations. The algorithm improves previous results by using a distributed function to elect the nodes that will provide the highest additional coverage to previous retransmissions. The algorithm does not require any signalling or impose special requirements on the participating devices

Total order broadcast protocols have been successfully applied as the basis for the construction of many fault-tolerant distributed systems. Unfortunately, the implementation of such a primitive can be expensive both in terms of communication steps and of number of messages exchanged. To alleviate this problem, optimistic total order protocols have been proposed. This paper addresses the problem of offering optimistic total order in geographically wide-area systems. We present a protocol that outperforms previous work, by minimizing the average latency of the optimistic notification

This paper proposes a distributed and scalable publish-subscribe broker with support for QoS. The broker, called IndiQoS, leverages on existing mechanisms to reserve resources in the underlying network and on an overlay network of peer-to-peer rendezvous nodes, to automatically select QoS-capable paths. By avoiding flooding of either QoS reservations or link-state information, IndiQoS is able to scale with respect to network size and number of reservations. Experimental results show the validity of our approach

This work presents a novel peer-to-peer system that is particularly well suited to support context-aware computing. The system, called GeoPeer, aims to combine the advantages of peer-to-peer systems that implement distributed hash tables with the suitability of geographical routing for supporting location-constrained queries and information dissemination. GeoPeer is comprised of two fundamental components: a Delaunay triangulation used to build a connected lattice of nodes and a mechanism to manage long range contacts that allows good routing performance, despite unbalanced distribution of nodes.

In this paper we propose a novel probabilistic broadcast protocol that reduces the average end-to-end latency by dynamically adapting to network topology and traffic conditions. It does so by using an unique strategy that consists in adjusting the fanout and preferred targets for different gossip rounds as a function of the properties of each node. Node classification is light-weight and integrated in the protocol membership management. Furthermore, each node is not required to have full knowledge of the group membership or of the network topology. The paper shows how the protocol can be configured and evaluates its performance with a detailed simulation model.

This paper presents a novel adaptation mechanism that allows every node of a gossip-based broadcast algorithm to adjust the rate of message emission 1) to the amount of resources available to the nodes within the same broadcast group and 2) to the global level of congestion in the system. The adaptation mechanism can be applied to all gossip-based broadcast algorithms we know of and makes their use more realistic in practical situations where nodes have limited resources whose quantity changes dynamically with time without decreasing the reliability. 1

In publish-subscribe systems, multicast is an efficient way to propagate information from the publishers to a group of subscribers. This paper studies the problem of mapping a large set of subscriptions into a fixed, smaller set of multicast groups in order to support efficiently the dissemination of events. Given the large search space, it is infeasible to obtain the optimal solution in reasonable time. To address this difficulty, the paper proposes and evaluates a genetic search solution for the mapping problem.

Epidemic, or probabilistic, multicast protocols have emerged as a variable mechanism to circumvent the scalability problems of reliable multicast protocols. However, most existing epidemic approaches use connectionless transport protocols to exchange messages and rely on the intrinsic robustness of the epidemic dissemination to mask network omissions. Unfortunately, such an approach is not network-friendly, since the epidemic protocol makes no effort to reduce the load imposed on the network when the system is congested. In this paper, we propose a novel epidemic protocol whose main characteristic is to be network-friendly. This property is achieved by relying on connection-oriented transport connections, such as TCP/IP, to support the communication among peers. Since during congestion messages accumulate in the border of the network, the protocol uses an innovative buffer management scheme, which combines different selection techniques to discard messages upon overflow. This technique improves the quality of the information delivered to the application during periods of network congestion. The protocol has been implemented and the benefits of the approach are illustrated using a combination of experimental and simulation results.

Semantic reliability is a novel correctness criterion for multicast protocols based on the concept of message obsolescence: A message becomes obsolete when its content or purpose is superseded by a subsequent message. By exploiting obsolescence, a reliable multicast protocol may drop irrelevant messages to find additional buffer space for new messages. This makes the multicast protocol more resilient to transient performance perturbations of group members, thus improving throughput stability. This paper describes our experience in developing a suite of semantically reliable protocols. It summarizes the motivation, definition, and algorithmic issues and presents performance figures obtained with a running implementation. The data obtained experimentally is compared with analytic and simulation models. This comparison allows us to confirm the validity of these models and the usefulness of the approach. Finally, the paper reports the application of our prototype to distributed multiplayer games.

Atomic broadcast is a fundamental problem of distributed systems: It states that messages must be delivered in the same order to their destination processes. This paper describes a solution to this problem in asynchronous distributed systems in which processes can crash and recover. A consensus-based solution to atomic broadcast problem has been designed by Chandra and Toueg for asynchronous distributed systems where crashed processes do not recover. We extend this approach: it transforms any consensus protocol suited to the crash-recovery model into an atomic broadcast protocol suited to the same model. We show that atomic broadcast can be implemented requiring few additional log operations in excess of those required by the consensus. The paper also discusses how additional log operations can improve the protocol in terms of faster recovery and better throughput. To illustrate the use of the protocol, the paper also describes a solution to the replica management problem in asynchronous distributed systems in which processes can crash and recover. The proposed technique makes a bridge between established results on weighted voting and recent results on the consensus problem.

View synchrony (VS) is a powerful abstraction in the design and implementation of dependable distributed systems. By ensuring that processes deliver the same set of messages in each view, it allows them to maintain consistency across membership changes. However experience indicates that it is hard to combine strong reliability guarantees as offered by VS with stable high performance. In this paper we propose a novel abstraction, semantic view synchrony (SVS), that exploits the application's semantics to cope with high throughput applications. This is achieved by allowing some messages to be dropped while still preserving consistency when new views are installed. Thus, SVS inherits the elegance of view synchronous communication. The paper describes how SVS can be implemented and illustrates its usefulness in the context of distributed multi-player games.

A total order algorithm is a fundamental building block in the construction of distributed fault-tolerant applications. Unfortunately, the implementation of such a primitive can be expensive both in terms of communication steps and of number of messages exchanged. This problem is exacerbated in large-scale systems, where the performance of the algorithm may be limited by the presence of high-latency links. Typically, the most efficient total order algorithms do not provide uniform delivery and assume the availability of a perfect failure detector. Such algorithms may provide inconsistent results if the system assumptions do not hold. On the other hand, algorithms that assume an unreliable failure detector always provide consistent results but exhibit higher costs. This paper presents a new algorithm that combines the advantages of both approaches. On good periods, when the system is stable and processes are not suspected, the algorithm operates as if a perfect failure detector is assumed. Yet, the algorithm is indulgent, since it never violates consistency, even in runs where processes are suspected.

Distributed applications are becoming increasingly complex, often requiring the simultaneous use of several communication channels with different qualities-of-service. This paper presents the Appia system, a protocol kernel that supports applications requiring multiple coordinated channels. Appia offers a clean and elegant way for the application to express inter-channel constraints, such as, for instance, that all channels should provide consistent information about the failures of remote nodes. These constraints can be implemented as protocol layers that can be dynamically combined with other protocol layers.

The paper presents a generic framework to analyse the timing behavior of protocol graphs derived from the composition of micro-protocols. The model assumes that a protocol stack is composed of a set of protocol objects that interact through the exchange of events. A specific task is associated with each relevant protocol event and for each task, the periods and offsets are derived from a description of the interactions between adjacent protocols. To illustrate the use of the model, a stack of modular reliable group communication protocols for the CAN field-bus is analysed.

Traditional reliable broadcast protocols fail to scale to large settings. The paper proposes a reliable multicast protocol that integrates two approaches to deal with the large-scale dimension in group communication protocols: gossip-based probabilistic broadcast and semantic reliability. The aim of the resulting protocol is to improve the resiliency of the probabilistic protocol to network congestion by allocating scarce resources to semantically relevant messages. Although intuitively it seems that a straightforward combination of probabilistic and semantic reliable protocols is possible, we show that it offers disappointing results. Instead, we propose an architecture based on a specialized probabilistic semantically reliable layer and show that it produces the desired results. The combined primitive is thus scalable to large number of participants, highly resilient to network and process failures, and delivers a high quality data flow even when the load exceeds the available bandwidth. We present a summary of simulation results that compare different protocol configurations.

The round-trip duration measurement technique is fundamental in solving many problems in asynchronous distributed systems. In essence, this technique provides the means for reading remote clocks with a known and bounded error. Therefore, it is used as a fundamental building block in several clock synchronization algorithms. In general, the technique can be used to implement duration measurement services, such as that of the timely computing base model. In this paper we propose a new technique for measuring distributed durations that minimizes the measurement error and is able to keep this error almost stable. The new technique can be used to improve the precision of remote clock reading in certain situations. We provide a protocol that implements this new technique and present some evaluation results. The results clearly show that our solution is better than existing ones.

This paper presents a new neural network to solve the shortest path problem for inter-network routing. The proposed solution extends the traditional single-layer recurrent Hopfield architecture introducing a two-layer architecture that automatically guarantees an entire set of constraints held by any valid solution to the shortest path problem. This new method addresses some of the limitations of previous solutions, in particular the lack of reliability in what concerns successful and valid convergence. Experimental results show that an improvement in successful convergence can be achieved in certain classes of graphs. Additionally, computation performance is also improved at the expense of slightly worse results.

Group communication, providing virtual synchrony semantics, is a powerful paradigm for building distributed applications. For applications that require a large number of groups, significant performance gains can be attained if these groups share the resources required to provide virtual synchrony. A service that maps multiple user groups onto a small number of instances of a virtually synchronous implementation is called a Light-Weight Group Service. The paper describes the design of a light-weight group service able to operate in partitionable networks. Partitions pose challenges to the design of this service, in particular because inconsistent mapping decisions can be made when the system is partitioned. The paper focuses on the design of reconciliation mechanisms needed when a partition is healed.

Atomic broadcast is a fundamental problem of distributed systems: it states that messages must be delivered in the same order to their destination processes. This paper describes a solution to this problem in asynchronous distributed systems in which processes can crash and recover. A consensus-based solution to atomic broadcast problem has been designed by Chandra and Toueg (1996) for asynchronous distributed systems where crashed processes do nor recover. Although our solution is based on different algorithmic principles, it follows the same approach: it transforms any consensus protocol suited to the crash-recovery model into an atomic broadcast protocol suited to the same model. We show that atomic broadcast can be implemented without requiring any additional log operations in excess of those required by the consensus. The paper also discusses how additional log operations can improve the protocol in terms of faster recovery and better throughput.

A causal ordering protocol ensures that if two messages are causally related and have the same destination, they are delivered to the application in their sending order. Causal order strongly simplifies the development of distributed object oriented systems. To prevent causal order violation, either messages may be forced to wait for messages in their past, or late messages may have to be discarded. For a real time setting, the first approach is not suitable since when a message misses a deadline, all the messages that causally depend on it may also be forced to miss their deadlines. We propose a novel causal ordering abstraction that takes message deadlines into consideration. Two implementations are proposed in the context of multicast and broadcast communication that deliver as many messages as possible to the application. Examples of distributed soft real time applications that benefit from the use of a deadline-constrained causal ordering primitive are given.

Reliable multicast protocols can strongly simplify the design of distributed applications. However it is hard to sustain a high multicast throughput when groups are large and heterogeneous. In an attempt to overcome this limitation, previous work has focused on weakening reliability properties. The authors introduce a novel reliability model that exploits semantic knowledge to decide in which specific conditions messages can be purged without compromising application correctness. This model is based on the concept of message obsolescence: a message becomes obsolete when its content or purpose is overwritten by a subsequent message. We show that message obsolescence can be expressed in a generic way and can be used to configure the system to achieve higher multicast throughput.

We present a new scalable fault-tolerant algorithm which ensures total order delivery of messages sent to multiple groups of processes. Our algorithm is particularly well suited for large scale systems because: (1) any process can multicast a message to one or more groups of processes without being forced to join those groups; (2) inter-group total order is ensured system-wide but, for each individual multicast, the number and size of messages exchanged depends only on the number of addressees; (3) process failure detection does not need to be reliable. Our algorithm also exhibits a modular design. It uses two companion protocols, namely a reliable multicast protocol and a consensus protocol, and these protocols are not required to use the same communication channels or to share common variables with the total order protocol. This approach follows a design methodology based on the composition of (encapsulated) micro-protocols.

This paper presents a new fault-tolerant clock synchronization algorithm designed for the Controller Area Network (CAN). The algorithm provides all correct processes of the system with a global timebase, despite the occurrence of faults in the network or in a minority of processes. Such global time-frame is a requirement of many distributed real-time control systems. Designing protocols for CAN is justified by the increasing use of this network in industrial automation applications. CAN owns a number of unique properties that can be used to improve the precision and performance of a clock synchronization algorithm. Unfortunately, some of its features also make the implementation of a fault-tolerant clock synchronization service a non-trivial task. Our algorithm addresses both the positive and the negative aspects of CAN.

The virtual synchrony model for group communication has proven to be a powerful paradigm for building distributed applications. In applications that use a large number of groups, significant performance gains can be attained if these groups share the resources required to provide virtual synchrony. A service that maps user groups onto instances of a virtually synchronous implementation is called a Light-Weight Group Service. This paper discusses the Light-Weight Group protocols in dynamic environments, where mappings cannot be defined a priori and may change over time. We show that it is possible to establish mappings that promote sharing and, at the same time, minimize interference. These mappings can be established in an automated manner using heuristics applied locally at each node. Experiments using an implementation in the Horus system show that significant performance improvements can be achieved with this approach.

Totally ordered multicast protocols have proved to be extremely useful in supporting fault-tolerant distributed applications. This paper compares the performance of the two main classes of protocols providing total order in large-scale systems (token-site and symmetric protocols) and proposes a new dynamic hybrid protocol that, when applied to systems where the topology/traffic patterns are not known a priori, offers a much lower latency than any of the previous classes of protocols in isolation.

The virtual synchrony model for group communication has proven to be a powerful paradigm for building distributed applications. Implementations of virtual synchrony usually require the use of failure detectors and failure recovery protocols. In applications that require the use of a large number of groups, significant performance gains can be attained if these groups share the resources required to provide virtual synchrony. A service that maps user groups onto instances of a virtually synchronous implementation is called a light-weight group service. This paper proposes a new design for the light-weight group protocols that enables the usage of this service in a transparent manner as a test case, the new design was implemented in the Horus system, although the underlying principles can be applied to other architectures as well. The paper also presents performance results from this implementation.

In recent years there has been a growing interest in developing communication systems that are able to deliver messages respecting potential causality. Unfortunately, causal delivery cannot be provided without costs: extra delays may be induced on message delivery or processes may be required to maintain and exchange records of causal relations. In this paper we present an extension to previous work on compression of causal information using knowledge about the topology of the communication structure. In order to make practical use of this result, we present a methodology to model the communication system. The technique exploits the physical structure of existing networks, in particular its hierarchical nature, to create a communication graph where causal separators match the underlying physical and administrative organization. We show that this approach can be applied to existing large-scale systems, providing the means for using topological timestamping with negligible overhead.

Although many algorithms and implementations of replicated services have been developed, most have embedded aspects of the replication management in the invocation protocol. This makes it extremely difficult to modify the replication protocol without changing the protocol used by the clients, and causes an undesirable violation of both transparency and modularity. The GRIP protocol supports the fault-tolerant remote invocation of replicated services, providing not only the usual location transparency but also transparency of replication semantics. Our approach is independent of the details of the replica control protocol used to maintain the consistency of server replicas. We use a lightweight remote invocation protocol in order to minimize the impact on the client of issues such as scale and replication consistency maintenance. Furthermore, unlike most previous systems we provide explicit support for weakly consistent replication protocols. GRIP is designed as a collection of modular services, which can be configured according to the needs of the application.>

Presents a processor group membership protocol designed to run on top of a local area network. The protocol maintains information about a selected group of stations that explicitly join the protocol by keeping a replica of a global membership table at every member. Additionally, the protocol guarantees that a given station always occupies the same entry in the table. As a result, table indexes uniquely and universally identify a station and can thus be used as short identifiers. The interest of a processor group membership is twofold: it is a powerful auxiliary for process group membership management and it provides support for efficient message addressing.>

A clock synchronization algorithm was given by P. Verissimo et al. (1989), dubbed a posteriori agreement, a variant of the convergence nonaveraging technique. By exploiting the characteristics of broadcast networks, the effect of message delivery delay variance is largely reduced. In consequence, the precision achieved by the algorithm is drastically improved. Accuracy preservation is near to optimal. A particular materialization of this algorithm, implemented as a time service of the xAMp group communications system, is given here. The algorithm was implemented using some of the primitives offered by xAMp, which simplified the work and stressed its advantages. Performance results for this implementation obtained on two different infrastructures are presented. Timings validate the design choices and clearly show that the algorithm is able to provide improved precision without compromising accuracy and reliability.>

The xAMp is a highly versatile group communications service aimed at supporting the development of distributed applications with different dependability, functionality, and performance requirements. These range from unreliable and nonordered to atomic multicast, and are enhanced by efficient group addressing and management support. The basic protocols are synchronous, clockless and designed to be used over broadcast local area networks (LANs), and are portable to a number of them. The functionality provided yields a reasonably complete solution to the problem of reliable group communication. While other protocols offer similar services, the authors follow a novel engineering approach by deriving all qualities of services from a single basic procedure. Thus, their implementation shares data structures, procedures, failure-recovery algorithms, and group monitor services, resulting in a highly integrated package.>

This paper deals with the problem of reliable group communication for distributed applications, in the context of the Reliable Broadcast class of protocols. An atomic multicast protocol for token passing Lans is presented. The actual implementation is on an 8802/4 Token-bus, although it is applicable to 8802/5 Token-rings and the FDDI Fibre-Optic network.