As Distributed Ledger Technologies (DLTs) mature, the inherent performance and scalability shortcomings of linearly structured blockchain designs become better understood. Protocols based on Directed Acyclic Graphs (DAGs) have been proposed to address such shortcomings. DAG-based protocols differ from traditional DLTs in the way they build and represent knowledge about transactions and relations between them. While traditional DLTs have straightforward homogeneous semantic attached to blocks and links between blocks, the semantic of vertices and edges in DAG-based protocols is nuanced and varied. In this work, we identify almost a dozen of knowledge-building dimensions in DAG-based DLTs, none of which have been studied before. Knowledge-building is important in DAG-based DLTs because of its significant impact on the size of the DAG, the pace at which new transactions are added, the finality of transactions, and so on. We analyze 40 DAG-based DLTs from this perspective, summarize our results in a taxonomy, and identify a number of research gaps.

Accumulation of blockchain data has led to a significant body of studies pertaining to block generation performance, financial assets, user interactions, etc. At the same time, surprisingly little attention has been dedicated to analyzing system characteristics of transactional workloads and to generating synthetic workloads. We argue that such analysis is imperative for multiple design and assessment goals. In this paper, we provide a comprehensive analysis of transaction features in the workload of three UTXO-based blockchain systems. The analysis covers 15 months and includes metrics such as input and output count, transaction size, temporal features, as well as their correlations and evolution over time. A few of the findings are quite surprising and have never been observed in the past. For example, we observe a shift in the distribution of output count over time. We also provide the first synthetic workload generator for UTXO transactions and release it as open source.

Systems managing Verifiable Credentials are becoming increasingly popular. Unfortunately, their support for revoking previously issued credentials allows verifiers to effectively monitor the validity of the credentials, which is sensitive information. While the issue started to gain recognition, no adequate solution has been proposed so far. In this work, we propose a novel framework for time-limited continuous verification. The holder is able to individually configure the verification period when sharing information with the verifier, and the system guarantees proven untraceability of the revocation status after the verification period expires. Differently from existing systems, the implementation adopts a more scalable blacklist approach where tokens corresponding to revoked credentials are stored in the registry. The approach employs ZK proofs that allow holders to prove non-membership in the blacklist. In addition to theoretically proving security, we evaluate the approach analytically and experimentally and show that it significantly improves bandwidth consumption on the holder while being on par with state-of-the-art solutions with respect to the other performance metrics.

AI inference workflows are typically structured as a pipeline or graph of AI programs triggered by events. As events occur, the AIs perform inference or classification tasks under time pressure to respond or take some action. Standard techniques that reduce latency in other streaming settings (such as caching and optimization-driven scheduling) are of limited value because AI data access patterns (models, databases) change depending on the triggering event: a significant departure from traditional streaming. In this work, we propose a novel affinity grouping mechanism that makes it easier for developers to express application-specific data access correlations, enabling coordinated management of data objects in server clusters hosting streaming inference tasks. Our proposals are thus complementary to other approaches such as caching and scheduling. Experiments confirm the limitations of standard techniques, while showing that the proposed mechanism is able to maintain significantly lower latency as workload and scale-out increase, and yet requires only minor code changes.

Due to the sheer volume of data, data owners (e.g., hospitals or other data collectors) tend to outsource their data to cloud service providers (CSPs) for the purpose of storage and analytics. However, privacy concerns about genomic and phenotype data significantly limit the data owners’ choice. In this work, we propose the first solution, to the best of our knowledge, that allows a CSP to perform efficient and privacy-preserving search and analysis over encrypted genomic and phenotype data that is multi-tenant, i.e. owned by multiple hospitals. We first propose an encryption mechanism for phenotype data, where each data owner is allowed to encrypt its data with a unique secret key. Moreover, the ciphertext supports privacy-preserving search and, consequently, enables the identification of the case and control groups for a genome-wide association study (GWAS) without any privacy violations. Furthermore, we provide a per-query based authorization mechanism for a client to access and operate on the data stored at the CSP. Additionally, we apply multi-key fully homomorphic encryption to encrypt genomic data and show how to compute GWAS statistics (e.g., chi-square distribution test) over the ciphertext of individuals in the identified case and control groups. Thus, for the first time, the proposed scheme provides privacy-preserving computation for the entire GWAS pipeline. Finally, we implement the proposed scheme and run experiments over a real-life genomic dataset to show its effectiveness. The result shows that the proposed solution is capable to efficiently identify the case/control groups and subsequently conduct GWAS on the identified case/control groups.

We present a new approach for designing reliable and scalable overlay networks to support topic-based pub/sub communication. We propose the${{\mathsf {MinAvg}}-{k}{\mathsf {TCO}}}$problem parameterized by${k}$: use the minimum number of edges to create a${k}$k-topic-connected overlay(${{k}TCO}$) for pub/sub systems, i.e., for each topic, the sub-overlay induced by nodes interested in the topic is${k}$-connected. We prove the NP-completeness of${{\mathsf {MinAvg}}-{k}{\mathsf {TCO}}}$and show a lower-bound for the hardness of its approximation. For${{\mathsf {MinAvg}}-{2}{\mathsf {TCO}}}$, we present GM2, the first polynomial-time algorithm with an approximation ratio. For${{\mathsf {MinAvg}}-{k}{\mathsf {TCO}}}$, where${k} \geq {2}$, we propose HararyPT, a simple and efficient heuristic that aligns nodes across different sub-overlays. We experimentally demonstrate the scalability of GM2 and HararyPT with regards to overlay quality under representative pub/sub workloads. GM2 outputs${{2}TCO}$with an empirically insignificant increase in the average node degree, e.g., an increase by 4 in a 1000-node network, as compared to the baseline${{1}TCO}$produced by the best-known algorithm. Moreover, GM2 reduces the topic diameters by around 50 percent with respect to those in${{1}TCO}$.

Increasing affordability of genome sequencing and, as a consequence, widespread availability of genomic data opens up new opportunities for the field of medicine, as also evident from the emergence of popular cloud-based offerings in this area, such as Google Genomics [1]. To utilize this data more efficiently, it is crucial that different entities share their data with each other. However, such data sharing is risky mainly due to privacy concerns. In this article, we attempt to provide a privacy-preserving and efficient solution for the “similar patient search” problem among several parties (e.g., hospitals) by addressing the shortcomings of previous attempts. We consider a scenario in which each hospital has its own genomic dataset and the goal of a physician (or researcher) is to search for a patient similar to a given one (based on a genomic makeup) among all the hospitals in the system. To enable this search, we propose a hierarchical index structure to index each hospital’s dataset with low memory requirement. Furthermore, we develop a novel privacy-preserving index merging mechanism that generates a common search index from individual indices of each hospital to significantly improve the search efficiency. We also consider the storage of medical information associated with genomic data of a patient (e.g., diagnosis and treatment). We allow access to this information via a fine-grained access control policy that we develop through the combination of standard symmetric encryption and ciphertext policy attribute-based encryption. Using this mechanism, a physician can search for similar patients and obtain medical information about the matching records if the access policy holds. We conduct experiments on large-scale genomic data and show the high efficiency of the proposed scheme.

Thanks to the popularity of mobile devices numerous location-based services (LBS) have emerged. While several privacy-preserving solutions for LBS have been proposed, most of these solutions do not consider the fact that LBS are typically cloud-based nowadays. Outsourcing data and computation to the cloud raises a number of significant challenges related to data confidentiality, user identity and query privacy, fine-grained access control, and query expressiveness. In this work, we propose a privacy-preserving framework for outsourcing LBS to the cloud. The framework supports multi-location queries with fine-grained access control, and search by location attributes, while providing semantic security. In particular, the framework implements a new model that allows the user to govern the trade-off between precision and privacy on a dynamic per-query basis. We also provide a security analysis to show that the proposed scheme preserves privacy in the presence of different threats. We also show the viability of our proposed solution and scalability with the number of locations through an experimental evaluation, using a real-life OpenStreetMap dataset.

A number of emerging multimedia applications, such as webinars, require users to interact by exchanging media streams. In such application there are multiple interacting participants which both produce and consume media content and a set of participants which are only consumers. Keeping the end-to-end latency as low as possible while not violating bandwidth constraints is one of the most important requirements for this type of application. While there exists solutions to this problem for applications such as multi-party video conferencing, they rely on dedicated infrastructures which may be expensive and not available to all users. On the other hand, decentralized P2P solutions have been focusing on single source media streaming, which does not consider multiple interactive participants. In this paper, we propose Maelstream, a self-organizing media streaming solution that supports multiple interacting participants as well as a large number of consumers. Maelstream uses gossip protocols to generate multiple latency-aware streaming trees on top of a P2P overlay. We have evaluated our solution with simulations implemented using Peersim and ns-3 simulators, and compared Maelstream with Chunkyspread, an unstructured protocol capable of fine-tuning latency. We show that Maelstream can achieve low end-to-end latency and scales well with the number of streams.

In recent years, notification services for social networks, mobile apps, messaging systems and other electronic services have become truly ubiquitous. When a new content becomes available, the service sends an instant notification to the user. When the content is produced in massive quantities, and it includes both large-size media and a lot of meta-information, it gives rise to a major challenge of selecting content to notify about and information to include in such notifications. We tackle three important challenges in realizing rich notification delivery: (1) content and presentation utility modeling, (2) notification selection and (3) scheduling of delivery. We consider a number of progressive presentation levels for the content. Since utility is subjective and hard to model, we rely on real data and user surveys. We model the content utility by learning from large-scale real world data collected from Spotify music streaming service. For the utility of the presentation levels we rely on user surveys. Blending these two techniques together, we derive utility of notifications with different presentation levels. We then model the selection and delivery of rich notifications as an optimization problem with a goal to maximize the utility of notifications under resource budget constraints. We validate our system with large-scale simulations driven by the real-world de-identified traces obtained from Spotify. With the help of several baseline approaches we show that our solution is adaptive and resource efficient.

Overlay design for topic-based publish/subscribe (pub/sub) systems is of primary importance because the overlay forms the basis for the system and directly impacts its performance. This paper focuses on the MinAvg-TCO problem: Use the minimum number of edges to construct a topic-connected overlay (TCO) such that all nodes that are interested in the same topic are organized in a directly connected dissemination suboverlay. Existing algorithms for MinAvg-TCO suffer from three key drawbacks: 1) prohibitively high runtime cost; 2) reliance on global knowledge and centralized operation; and 3) nonincremental operation by reconstructing the TCO from scratch. From a practical point of view, these are all severe limitations. To address these concerns, we develop algorithms that dynamically join multiple TCOs. Inspired by the divide-and-conquer character of this idea, we derive a number of algorithms for the original MinAvg-TCO problem that accommodate a variety of practical pub/sub workloads. Both theoretical analysis and experimental evaluations demonstrate that our divide-and-conquer algorithms seek a balance between time efficiency and the number of edges required: Our algorithms cost a fraction (up to 1.67%) of the runtime cost of their greedy alternatives, which come at the expense of an empirically insignificant increase in the average node degree. Furthermore, in order to reduce the probability of poor partitioning at the divide phase, we develop a bulk-lightweight partitioning scheme on top of random partitioning. This more refined partitioning imposes a marginally higher runtime cost, but leads to improvements in the output TCOs, including average node degrees and topic diameters.

With the advent of recent technological advances, more demanding tele-immersive applications have started to emerge. In the World Opera application, artists from different opera houses across the globe can participate in a single united performance, and interact almost as if they were co-located. One of the main design challenges in this application domain is to assess to what extent the inevitable failures of some of the numerous and complex hardware, software, and network components affect the quality of experience for the user. This challenge cannot be addressed by traditional system-centric methods for dependability evaluation, which do not take personalized user perspective into account when considering meaningful and acceptable degradation of services. In this paper, we propose a novel method to assess the quality of experience in presence of failures, based on a new metric called perceived reliability. The method takes the human perspective into account and allows considering factors such as human perception of video and audio, characteristics of the audience, as well as performance elements and artistic content. This method can help system designers and engineers compare architectural variants and determine the dependability budget. We show the feasibility of our method by applying it to a World Opera performance. To this end, we construct a SAN-based model and run simulations in the Möbius framework. The obtained results provide useful guidelines for system engineers towards improving the quality of experience of World Opera performances despite the presence of failures.

We incorporate underlay information into overlay design for topic-based publish/subscribe (pub/sub) systems on geo-distributed data centers. We propose the MinAvg-WTCO problem that optimizes the weighted average node degree while constructing a topic-connected overlay (TCO), i.e., Each topic induces a connected sub-overlay among all nodes interested in this topic. Most existing TCO designs are oblivious to the low-level network infrastructure and assume edge equivalence. We prove that MinAvg-WTCO is NP-complete and difficult to approximate within a logarithmic factor with regard to the number of nodes. We devise several approximation algorithms for MinAvg-WTCO using different design techniques. Both theoretical analysis and empirical evaluation show that our designed algorithms tread the balance between overlay quality and runtime cost. Our algorithms significantly outperform the state of the art for TCO design that ignores edge differences.

Modern applications for distributed publish/subscribe systems often require stream aggregation capabilities along with rich data filtering. When compared to other distributed systems, aggregation in pub/sub differentiates itself as a complex problem which involves dynamic dissemination paths that are difficult to predict and optimize for a priori, temporal fluctuations in publication rates, and the mixed presence of aggregated and non-aggregated workloads. In this paper, we propose a formalization for the problem of minimizing communication traffic in the context of aggregation in pub/sub. We present a solution to this minimization problem by using a reduction to the well-known problem of minimum vertex cover in a bipartite graph. This solution is optimal under the strong assumption of complete knowledge of future publications. We call the resulting algorithm "Aggregation Decision, Optimal with Complete Knowledge" (ADOCK). We also show that under a dynamic setting without full knowledge, ADOCK can still be applied to produce a low, yet not necessarily optimal, communication cost. We also devise a computationally cheaper dynamic approach called "Aggregation Decision with Weighted Publication" (WAD). We compare our solutions experimentally using two real datasets and explore the trade-offs with respect to communication and computation costs.

Beyond offering the widely used keyword search function, many peer-to-peer systems nowadays support the subscription function. For example, Vuze allows users to create subscription filters based on the keyword search. Given the subscription, episodic or related content will be delivered to the users whenever new episodes are available. Unfortunately, these applications suffer from the downsides, for example, high network traffic in the nodes maintaining popular terms. In this paper, we propose the MTAF mechanism to overcome the issues. The key of MTAF is to carefully select a subset of terms without incurring false negatives and to forward the content item toward the home nodes of such selected terms for low content forwarding cost. Experimental results based on real datasets indicate that the proposed solutions are efficient compared to existing approaches. In particular, the similarity-based replication of filters is shown to mitigate the effect of hot spots that arise due to the fact that some document terms are substantially more popular than the others.

Publish/subscribe (pub/sub) is a popular communication paradigm in the design of large-scale distributed systems. A fundamental challenge in deploying pub/sub systems on a data center or a cloud infrastructure is efficient and cost-effective resource allocation that would allow delivery of notifications to all subscribers. In this paper, we provide answers to the following three fundamental questions: Given a pub/sub workload, (1) what is the minimum amount of resources needed to satisfy all the subscribers, (2) what is a cost-effective way to allocate resources for the given workload, and (3) what is the cost of hosting it on a public Infrastructure-as-a-Service (IaaS) provider like Amazon EC2. To answer these questions, we formulate a problem coined Minimum Cost Subscriber Satisfaction (MCSS). We prove MCSS to be NP-hard and provide an efficient heuristic solution based on a combination of optimizations. We evaluate the solution experimentally using real traces from Spotify and Twitter along with a pricing model from Amazon. We show the impact of each optimization using a naive solution as the baseline. Using a variety of practical scenarios for each dataset, we also show that our solution scales well for millions of subscribers and runs fast.

Publish/subscribe (pub/sub) is a popular communication paradigm in the design of large-scale distributed systems. A provider of a pub/sub service (whether centralized, peer-assisted, or based on a federated organization of cooperatively managed servers) commonly faces a fundamental challenge: given limited resources, how to maximize the satisfaction of subscribers? We provide, to the best of our knowledge, the first formal treatment of this problem by introducing two metrics that capture subscriber satisfaction in the presence of limited resources. This allows us to formulate matters as two new flavors of maximum coverage optimization problems. Unfortunately, both variants of the problem prove to be NP-hard. By subsequently providing formal approximation bounds and heuristics, we show, however, that efficient approximations can be attained. We validate our approach using real-world traces from Spotify and show that our solutions can be executed periodically in real-time in order to adapt to workload variations.

We incorporate fault tolerance in designing reliable and scalable overlay networks to support topic-based pub/sub communication. We propose the MinAvg- kTCO problem parameterized by k: use the minimum number of edges to create a k-topic-connected overlay (kTCO) for pub/sub systems, i.e., for each topic the sub-overlay induced by nodes interested in the topic is k-connected.

A number of recently proposed systems provide secure and privacy-preserving data dissemination by leveraging pre-existing social trust relations and effectively mapping them into communication links. However, as we show in this paper, the underlying trust graph may not be optimal as a communication overlay. It has relatively long path lengths and it can be easily partitioned in scenarios where users are unavailable for a fraction of time. Following this observation, we present a method for improving the robustness of trust-based overlays. Essentially, we start with an overlay derived from the trust graph and evolve it in a privacy-preserving fashion into one that lends itself to data dissemination. The experimental evaluation shows that our approach leads to overlays that are significantly more robust under churn, and exhibit lower path lengths than the underlying trust graph.

Evaluating new ideas for job scheduling or data transfer algorithms in large-scale grid systems is known to be notoriously challenging. Existing grid simulators expect to receive a realistic workload as an input. Such input is difficult to provide in absence of an in-depth study of representative grid workloads. In this work, we analyze the ATLAS workload processed on the resources of NDG Facility. ATLAS is one of the biggest grid technology users, with extreme demands for CPU power and bandwidth. The analysis is based on the data sample with ~1.6 million jobs, 1,723 TB of data transfer, and 873 years of processor time. Our additional contributions are (a) scalable workload models that can be used to generate a synthetic workload for a given number of jobs, (b) an open-source workload generator software integrated with existing grid simulators, and (c) suggestions for grid system designers based on the insights of data analysis.

It is a key challenge and fundamental problem in the design of distributed publish/subscribe systems to construct the underlying dissemination overlay. In this paper, we focus on effective practical solution for the Min Max-TCO problem: Create a topic-connected pub/sub overlay in which all nodes interested in the same topic are organized in a directly connected dissemination sub-overlay while keeping the maximum node degree to the minimum. Previously known solutions provided an extensive analysis of the problem and an algorithm that achieves a logarithmic approximation for Min Max-TCO. Yet, they did not focus on efficiency of the solution or feasibility of decentralized operation that would not require full knowledge of the system. Compared to these solutions, our proposed algorithm produces an overlay with marginally higher degrees. At the same time, it has drastically reduced runtime cost, which is corroborated by both theoretical analysis and empirical evaluation. The latter shows a speedup by a factor of more than 25 on average for typical pub/sub workloads.

Keyword-based content alert services, e.g., Google Alerts and Microsoft Live Alerts, empower the end users with the ability to automatically receive useful and most recent content. In this paper, we leverage the favorable properties of DHTs, such as scalability, and propose a design of a scalable keyword-based content alert service. The DHT-based architecture matches textual documents with queries based on document terms: For each term, the implementation assigns a home node that is responsible for handling documents and queries that contain the term. The main challenge of this keyword-based matching scheme is the high number of terms that appear in a typical document resulting in a high publication cost. Fortunately, a document can be forwarded to the home nodes of a carefully selected subset of terms without incurring false negatives. In this paper we focus on the MTAF problem of minimizing the number of selected terms to forward the published content. We show that the problem is NP-hardness, and consider centralized and DHT-based solutions. Experimental results based on real datasets indicate that the proposed solutions are efficient compared to existing approaches. In particular, the similarity-based replication of filters that is a key element of our solution is shown to mitigate the effect of hotspots that arise due to the fact that some document terms are substantially more popular than the others, both inside documents and queries.

State transfer mechanisms are an essential building block in the design of many distribution applications that replicate the state, such as partially replicated databases or view-synchronous group communication. When a reconfiguration occurs, a need arises to ship a subset of objects that constitute the application state to a subset of nodes in the system. The most commonly employed solution is to elect a leader that collects state objects and transmits them to the nodes that need to receive them. In this paper, we present the problem of communication-balanced state transfer wherein the goal is to distribute the load of communication due to state transfer evenly across the participating nodes. We propose an algorithm that achieves the optimal balance, analyze it, and describe how it can be used in a variety of applications. We evaluate the algorithm on a typical setup of partially replicated databases and show that it attains a significant improvement compared with existing approaches.

Leases have proved to be an effective concurrency control technique for distributed systems that are prone to failures. However, many benefits of leases are only realized when leases are granted for approximately the time of expected use. Correct assessment of lease duration has proven difficult for all but the simplest of resource allocation problems. In this paper, we present a model that captures a number of lease styles and semantics used in practice. We consider a few performance characteristics for lease-based systems and analytically derive how they are affected by lease duration. We confirm our analytical findings by running a set of experiments with the OO7 benchmark suite using a variety of workloads and fault loads.

Overlay network design for topic-based publish/subscribe systems is of primary importance because the overlay directly impacts the system's performance. Determining a topic-connected overlay, in which for every topic the graph induced by nodes interested in the topic is connected, is a fundamental problem. Existing algorithms for this problem suffer from three key drawbacks: (1) prohibitively high running time cost, (2) requirement of full system knowledge and centralized operation, and (3) constructing overlay from scratch. From a practical point of view, these are all significant limitations. To address these concerns, in this paper, we develop novel algorithms that efficiently solve the problem of dynamically joining two or more topic-connected overlays. Inspired from the divide-and-conquer character of our approach, we derive an algorithm that solves the original problem at a fraction (up to 1.7\%) of the running time cost of alternative solutions, but at the expense of an empirically insignificant increase in the average node degree.

Quorum-based schemes are one of the main abstractions in the design of data-sharing replicated systems. One of the most salient characteristics of a quorum system is its availability for operation, i.e., the probability that there exists a network component in the current system state that contains a quorum. The advent of highly-available global electronic services leads to ubiquitous deployment of multi-clustered replicated architectures with sites from multiple clusters connected by inherently unreliable wide-area networks. Yet, the traditional methods for analyzing availability have not been taking link failures into account.

We investigate the problem of designing a scalable overlay network to support decentralized topic-based pub/sub communication. We introduce a new optimization problem, called Minimum Topic-Connected Overlay (Min-TCO), that captures the tradeoff between the scalability of the overlay (in terms of the nodes' fanout) and the message forwarding overhead incurred by the communicating parties. Roughly, the Min-TCO problem is as follows: Given a collection of nodes and their subscriptions, connect the nodes using the minimum possible number of edges so that for each topic t, a message published on t could reach all the nodes interested in t by being forwarded by onlythe nodes interested in t.

View-oriented group communication is an important and widely used building block for constructing highly-available fault-tolerant systems. Unfortunately, group-communication based systems are extremely hard to test and debug due to a number of stateful complex algorithms deployed in parallel and the unique combination of distributed and concurrent programming paradigms that amplifies the non-determinism in the system behavior. In this work, we elaborate on the specific challenges we encountered during the process of testing DCS, a group communication component of the WebSphere (WAS) architecture, as well as on the methodology we have devised and employed in order to cope with these challenges. Our solution relies on a carefully compiled set of invariants that need to be preserved at every execution point and a log analyzer algorithm that performs cross-log verification for all the processes participating in the execution, as well as on of other techniques whose details are described in the paper.

This paper introduces a novel architecture for implementing content-based pub/sub communications on top of structured overlay networks. This architecture overcomes some well-known limitations of existing infrastructures, i.e. lack of self-configuration and of adaptiveness to dynamic changes. This is achieved by devising a mediator stratum between the rich event subscription semantics of content-based pub/sub systems and the standard logical addressing scheme of overlays. The paper describes details of the design and provides considerations in selecting the subscription-to-node and event-to-node mappings suitable for the solution. We identify the lack of native support for one-to-many communication by overlay networks as the main impediment for efficient system operation. The paper introduces a novel primitive for one-to-many message delivery, showing through simulation how this can improve performance of the architecture. The simulation study also shows performance comparison between the different mappings proposed as well as evaluation of other optimizations discussed in the paper

Proposes a new classification of executions with checkpoints that is based on the notion of k-rollback, indicating the maximal number of checkpoints that may need to be rolled back during recovery. The relation between known execution classes is explored, and it is shown that coordinated checkpointing, SZPF (strictly Z-path free) and ZPF (Z-path free) are 1-rollback mechanisms, while ZCF (Z-cycle free) is (n-1)-rollback, where n is the number of participants in an execution. A new class of executions, called d-BC (d-bounded cycles), is introduced, and is shown to be an [(n-1)/spl middot/d]-rollback mechanism (ZCF is a special case of d-BC for d=1). Finally, a d-BC protocol is presented. This protocol has the nice property that it does not impose any control information overhead on an application's messages, yet it only sends a few control messages of its own. Moreover, the protocol maintains information about recovery lines, which enables very efficient discovery of the most recent recovery line that existed a short time before the failure.