Fault-tolerant broadcast is a fundamental service in distributed systems, by which processes can communicate with each other consistently and reliably. It has two main forms: Reliable Broadcast (RB) and Uniform Reliable Broadcast (URB). This service has been extensively investigated in non-anonymous distributed systems where processes have unique identifers, usually assume the communication channels are reliable, which is not always the case in real systems. In this paper, the fault-tolerant broadcast service is studied in an anonymous asynchronous message passing distributed system model with fair lossy communication channels. Firstly, two simple and non-quiescent algorithms implementing RB and URB are given. Secondly, two new classes of failure detectors A_Theta and AP* are proposed. Finally, with the information provided by A_Theta and AP*, quiescent algorithms for both RB and URB are given.

This paper is on homonymous distributed systems where processes are prone to crash failures and have no initial knowledge of the system membership (``homonymous'' means that several processes may have the same identifier). New classes of failure detectors suited to these systems are first defined. Among them, the classes $\HO$ and $\HS$ are introduced that are the homonymous counterparts of the classes $\Omega$ and $\Sigma$, respectively. (Recall that the pair $\langle \Omega, \Sigma\rangle$ defines the weakest failure detector to solve consensus.) Then, the paper shows how $\HO$ and $\HS$ can be implemented in homonymous systems without membership knowledge (under different synchrony requirements). Finally, two algorithms are presented that use these failure detectors to solve consensus in homonymous asynchronous systems where there is no initial knowledge of the membership. One algorithm solves consensus with $\langle \HO, \HS\rangle$, while the other uses only $\HO$, but needs a majority of correct processes. Observe that the systems with unique identifiers and anonymous systems are extreme cases of homonymous systems from which follows that all these results also apply to these systems. Interestingly, the new failure detector class $\HO$ can be implemented with partial synchrony, while the analogous class $\AO$ defined for anonymous systems can not be implemented (even in synchronous systems). Hence, the paper provides us with the first proof showing that consensus can be solved in anonymous systems with only partial synchrony (and a majority of correct processes).

In this paper we explore the minimal system requirements to implement unreliable failure detectors. We first consider systems formed by lossy asynchronous and eventually timely links. On these systems we define two properties, the weak property and the strong property, depending on whether all correct processes can be reached with links that are not lossy asynchronous from one or from all correct processes, respectively. We present necessary conditions based on these properties. We show that there is no algorithm that implements diamS, Omega, nor S (resp. diamP nor P) if we allow one single failure in a system that, when all processes are correct, does not satisfy the weak (resp. strong) property. Then, we propose an algorithm that implements diamP if the strong property is satisfied, and diamS (and Omega with an additional assumption) if only the weak property is satisfied. For systems formed by synchronous and lossy asynchronous links only, we propose another algorithm that implements detector class P4if the strong property is satisfied, and implements a new detector class S1(and Omega with an additional assumption) if only the weak property is satisfied

No abstract available.

Unreliable failure detectors were proposed by Chandra and Toueg as mechanisms that provide information about process failures. Chandra and Toueg defined eight classes of failure detectors, depending on how accurate this information is, and presented an algorithm implementing a failure detector of one of these classes in a partially synchronous system. This algorithm is based on all-to-all communication and periodically exchanges a number of messages that is quadratic on the number of processes. We study the implementability of different classes of failure detectors in several models of partial synchrony. We first show that no failure detector with perpetual accuracy (namely, P, Q, S, and W) can be implemented in these models in systems with even a single failure. We also show that, in these models of partial synchrony, it is necessary a majority of correct processes to implement a failure detector of the class /spl theta/ proposed by Aguilera et al. Then, we present a family of distributed algorithms that implement the four classes of unreliable failure detectors with eventual accuracy (namely, /spl diams/P, /spl diams/Q, /spl diams/S, and /spl diams/W). Our algorithms are based on a logical ring arrangement of the processes, which defines the monitoring and failure information propagation pattern. The resulting algorithms periodically exchange at most a linear number of messages.

The concept of unreliable failure detecto was introduced by Chandra and Toueg [2] as a mechanism that provides (possibly incorrect) information about process failures. This mechanism has been used to solve different problems in async hronous systems, in particular the Consensus problem.

Unreliable failure detectors were introduced by Chandra and Toueg [2] as a mechanism that provides (possibly incorrect) information about process failures. They showed how unreliable failure detectors can be used to solve the Consensus problem in asynchronous systems. They also showed in [1] that one of the classes of failure detectors they defined, namely Eventually Strong (⋄S), is the weakest class allowing to solve Consensus1.

One way to implement a fault-tolerant service is by replicating it at sites that fail independently. One of the replication techniques is active replication where each request is executed by all the replicas. Thus, the effects of failures can be completely masked, resulting in an increase of service availability. In order to preserve consistency among replicas, replicas must exhibit a deterministic behavior, which has traditionally been achieved by restricting replicas to being single-threaded. However, this approach cannot be applied in some setups like transactional systems, where it is not admissible to process transactions sequentially. The authors present a deterministic scheduling algorithm for multithreaded replicas in a transactional framework. To ensure replica determinism, requests to replicated servers are submitted by means of reliable and totally ordered multicast. Internally, a deterministic scheduler ensures that all threads are scheduled in the same way at all replicas which guarantees replica consistency.

The concept of unreliable failure detector was introduced by T.D. Chandra and S. Toueg (1996) as a mechanism that provides information about process failures. Depending on the properties which the failure detectors guarantee, they proposed a taxonomy of failure detectors. It has been shown that one of the classes of this taxonomy, namely Eventually Strong (/spl nabla/S), is the weakest class allowing a solution of the Consensus problem. The authors present a new algorithm implementing /spl nabla/S. Our algorithm guarantees that eventually all the correct processes agree on a common correct process. This property trivially allows us to provide the accuracy and completeness properties required by /spl nabla/S. We show then that our algorithm is better than any other proposed implementation of /spl nabla/S in terms of the number of messages and the total amount of information periodically sent. In particular, previous algorithms require periodic exchange of at least a quadratic amount of information, while ours only requires O(n log n) (where n is the number of processes). However, we also propose a new measure to evaluate the efficiency of this kind of algorithm, the eventual monitoring degree, which does not rely on a periodic behavior and expresses the degree of processing required by the algorithms better. We show that the runs of our algorithm have optimal eventual monitoring degree.

A large number of protection domain crossings and context switches is often the cause of bad performance in complex object-oriented systems. We have identified the CompositeCall pattern which has been used to address this problem for decades. The pattern modifies the traditional client/server interaction model so that clients are able to build compound requests that are evaluated in the server domain. We implemented CompositeCalls for both a traditional OS, Linux, and an experimental object-oriented μkernel, Off++. In the first case, we learned about implications of applying CompositeCall to a non-object-oriented ‘legacy’ system. In both experiments, we learned when CompositeCalls help improving system performance and when they do not help. In addition, our experiments gave us important insights about some pernicious design traditions extensively used in OS construction. Copyright © 2000 John Wiley & Sons, Ltd.