A description is given of how to determine the optimal migration policy for data items in a distributed database. A migration policy determines whether remote execution or migration is used when a remote request on a data item is initiated. A migration policy is modeled using a discrete Markov chain. The states in the Markov chain encode the history of previous requests and determine the probability distribution of the location of future requests. A modified policy iteration procedure is used to determine the optimal policy.>

The problem of broadcasting messages to a large number of hosts in a network is considered. The work of propagating a message is distributed and minimized among the hosts by arranging them into a minimum-cost spanning tree. Only the cooperation of the hosts that are supposed to receive these messages is required. The proposed protocol guarantees eventual and ordered delivery despite transients, and at most k permanent failures. This is achieved without requiring a large amount of information to be stored and maintained by each host, even when many hosts may initiate broadcast. Propagation delays and message overhead are derived for the proposed protocol.>

Consideration is given to the problem of propagating messages to a large number of hosts in a distributed database. The work of propagating the message is distributed and minimized among the hosts by arranging them into a minimum-cost spanning tree. Only the cooperation of the hosts that belong to the database is required. Transient and permanent failures are handled in this protocol. Eventual delivery and propagation within a network partition are guaranteed despite failures. This is achieved without requiring a large amount of information to be stored and maintained by each host, even when many hosts in the database may initiate updates.>

ROSE, a modular distributed operating system that provides support for building reliable applications, is designed and implemented. Failure detection capabilities are provided by a failure detection server. Configuration objects can be used to capture the relationship among multiple processes that cooperate to replicate certain resources. Replicated address space (RAS) objects, whose content is accessible with a high probability despite hardware failures, can be used to increase data availability. Finally, a resistant process (RP) abstraction allows user processes to survive hardware failures with minimal interruption. Two different implementations of RP are provided: one checkpoints the information about its state in an RAS object periodically; the other uses replicated execution by executing the same code in different nodes at the same time.>

A modular distributed operating system, ROSE, that provides support for building reliable applications is presented. In the kernel layer, network IPC and failure detection capabilities are provided. Above the kernel layer, replicated address space (RAS) objects are provided whose content is accessible with a high probability despite hardware failures. In the layer above, a resilient process (RP) abstraction which allows user processes to survive hardware failures with minimal interruption is provided. Two different implementations of RP are given: one checkpoints the information about its state in a RAS object periodically; the other uses replicated execution by executing the same code in different nodes at the same time.>

A scheme to replicate transactions is described. The scheme allows a k-replicated transaction to survive (k-1) failures. No coordination among the k replicas is needed until one of them reaches the end and proceeds to abort the others. Consequently, the scheme avoids the overhead and delay caused by failure detection reconfiguration, and synchronization during the k replicas' execution. A robust commit protocol to choose the transaction replica that should be committed and a procedure to choose the nodes on which a transaction replica is executed are described. The goal of the procedure is to maximize reliability.>

In this paper we describe an approach to implementing atomicity. Atomicity requires that computations appear to be all-or-nothing and executed in aserialization order. The approach we describe has three characteristics. First, it utilizes the semantics of an application to improve concurrency. Second, it reduces the complexity of application-dependent synchronization code by analyzing the process of writing it. Third, our approach hides the protocol used to arrive at a serialization order from the applications. As a result, different protocols can be used without affecting the applications. Our approach uses a history abstraction. The history captures the ordering relationship among concurrent computations. By determining what types of computations exist in the history and their parameters, a computation can determine whether it can proceed.