In this article, we propose and evaluate three different state recovery algorithms aimed for Paxos-one of the most popular distributed agreement protocols. Paxos is commonly used to maintain consistency among state machine replicas despite of failures of processes. The first algorithm, that we call FullSS, originates from the original Paxos and requires that the system frequently uses stable storage during regular (non-faulty) execution. The other two state recovery algorithms, ViewSS and EpochSS, scarcely require access to stable storage, and the recovering process must do much less work to restore its lost state, and to catch up on the current state of the system. We thoroughly analyze and compare the behavior of the three algorithms during state recovery and also during regular, non-faulty system execution, under various workloads (e.g., causing the network or CPU saturation). The experimental results show that by using ViewSS and EpochSS, we can significantly improve process recovery with respect to the original Paxos, if only it can be assumed that at any time a majority of replicas are up running (excluding those replicas that are just recovering). Moreover, these algorithms do not impact the performance of Paxos during regular (non-faulty) operation. However, FullSS is the only choice out of the three, if the system must tolerate catastrophic failures.

With the increased failure rate expected in future extreme scale supercomputers, process replication might become a viable alternative to check pointing. By default, the workload efficiency of replication is limited to 50% because of the additional resources that have to be used to execute the replicas of the application's processes. In this paper, we introduce intra-parallelization, a solution that avoids replicating all computation by introducing work-sharing between replicas. We show on a representative set of benchmarks that intra-parallelization allows achieving more than 50% efficiency without compromising fault tolerance.

As the level of parallelism in manycore processors keeps increasing, providing efficient mechanisms for thread synchronization in concurrent programs is becoming a major concern. On cache-coherent shared-memory processors, synchronization efficiency is ultimately limited by the performance of the underlying cache coherence protocol. This paper studies how hardware support for message passing can improve synchronization performance. Considering the ubiquitous problem of mutual exclusion, we adapt two state-of-the-art solutions used on shared-memory processors, namely the server approach and the combining approach, to leverage the potential of hardware message passing. We propose HybComb, a novel combining algorithm that uses both message passing and shared memory features of emerging hybrid processors. We also introduce MP-Server, a straightforward adaptation of the server approach to hardware message passing. Evaluation on Tilera's TILE-Gx processor shows that MP-Server can execute contended critical sections with unprecedented throughput, as stalls related to cache coherence are removed from the critical path. HybComb can achieve comparable performance, while avoiding the need to dedicate server cores. Consequently, our queue and stack implementations, based on MP-Server and HybComb, largely outperform their most efficient pure-shared-memory counterparts.

We introduce Distal, a new framework that simplifies turning pseudocode of fault tolerant distributed algorithms into efficient executable code. Without proper tool support, even small amounts of pseudocode normally ends up in several thousands of non-trivial lines of Java or C++. Distal is implemented as a library in Scala and consists of two main parts: a domain specific language (DSL) in which algorithms are expressed and an efficient messaging layer that deals with low level issues such as connection management, threading and (de)serialization. The DSL is designed such that implementations of distributed algorithms highly resemble the pseudocode found in research papers. By writing code that is close to the protocol description, one can be more convinced that the implemented system really reflects the protocol specification on paper. Distal does not only make it simple and intuitive to implement distributed algorithms but it also leads to efficient implementations.

The traditional architecture used by implementations of Replicated State Machines (RSM) does not fully exploit modern multi-core CPUs. This is increasingly the limiting factor in their performance, because network speeds are increasing much faster than the single-thread performance of CPUs. Thus, when deployed on Gigabit-class networks and exposed to a workload of small to medium size client requests, RSMs are often CPU-bound, as they are only able to leverage a few cores, even though many more may be available. In this work, we revisit the traditional architecture of a RSM implementation, showing how it can be parallelized so that its performance scales with the number of cores in the nodes. We do so by applying several good practices of concurrent programming to the specific case of state machine replication, including staged execution, workload partitioning, actors, and non-blocking data structures. We describe and test a Java prototype of our architecture, based on the Paxos protocol. With a workload consisting of small requests, we achieve a six times improvement in throughput using eight cores. More generally, in all our experiments we have consistently reached the limits of the network subsystem by using up to 12 cores, and do not observe any degradation when using up to 24 cores. Furthermore, the profiling results of our implementation show that even at peak throughput contention between threads is minimal, suggesting that the throughput would continue scaling given a faster network.

The high failure rate expected for future supercomputers requires the design of new fault tolerant solutions. Most checkpointing protocols are designed to work with any message-passing application but suffer from scalability issues at extreme scale. We take a different approach: We identify a property common to many HPC applications, namely channel-determinism, and introduce a new partial order relation, called always-happens-before relation, between events of such applications. Leveraging these two concepts, we design a protocol that combines an unprecedented set of features. Our protocol called SPBC combines in a hierarchical way coordinated checkpointing and message logging. It is the first protocol that provides failure containment without logging any information reliably apart from process checkpoints, and this, without penalizing recovery performance. Experiments run with a representative set of HPC workloads demonstrate a good performance of our protocol during both, failure-free execution and recovery.

The paper proposes a new state machine replication protocol for the partially synchronous system model with Byzantine faults. The algorithm, called BFT-Mencius, guarantees that the latency of updates initiated by correct processes is eventually upper-bounded, even in the presence of Byzantine processes. BFTMencius is based on a new communication primitive, Abortable Timely Announced Broadcast (ATAB), and does not use signatures. We evaluate the performance of BFT-Mencius in cluster settings, and show that it provides bounded latency and good throughput, being comparable to the state-of-the-art algorithms such as PBFT and Spinning in fault-free configurations and outperforming them under performance attacks by Byzantine processes.

Virtual machine (VM) replication has been recognized as an inexpensive way of providing high availability on commodity hardware. Unfortunately, its impact on system performance is far from negligible and strategies have been proposed to mitigate this problem. In this paper we take a look at VM replication from a different perspective: the choice of a hyper visor. Namely, the differences between hyper visors in terms of architecture and performance are well known and studied in the literature, but no analysis has been performed so far in the context of replication. Taking open-source hyper visors Xen and KVM as examples, we show what hyper visor services are necessary to implement a primary-backup replication scheme and how hyper visor design affects the development steps and the performance. Interestingly, our user space implementation on top of KVM achieves roughly the same performance as an already existing, more mature Xen implementation, which leads us to the conclusion that the inherent cost of the replication scheme dominates the differences between the chosen hyper visors.

Transmission faults allow us to reason about permanent and transient value faults in a uniform way. However, all existing solutions to consensus in this model are either in the synchronous system, or require strong conditions for termination, that exclude the case where all messages of a process can be corrupted. We introduce eventual consistency in order to overcome this limitation. Eventual consistency denotes the existence of rounds in which processes receive the same set of messages. Eventually consistent rounds can be simulated from eventually synchronous rounds, and eventual consistent rounds can be used to solve consensus.

Many-core chips with more than 1000 cores are expected by the end of the decade. To overcome scalability issues related to cache coherence at such a scale, one of the main research directions is to leverage the message-passing programming model. The Intel Single-Chip Cloud Computer (SCC) is a prototype of a message-passing many-core chip. It offers the ability to move data between on-chip Message Passing Buffers (MPB) using Remote Memory Access (RMA). Performance of message-passing applications is directly affected by efficiency of collective operations, such as broadcast. In this paper, we study how to make use of the MPBs to implement an efficient broadcast algorithm for the SCC. We propose OC-Bcast (On-Chip Broadcast), a pipelined k-ary tree algorithm tailored to exploit the parallelism provided by on-chip RMA. Using a LogP-based model, we present an analytical evaluation that compares our algorithm to the state-of-the-art broadcast algorithms implemented for the SCC. As predicted by the model, experimental results show that OC-Bcast attains almost three times better throughput, and improves latency by at least 27\%. Furthermore, the analytical evaluation highlights the benefits of our approach: OC-Bcast takes direct advantage of RMA, unlike the other considered broadcast algorithms, which are based on a higher-level send/receive interface. This leads us to the conclusion that RMA-based collective operations are needed to take full advantage of hardware features of future message-passing many-core architectures.

Implementations of state machine replication are prevalently using variants of Paxos or other leader-based protocols. Typically these protocols are also leader-centric, in the sense that the leader performs more work than the non-leader replicas. Such protocols scale poorly, because as the number of replicas or the load on the system increases, the leader replica quickly reaches the limits of one of its resources. In this paper we show that much of the work performed by the leader in a leader-centric protocol can in fact be evenly distributed among all the replicas, thereby leaving the leader only with minimal additional workload. This is done (i) by distributing the work of handling client communication among all replicas, (ii) by disseminating client requests among replicas in a distributed fashion, and (iii) by executing the ordering protocol on ids. We derive a variant of Paxos incorporating these ideas. Compared to leader-centric protocols, our protocol not only achieves significantly higher throughput for any given number of replicas, but also increases its throughput with the number of replicas.

Consensus is one of the key problems in fault-tolerant distributed computing. Although the solvability of consensus is now a well-understood problem, comparing different algorithms in terms of efficiency is still an open problem. In this paper, we address this question for round-based consensus algorithms using communication predicates, on top of a partial synchronous system that alternates between good and bad periods (synchronous and nonsynchronous periods). Communication predicates together with the detailed timing information of the underlying partially synchronous system provide a convenient and powerful framework for comparing different consensus algorithms and their implementations. This approach allows us to quantify the required length of a good period to solve a given number of consensus instances. With our results, we can observe several interesting issues, such as the number of rounds of an algorithm is not necessarily a good metric for its performance.

We investigate the reduction of atomic broadcast to consensus in systems with Byzantine faults. Among the several definitions of Byzantine consensus that differ only by their validity property, we identify those equivalent to atomic broadcast. Finally, we give the first deterministic atomic broadcast reduction with a constant time complexity with respect to consensus.

Many atomic broadcast algorithms have been published in the last 20 years. Token-based algorithms represent a large class of these algorithms. Interestingly, all the token-based atomic broadcast algorithms rely on a group membership service and none of them uses unreliable failure detectors directly. This paper presents the first token-based atomic broadcast algorithm that uses an unreliable failure detector instead of a group membership service. It requires a system size that is quadratic in the number of supported failures. The special case of a single supported failure (f=1) requires n=3 processes. We experimentally evaluate the performance of this algorithm in local and wide area networks, in order to emphasize that atomic broadcast is efficiently implemented by combining a failure detector and a token-based mechanism. The evaluation shows that the new token-based algorithm surpasses the performance of the other algorithms in most small-system settings.

The paper proposes a generic consensus algorithm that highlights the basic and common features of known consensus algorithms. The parameters of the generic algorithm encapsulate the core differences between various consensus algorithms, including leader-based and leader-free algorithms, addressing benign faults, authenticated Byzantine faults and Byzantine faults. This leads to the identification of three classes of consensus algorithms. With the proposed classification, Paxos and PBFT indeed belong to the same class, while FaB Paxos belongs to a different class. Interestingly, the classification allowed us to identify a new Byzantine consensus algorithm that requires n > 4b, where b is the maximum number of Byzantine processes.

We introduce the notion of a swift algorithm. Informally, an algorithm that solves the repeated consensus is swift if, in a partial synchronous run of this algorithm, eventually no timeout expires, i.e., the algorithm execution proceeds with the actual speed of the system. This definition differs from other efficiency criteria for partial synchronous systems. Furthermore, we show that the notion of swiftness explains why failure detector based algorithms are typically more efficient than round-based algorithms, since the former are naturally swift while the latter are naturally non-swift. We show that this is not an inherent difference between the models, and provide a round implementation that is swift, therefore performing similarly to failure detector algorithms while maintaining the advantages of the round model.

Atomic broadcast is a useful abstraction for implementing fault-tolerant distributed applications such as state-machine replication. Although a number of algorithms solving atomic broadcast have been published, the problem of bounding the memory used by these algorithms has not been given the attention it deserves. It is indeed impossible to solve repeated atomic broadcast with bounded memory in a system (non-synchronous or not equipped with a perfect failure detector) in which consensus is solvable with bounded memory. The intuition behind this impossibility is the inability to safely garbage-collect unacknowledged messages, since a sender process cannot tell whether the destination process has crashed or is just slow.The usual technique to cope with this problem is to introduce a membership service, allowing the exclusion of a slow or silent process from the group and safely discarding unacknowledged messages sent to this process. In this paper,we present a novel solution that does not rely on a membership service. We relax the specification of atomic broadcast so that it can be implemented with bounded memory, while being strong enough to still be useful for applications that use atomic broadcast, e.g., state-machine replication.

In this paper we study dynamic protocol updates (DPU), which consist in replacing, without interruption, a given protocol during execution. We focus especially on group communication protocols. The paper proposes a methodology to conveniently describe which protocols are correctly replaced by a given DPU algorithm. More precisely, our methodology characterizes DPU algorithms by a set of inference rules. To validate our approach, we illustrate our methodology with a new DPU algorithm.

Most papers addressing consensus in wireless ad hoc networks adopt system models similar to those developed for wired networks. These models are focused towards node failures while ignoring link failures, and thus are poorly suited for wireless ad hoc networks. The recently proposed HO model does not have this drawback. The paper shows that an existing algorithm and the HO model can be used for multi-hop wireless ad hoc networks, if extended with an adequate communication layer. The description of the communication layer is augmented with simulation results that validate the feasibility of our approach and provide better understanding of the behavior of wireless environments.

Consensus is one of the key problems in fault tolerant distributed computing. A very popular model for solving consensus is the failure detector model defined by Chandra and Toueg. However, the failure detector model has limitations. The paper points out these limitations, and suggests instead a model based on communication predicates, called HO model. The advantage of the HO model over failure detectors is shown, and the implementation of the HO model is discussed in the context of a system that alternates between good periods and bad periods. Two definitions of a good period are considered. For both definitions, the HO model allows us to compute the duration of a good period for solving consensus. Specifically, the model allows us to quantify the difference between the required length of an initial good period and the length of a non initial good period.

Modularity is a desirable property of complex software systems, since it simplifies code reuse, verification, maintenance, etc. However, the use of loosely coupled modules introduces a performance overhead. This overhead is often considered negligible, but this is not always the case. This paper aims at casting some light on the cost, in terms of performance, that is incurred when designing a relevant group communication protocol with modularity in mind: atomic broadcast. We conduct our experiments using two versions of atomic broadcast: a modular version and a monolithic one. We then measure the performance of both implementations under different system loads. Our results show that the overhead introduced by modularity is strongly related to the level of stress to which the system is subjected, and in the worst cases, reaches approximately 50%.

Consensus encalpsulates the inherent problems of building fault tolerant distributed systems. In this context, the classic model of Byzantine faulty processes can be restated such that messages from a subset of processes can be arbitrarily corrupted (including addition and omission of messages).

Consensus is one of the most fundamental problems in fault-tolerant distributed computing. This paper proposes a mechanical method for analyzing the condition that allows one to solve consensus. Specifically, we model check a distributed algorithm that implements a communication predicate, which is an alternative system abstraction to failure detectors. This model checking problem is challenging because it involves both continuous time and unbounded integers. We solve the problem by reducing it to the satisfiability problem of linear arithmetic constraints over real and integer variables. The proposed method can be used to determine the length of a synchronous period required for implementing a communication predicate for solving consensus.

We show for the first time that standard model checking allows one to completely verify asynchronous algorithms for solving consensus, a fundamental problem in fault-tolerant distributed computing. Model checking is a powerful verification methodology based on state exploration. However it has rarely been applied to consensus algorithms, because these algorithms induce huge, often infinite state spaces. Here we focus on consensus algorithms based on the Heard-Of model, a new computation model for distributed computing. By making use of the high abstraction level provided by this computation model and by devising a finite representation of unbounded timestamps, we develop a methodology for verifying consensus algorithms in every possible state by model checking.

In previous work, it has been shown how to solve atomic broadcast by reduction to consensus on messages. While this solution is theoretically correct, it has its limitations in practice, since executing consensus on large messages can quickly saturate the system. The problem can be addressed by executing consensus on message identifiers instead of the full messages, in order to decouple the size of the messages from the size of the data sent by the consensus algorithm. In this paper, we study the impact of executing consensus on message identifiers instead of on the full messages, in the context of solving atomic broadcast. We also discuss the implications of executing consensus on message identifiers on the consensus and atomic broadcast algorithms

In this paper, we study dynamic protocol update (DPU). Contrary to local code updates on-the-fly, DPU requires global coordination of local code replacements. We propose a novel solution to DPU. The key idea is to add a level of indirection between the service callers and the service provider. This indirection level facilitates an implementation of simple and efficient algorithms for DPU. For example, we describe an experimental implementation of adaptive group communication middleware. It can switch between different atomic broadcast protocols on-the-fly. All middleware protocols, including those that depend on the updated protocols, provide service correctly and with negligible delay while the global update takes places. The switching algorithm introduces very low overhead that we illustrate by showing example measurement results.

The paper addresses the cost of consensus algorithms. It has been shown that in the best case, consensus can be solved in two communication steps with f<n/2, and in one communication step with f

We present DRIFT - a total order multicast algorithm for ad hoc networks with mobile or static nodes. Due to the ad hoc nature of the network, DRIFT uses flooding for message propagation. The key idea of DRIFT is virtual flooding - a way of using unrelated message streams to propagate message causality information in order to accelerate message delivery. We describe DRIFT in detail. We evaluate its performance in a simulator and in a wireless sensor network. In both cases our results demonstrate that the performance of DRIFT exceeds that of the simple total order multicast algorithm designed for wired networks, on which it is based. In simulation at scale, for certain experiment settings, DRIFT achieved speedup of several orders of magnitude

We revisit the well-known group membership problem and show how it can be considered a special case of a simple problem, the set membership problem. In the set membership problem, processes maintain a set whose elements are drawn from an arbitrary universe: They can request the addition or removal of elements to/from that set, and they agree on the current value of the set. Group membership corresponds to the special case where the elements of the set happen to be processes. We exploit this new way of looking at group membership to give a simple and succinct specification of this problem and to outline a simple implementation approach based on the state machine paradigm. This treatment of group membership separates several issues that are often mixed in existing specifications and/or implementations of group membership. We believe that this separation of concerns greatly simplifies the understanding of this problem.

Designing and correctly implementing group communication systems (GCSs) is notoriously difficult. Assuming that processes fail only by crashing provides a powerful means to simplify the theoretical development of these systems. When making this assumption, however, one should not forget that clean crash failures provide only a coarse approximation of the effects that errors can have in distributed systems. Ignoring such a discrepancy can lead to complex GCS-based applications that pay a large price in terms of performance overhead yet fail to deliver the promised level of dependability. This paper provides a thorough study of error effects in real systems by demonstrating an error-injection-driven design methodology, where error injection is integrated in the core steps of the design process of a robust fault-tolerant system. The methodology is demonstrated for the Fortika toolkit, a Java-based GCS. Error injection enables us to uncover subtle reliability bottlenecks both in the design of Fortika and in the implementation of Java. Based on the obtained insights, we enhance Fortika's design to reduce the identified bottlenecks. Finally, a comparison of the results obtained for Fortika with the results obtained for the OCAML-based Ensemble system in a previous work, allows us to investigate the reliability implications that the choice of the development platform (Java versus OCAML) can have

Atomic broadcast in particular, and group communication in general, have mainly been specified and implemented in a system model where processes do not recover after a crash. The model is called crash-stop. The drawback of this model is its inability to express algorithms that tolerate the crash of a majority of processes. This has led to extend the crash-stop model to the so-called crash-recovery model, in which processes have access to stable storage, to log their state periodically. This allows them to recover a previous state after a crash. However, the existing specifications of atomic broadcast in the crash-recovery model are not satisfactory, and the paper explains why. The paper also proposes a new specification of atomic broadcast in the crash-recovery model that addresses these issues. Specifically, our new specification allows to distinguish between a uniform and a non-uniform version of atomic broadcast. The non-uniform version logs less information, and is thus more efficient. The uniform and non-uniform atomic broadcast have been implemented and compared with a published atomic broadcast algorithm. Performance results are presented.

In this paper, we present a performance comparison of database replication techniques based on total order broadcast. While the performance of total order broadcast-based replication techniques has been studied in previous papers, this paper presents many new contributions. First, it compares with each other techniques that were presented and evaluated separately, usually by comparing them to a classical replication scheme like distributed locking. Second, the evaluation is done using a finer network model than previous studies. Third, the paper compares techniques that offer the same consistency criterion (one-copy serializability) in the same environment using the same settings. The paper shows that, while networking performance has little influence in a LAN setting, the cost of synchronizing replicas is quite high. Because of this, total order broadcast-based techniques are very promising as they minimize synchronization between replicas.

Summary form only given. We address programming abstractions for building protocols from smaller, reusable microprotocols. The existing protocol frameworks, such as Appia and Cactus, either restrict the amount of concurrency between microprotocols, or depend on the programmer, who should implement all the necessary synchronisation using standard language facilities. We develop J-SAMOA: a framework for a synchronisation augmented microprotocol approach in Java. It has been designed to allow concurrent protocols to be expressed without explicit low-level synchronisation, thus making programming easier and less error-prone. We describe versioning concurrency control algorithms. They are used by the runtime system of our framework to guarantee that the concurrent execution of a protocol is equivalent to a serial execution of its microprotocols. This guarantee, called the isolation property, ensures consistency of session or message-specific data maintained by microprotocols.

We propose a novel approach to the composition of group communication protocols. In this approach, components are modelled as finite state machines communicating via signals. We introduce two building blocks, called adaptor and adaplexor, that ease the development and the composition of group communication protocol stacks, and we discuss how isolation can be achieved in this setting. To validate our architectural concepts, we have implemented the proposed group communication architecture in SDL.

Group communication provides communication primitives with various semantics and their use greatly simplifies the development of highly available services. However, despite tremendous advances in research and numerous prototypes, group communication stays confined to small niches and academic prototypes. In contrast, message-oriented middleware such as the Java message service (JMS) is widely used, and has become a de-facto standard. We believe that the lack of a well-defined and easily understandable standard is the reason that hinders the deployment of group communication systems. Since JMS is a well-established technology, an interesting solution is to extend JMS adding group communication primitives to it. Foremost, this requires extending the traditional semantics of group communication in order to take into account various features of JMS, e.g., durable/nondurable subscriptions and persistent/non-persistent messages. The resulting new group communication specification, together with the corresponding API, defines group communication primitives compatible with JMS.

Group communication is a topic studied since more than twenty years. During this period significant results have been obtained. Nevertheless there are issues that have not been addressed adequately. The paper presents both the important results related to group communication that have been obtained, but also points out what remains to be done to make group communication widely used, and as successful as some of the existing middleware technologies.

No abstract available.

Many atomic broadcast algorithms have been published in the last twenty years. Token-based algorithms represent a large class of these algorithms. Interestingly, all the token-based atomic broadcast algorithms rely on a group membership service, i.e., none of them uses unreliable failure detectors directly. The paper presents the first token-based atomic broadcast algorithm that uses an unreliable failure detector - the new failure detector denoted by /spl Rscr/ - instead of a group membership service. The failure detector /spl Rscr/ is compared with <>V and <>S. In order to make it easier to understand the atomic broadcast algorithm, the paper derives the atomic broadcast algorithm from a token-based consensus algorithm that also uses the failure detector /spl Rscr/.

Protocols that solve agreement problems are essential building blocks for fault tolerant distributed systems. While many protocols have been published, little has been done to analyze their performance, especially the performance of their fault tolerance mechanisms. In this paper, we compare two well-known asynchronous consensus algorithms. In both algorithms, a leader process tries to impose a decision, and another leader retries if the leader fails doing so. The algorithms elect leaders differently: the Chandra-Toueg algorithm has a rotating leader, whereas processes in the Paxos algorithm elect leaders directly. We investigate the performance implications of this difference. In the system under study, processes send atomic broadcasts to each other. Consensus is used to decide the delivery order of messages. We evaluate the steady state latency in (1) runs with neither crashes nor suspicions, (2) runs with crashes and (3) runs with no crashes in which correct processes are wrongly suspected to have crashed, as well as the transient latency after (4) one crash and (5) multiple correlated crashes. The results show that the Paxos algorithm tolerates frequent wrong suspicions (3) and correlated crashes (5) better, while the performance is comparable in all other scenarios.

Peter Urban, Ilya Shnayderman and Andre Schiper Comparison of Failure Detectors and Group Membership: Performance Study of Two Atomic Broadcast Algorithms In Proc. of the 2003 International Conference on Dependable Systems and Networks (DSN), pages 645-654 Protocols that solve agreement problems are essential building blocks for fault tolerant distributed systems. While many protocols have been published, little has been done to analyze their performance, especially the performance of their fault tolerance mechanisms. In this paper, we present a performance evaluation methodology that can be generalized to analyze many kinds of fault-tolerant algorithms. We use the methodology to compare two atomic broadcast algorithms with different fault tolerance mechanisms: unreliable failure detectors and group membership. We evaluated the steady state latency in (1) runs with neither crashes nor suspicions, (2) runs with crashes and (3) runs with no crashes in which correct processes are wrongly suspected to have crashed, as well as (4) the transient latency after a crash. We found that the two algorithms have the same performance in Scenario 1, and that the group membership based algorithm has an advantage in terms of performance and resiliency in Scenario 2, whereas the failure detector based algorithm offers better performance in the other scenarios. We discuss the implications of our results to the design of fault tolerant distributed systems.

While group communication systems have been proposed for some time, they are still not used much in actual systems. We believe that one reason for this is the lack of standardisation of group communication system interfaces. The paper proposes an architecture, using the standard decomposition into services, where services are based on standard interfaces: both interactions between services and interactions with the application use existing, open standards. A decomposition of the group communication into services is presented, along with a description of applicable standards. As an example, a group membership service based on the LDAP standard is discussed.

No abstract available.

The paper presents and compares Appia and Cactus, two frameworks for protocol composition. The comparison is based on the experience gained in implementing a fault-tolerant atomic broadcast service. The paper also gives preliminary performance results, and concludes with a discussion of the most interesting features of the two frameworks, and suggestions for an improved framework.

In today's systems, applications are composed from various components that may be located on different machines. The components (acting as servers) may have to collaborate in order to service a client request. More specifically, a client request to one component may trigger a request to another component. To ensure fault-tolerance, components are generally replicated. Replicated components lead to the problem of a replicated server invoking another replicated server. We call this the problem of replicated invocation. Replicated invocation has been considered in the context of deterministic servers. However, the problem is more difficult to address when servers are non-deterministic. In this context, work has been done to enforce deterministic execution. In this paper, we consider a different approach: instead of preventing non-deterministic execution of servers we discuss how to handle it. We present the problem of non-deterministic replicated invocation. Our solution then consists of sharing sufficient undo information among the replicas of the server invoking another server.

This paper describes a distributed algorithm for reliable multicast in mobile cellular networks. In the proposed solution the multicast message is flooded to all the base stations over reliable channels. The base stations then collectively ensure that all mobile nodes belonging to the multicast group get the message. The originality of our solution is that it is fully decentralized. Each base station can independently decide when to flush a message from its buffer. Even if a node moves from one cell to another while a multicast is in progress, delivery of the message to the node is guaranteed. Simulation experiments show that using the proposed solution, memory requirements at the base stations are significantly smaller than by using centralized solutions.

Although far from the optimal, flooding is an indispensable message dissemination technique for network-wide broadcast within mobile ad hoc networks (MANETs). As such, the plain flooding algorithm provokes a high number of unnecessary packet rebroadcasts, causing contention, packet collisions and ultimately wasting precious limited bandwidth. We explore the phase transition phenomenon observed in percolation theory and random graphs as a basis for defining probabilistic flooding algorithm. By considering ideal and realistic models, we acquire a better understanding of the factors that determine phase transition, the consequences of the passage to realistic MANET conditions and to what extent we may benefit from probabilistic flooding in real MANET networks.

Mobile agents have attracted considerable interest in recent years. In the context of mobile agents, fault tolerance is crucial to enable the integration of mobile agent technology into today's business applications. This article identifies two important properties for fault-tolerant mobile agent execution: nonblocking and exactly-once. Nonblocking ensures that the agent execution can proceed despite a single failure of the agent or the machine, for instance. Replication is the generally adopted mechanism to prevent blocking, but may lead to multiple executions of the agent (i.e., a violation of the exactly-once property), which is undesirable with operations that have side effects. Hence, we propose that fault-tolerant mobile agent execution be modeled as a sequence of agreement problems. Our approach is nonblocking and ensures exactly-once execution. FATOMAS, our prototype fault-tolerant mobile agent system, implements our approach. Its performance evaluation illustrates the overhead of the replication mechanisms.

Atomic broadcast primitives are often proposed as a mechanism to allow fault-tolerant cooperation between sites in a distributed system. Unfortunately, the delay incurred before a message can be delivered makes it difficult to implement high performance, scalable applications on top of atomic broadcast primitives. Recently, a new approach has been proposed for atomic broadcast which, based on optimistic assumptions about the communication system, reduces the average delay for message delivery to the application. We develop this idea further and show how applications can take even more advantage of the optimistic assumption by overlapping the coordination phase of the atomic broadcast algorithm with the processing of delivered messages. In particular, we present a replicated database architecture that employs the new atomic broadcast primitive in such a way that communication and transaction processing are fully overlapped, providing high performance without relaxing transaction correctness.

Mobile agents are computer programs that act autonomously on behalf of a user and travel through a network of heterogeneous machines. To enable mobile agent technology for e-business, transaction support needs to be provided, in particular execution atomicity. Execution atomicity ensures that either all operations of the agent succeed, or none at all, and needs to be ensured also in the face of infrastructure failures. We distinguish between blocking and non-blocking solutions for transactional mobile agents, i.e., mobile agents, that execute as a transaction. The approach presented in the paper is non-blocking. A non-blocking transactional mobile agent execution has the important advantage, that it can make progress despite failures.

When processes on two different machines communicate, they most often do so using the TCP protocol. While TCP is appropriate for a wide range of applications, it has shortcomings in other application areas. One of these areas is fault tolerant distributed computing. For some of those applications, TCP does not address link failures adequately: TCP breaks the connection if connectivity is lost for some duration (typically minutes). This is sometimes undesirable. The paper proposes robust TCP connections, a solution to the problem of broken TCP connections. The paper presents a session layer protocol on top of TCP that ensures reconnection, and provides exactly-once delivery for all transmitted data. A prototype has been implemented as a Java library. The prototype has less than 10% overhead on TCP sockets with respect to the most important performance figures.

This paper investigates the two main and seemingly antagonistic approaches to broadcasting messages reliably in fault-tolerant distributed systems: the approach based on reliable broadcast, and that based on view synchronous communication (or VSC for short). While VSC does more than reliable broadcast, this has a cost. We show that this cost can be reduced by exploiting the difference between input-triggered and output-triggered suspicions, and by replacing the standard VSC broadcast primitive by two broadcast primitives, one sensitive to input-triggered suspicions, and the other sensitive to output-triggered suspicions.

Fault tolerance is fundamental to the further development of mobile agent applications. In the context of mobile agents, fault-tolerance prevents a partial or complete loss of the agent, i.e., it ensures that the agent arrives at its destination. We present FATOMAS, a Java-based fault-tolerant mobile agent system based on an algorithm presented in an earlier paper (2000). Contrary to the standard "place-dependent" architectural approach, FATOMAS uses the novel "agent-dependent" approach. In this approach, the protocol that provides fault tolerance travels with the agent. This has the important advantage to allow fault-tolerant mobile agent execution without the need to modify the underlying mobile agent platform (in our case ObjectSpace's Voyager). In our performance evaluation, we show the costs of our approach relative to the single, non-replicated agent execution. Pipelined mode and optimized agent forwarding are two optimizations that reduce the overhead of a fault-tolerant mobile agent execution.

Replication is a powerful technique for increasing availability of a distributed service. Algorithms for replicating distributed services do however face a dilemma: they should be: efficient (low latency); while ensuring consistency of the replicas, which are two contradictory goals. The paper concentrates on active replication, where all the replicas handle the clients' requests. Active replication is usually implemented using the atomic broadcast primitive. To be efficient, some atomic broadcast algorithms deliberately sacrifice consistency, if inconsistency is likely to occur with a low probability. We present an algorithm that handles replication efficiently in most scenarios, while preventing inconsistencies. The originality of the algorithm is to take the client-server interaction into account, while traditional solutions consider atomic broadcast as a black box.

The paper considers a consensus algorithm for an asynchronous system augmented with failure detectors, and analyzes the impact on its termination time of various implementations of failure detectors. The study shows that the design of fault-tolerant distributed algorithms in the asynchronous system model augmented with failure detectors is orthogonal to implementing the actual failure detectors. This nicely decouples logical issues (proof of correctness) from engineering issues (e.g., performance and timing constraints).

Fault-tolerant control systems can be built by replicating critical components. However replication raises the issue of inconsistency. Multiple protocols for ensuring consistency have been described in the literature. PADRE (Protocol for Asymmetric Duplex REdundancy) is such a protocol, and an interesting case study of a complex and sensitive problem: the management of replicated traffic controllers in a railway system. However, the low level at which the protocol has been developed embodies system details, namely timeliness assumptions, that make it difficult to understand and may narrow its applicability. We argue that, when designing a protocol, it is preferable to consider first a general solution that does not include any timeliness assumptions; then, by taking into account an additional hypothesis, one can easily design a time-based solution tailored to a specific environment. This paper illustrates the benefit of a top-down protocol design approach and shows that PADRE can be seen as an instance of a standard primary-backup replication protocol based on view-synchronous communication (VSC).

Fault tolerance can be achieved in distributed systems by replication. However Fischer, Lynch and Paterson (1985) have proven an impossibility result about consensus in the asynchronous system model, and similar impossibility results exist for atomic broadcast and group membership. We investigate, with the aid of an experiment conducted in a LAN, whether these impossibility results set limits to the robustness of a replicated server exposed to extremely high loads. The experiment consists of client processes that send requests to a replicated server (three replicas) using an atomic broadcast primitive. It has parameters that allow us to control the load on the hosts and the network, as well as the timeout value used by our heartbeat failure detection mechanism. Our main observation is that the atomic broadcast algorithm never stops delivering messages, not even under arbitrarily high load and very small timeout values (1 ms). So, by trying to illustrate the practical impact of impossibility results, we discovered that we had implemented a very robust replicated service.

This paper describes a modular approach for the construction of fault-tolerant agreement protocols. The approach is based on a generic consensus service. Fault-tolerant agreement protocols are built using a client-server interaction, where the clients are the processes that must solve the agreement problem and the servers implement the consensus service. This service is accessed through a generic consensus filter, customized for each specific agreement problem. We illustrate our approach on the construction of various fault-tolerant agreement protocols, such as nonblocking atomic commitment, group membership, view synchronous communication, and total order multicast. Through a systematic reduction to consensus, we provide a simple way to solve agreement problems. In addition to its modularity, our approach enables efficient implementations of agreement protocols and precise characterization of the assumptions underlying their liveness and safety properties.

We compare, in terms of solvability and efficiency, the synchronous model, noted Ss, with the asynchronous model augmented with a perfect failure detector, noted S/sub P/. We first exhibit a problem that, although time-free, is solvable in S/sub S/ but not in S/sub P/. We then examine whether one of these two models allows more efficient solutions for designing fault-tolerant applications. In particular, we concentrate on the uniform consensus problem which is solvable in both models, and we design a uniform consensus algorithm for the S/sub S/ model that is more efficient than any algorithm solving uniform consensus in S/sub P/ with respect to some significant time complexity measure. From a practical viewpoint, the synchronous model thus seems better than the asynchronous model augmented with a perfect failure detector.

Resource contention is widely recognized as having a major impact on the performance of distributed algorithms. Nevertheless, the metrics that are commonly used to predict their performance take little or no account of contention. We define two performance metrics for distributed algorithms that account for network contention as well as CPU contention. We then illustrate the use of these metrics by comparing four atomic broadcast algorithms, and show that our metrics allow for a deeper understanding of performance issues than conventional metrics.

Replication is an area of interest to both distributed systems and databases. The solutions developed from these two perspectives are conceptually similar but differ in many aspects: model, assumptions, mechanisms, guarantees provided, and implementation. In this paper, we provide an abstract and "neutral" framework to compare replication techniques from both communities. The framework has been designed to emphasize the role played by different mechanisms and to facilitate comparisons. The paper describes the replication techniques used in both communities, compares them, and points out ways in which they can be integrated to arrive to better, more robust replication protocols.

Fault tolerance is fundamental to the further development of mobile agent applications. In the context of mobile agents, fault tolerance prevents a partial or complete loss of the agent, i.e. ensures that the agent arrives at its destination. Simple approaches such as checkpointing are prone to blocking. Replication can in principle improve solutions based on checkpointing. However existing solutions in this context either assume a perfect failure detection mechanism (which is not realistic in an environment such as the Internet), or rely on complex solutions based on leader election and distributed transactions, where only a subset of solutions prevents blocking. The paper proposes a novel approach to fault tolerant mobile agent execution, which is based on modeling agent execution as a sequence of agreement problems. Each agreement problem is one instance of the well understood consensus problem. Our solution does not require a perfect failure detection mechanism, while preventing blocking and ensuring that the agent is executed exactly once.

Data replication is an increasingly important topic as databases are more and more deployed over clusters of workstations. One of the challenges in database replication is to introduce replication without severely affecting performance. Because of this difficulty, current database products use lazy replication, which is very efficient but can compromise consistency. As an alternative, eager replication guarantees consistency but most existing protocols have a prohibitive cost. In order to clarify the current state of the art and open up new avenues for research, this paper analyses existing eager techniques using three key parameters (server architecture, server interaction and transaction termination). In our analysis, we distinguish eight classes of eager replication protocols and, for each category, discuss its requirements, capabilities and cost. The contribution lies in showing when eager replication is feasible and in spelling out the different aspects a database replication protocol must account for.

Atomic broadcast primitives allow fault-tolerant cooperation between sites in a distributed system. Unfortunately, the delay incurred before a message can be delivered makes it difficult to implement high performance, scalable applications on top of atomic broadcast primitives. A new approach has been proposed which, based on optimistic assumptions about the communication system, reduces the average delay for message delivery. We develop this idea further and present a replicated database architecture that employs the new atomic broadcast primitive in such a way that the coordination phase of the atomic broadcast is fully overlapped with the execution of transactions, providing high performance without relaxing transaction correctness.

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.

No abstract available.

This paper presents the semi-passive replication technique, a variant of passive replication, that can be implemented in the asynchronous system model without requiring a membership service to agree on a primary. Passive replication is a popular replication technique since it can tolerate non-deterministic servers (e.g., multi-threaded servers) and uses little processing power when compared to other replication techniques. However, passive replication suffers from a high reconfiguration cost in case of the failure of the primary. The semi-passive replication technique presented in the paper benefits from the same advantages as passive replication. However, since it does not require a group membership service, semi-passive replication has a considerably lower cost in case of failure. As explained in the paper, this technique can benefit from an aggressive time-out value significantly lower than what a group membership allows. As a result, the reaction to crashes is greatly improved. The semi-passive replication algorithm uses failure detectors. The algorithm given in the paper is analysed in the failure free case and in the case of one server crash. The response time (for the client) of these two scenarios is analysed through simulation.

We present a fault tolerant algorithm that ensures total order delivery of messages sent to multiple groups of processes. Our algorithm is a multiple group "genuine" multicast algorithm in the sense that: (1) any process can send a message to any set of process groups; and (2) only the sender and the receivers of a message take part in the algorithm needed to deliver the message. The correctness of our algorithm does not require reliable failure detectors, but requires causal order delivery of messages. This establishes a new and interesting link between causal order delivery and fault tolerance with unreliable failure detectors.

The paper presents a fault tolerant lazy replication protocol that ensures 1-copy serializability at a relatively low cost. Unlike eager replication approaches, our protocol enables local transaction execution and does not lead to any deadlock situation. Compared to previous lazy replication approaches, we significantly reduce the abort rate of transactions and we do not require any reconciliation procedure. Our protocol first executes transactions locally, then broadcasts a transaction certification message to all replica managers, and finally employs a certification procedure to ensure 1-copy serializability. Certification messages are broadcast using a non blocking atomic broadcast primitive, which alleviates the need for a more expensive non blocking atomic commitment algorithm. The certification procedure uses a reordering technique to reduce the probability of transaction aborts.

Non-blocking atomic commitment protocols enable a decision (commit or abort) to be reached at every correct participant, despite the failure of others. The cost for non-blocking implies however (1) a high number of messages and communication steps required to reach commit, and (2) a complicated termination protocol needed in the case of failure suspicions. In this paper, we present a non-blocking protocol, called MDSPC (Modular and Decentralized Three Phase Commit), which enables to trade resiliency against efficiency. As conveyed by our performance measures, MDSPC is faster than existing non-blocking protocols, and in the case of a broadcast network and a reasonable resiliency rate (e.g. 2 or 3) is almost as efficient as the classical (blocking) 2PC. The termination protocol of MDSPC is encapsulated inside a majority consensus protocol. This modularity leads to a simple structure of MDSPC and enables a precise characterization of its liveness in an asynchronous system with an unreliable failure detector.

In a transactional system, an atomic commitment protocol ensures that for any transaction, all data manager processes agree on the same outcome (commit or abort). A non-blocking atomic commitment protocol enables an outcome to be decided at every correct process despite the failure of others. In this paper we apply, for the first time, the fundamental result of T. Chandra and S. Toueg (1991) on solving the abstract consensus problem, to non-blocking atomic commitment. More precisely, we present a non-blocking atomic commitment protocol in an asynchronous system augmented with an unreliable failure detector that can make an infinity of false failure suspicions. If no process is suspected to have failed, then our protocol is similar to a three phase commit protocol. In the case where processes are suspected, our protocol does not require any additional termination protocol: failure scenarios are handled within our regular protocol and are thus much simpler to manage.

The increased interest in protocols that provide a total order on message delivery has led to several different definitions of total order. In this paper we investigate these different definitions and propose a hierarchy that helps to better understand the implications of the different possibilities in terms of guarantees and communication cost. We identify two definitions: weak total order and strong total order, which are at the extremes of the proposed hierarchy, and incorporate them into a consistent design. Finally, we propose high-level algorithms based on a virtually synchronous communication environment that implement the given definitions.

DUPLEX is a distributed collaborative editor for users connected through a large-scale environment such as the Internet. Large-scale implies heterogeneity, unpredictable communication delays and failures, and inefficient implementations of techniques traditionally used for collaborative editing in local area networks. To cope with these unfavorable conditions, DUPLEX proposes a model based on splitting the document into independent parts, maintained individually and replicated by a kernel. Users act on document parts and interact with co-authors using a local environment providing a safe store and recovery mechanisms against failures or divergence with co-authors. Communication is reduced to a minimum, allowing disconnected operation. Atomicity, concurrency, and replica control are confined to a manageable small context.

We devetop necessary conditions for the development of asynchronous distributed sofiware that will perform uniform actions (’evenis that if performed by any pro-cess, must be performed at all processes). The pa-per focuses on dynamic uniformity, which differs from ihe classical problems in that processes continually leave and join the ongoing computation. It relates the problem to asynchronous Consensus, and shows that Consensus is a harder problem. We provide a rigorous characterization of the framework upon which several existing distributed programming environments are based. And, our work shows that progress is some-times possible in a primary-partition model even when consensus is not. 1

The authors present the definition of and solution to the uniform reliable multicast problem in the virtually synchronous environment defined by the Isis system. A uniform reliable multicast of a message m has the property that if m has been received by any destination process (faulty or not), then m is received by all processes that reach a decision. Uniform reliable multicast provides a solution to the distributed commit problem. Two multicast primitives are defined in the virtually synchronous model: reliable multicast (called view-atomic) and uniform reliable multicast (called uniform view-atomic). The view-atomic multicast is used to implement the uniform view-atomic primitive. As view-atomicity is based on the concept of process group membership, a connection is established between the process group membership and the distributed commit problems.>

The ISIS toolkit is a distributed programming environment based on support for virtually synchronous process groups and group communication. A suite of protocols is presented to support this model. The approach revolves around a multicast primitive, called CBCAST, which implements a fault-tolerant, causally ordered message delivery. This primitive can be used directly or extended into a totally ordered multicast primitive, called ABCAST. It normally delivers messages immediately upon reception, and imposes a space overhead proportional to the size of the groups to which the sender belongs, usually a small number. It is concluded that process groups and group communication can achieve performance and scaling comparable to that of a raw message transport layer. This finding contradicts the widespread concern that this style of distributed computing may be unacceptably costly.

In this paper we present a simple and efficient implementation of the rendezvous developed for a small multiprocessor system (6–10 processors). At first, we present the communication primitives with their traditional implementation. Secondly, we discuss in details our implementation and the communication architecture needed. We conclude with an evaluation showing that our implementation needs a maximum of four context switches to realize a rendezvous, which can be considered as an ideal result.

Program animation has mainly been developed for sequential programs. Animation of concurrent programs is much more uncommon, mainly because of the important technical problems. This paper presents a project whose objective is to animate any concurrent program written in the language Portal, a real time language close to Modula. The usefulness of animation in the context of teaching is shown by a few examples.

This paper describes a student project which is a major part of a senior level Operating Systems course at the Federal Institute of Technology in Lausanne.