Describes a new method for dynamically clustering hierarchical data which maintains good clustering within disk pages in the presence of insertions and deletions. This simple but effective method, which we call Enc, encodes the insertion order of children with respect to their parents and concatenates the insertion numbers to form a compact key for the data. This compact key is stored only in the indexing structure and does not affect the logical database schema. Experimental results show that our Enc method is very efficient for hierarchical queries and performs reasonably well for random access queries.

A practical, fault-tolerant method for reclaiming inaccessible objects in a distributed heap is presented. The algorithm is general and does not require homogeneous components. It reclaims inaccessible objects in a timely fashion, including those that reside on inaccessible cycles. It allows each computer that contains parts of the heap to garbage collect independently according to its storage requirements, using whatever algorithm it chooses. A highly available service is used to store information about the intercomputer references. The computers containing parts of the heap communicate with the central service only periodically. By using the service the overhead at each node is minimized.>

To provide high availability for services such as mail or bulletin boards, data must be replicated. One way to guarantee consistency of replicated data is to force service operations to occur in the same order at all sites, but this approach is expensive. For some applications a weaker causal operation order can preserve consistency while providing better performance. This paper describes a new way of implementing causal operations. Our technique also supports two other kinds of operations: operations that are totally ordered with respect to one another and operations that are totally ordered with respect to all other operations. The method performs well in terms of response time, operation-processing capacity, amount of stored state, and number and size of messages; it does better than replication methods based on reliable multicast techniques.

To provide high availability for services such as mail or bulletin boards, data must be replicated.One way to guarantee consistency of replicated data is to force service operations to occur in the same order at all sites, but this approach is expensive.In this paper, we propose lazy replication as a way to preserve consistency by exploiting the semantics of the service's operations to relax the constraints on ordering.Three kinds of operations are supported: operations for which the clients define the required order dynamically during the execution.operations for which the service defines the order, and operations that must be globally ordered with respect to both client ordered and service ordered operations.The method performs well in terms of response time, amount of stored state, number of messages, and availability.It is especially well suited to applications in which most operations require only the client-defined order.

This paper addresses the problem of organising and controlling activities that involve multiple steps of processing and that typically are of long duration. We explore the use of triggers and transactions to specify and organize such long-running activities. Triggers offer data- or event-driven specification of control flow, and thus provide a flexible and modular framework with which the control structures of the activities can be extended or modified. We describe a model based on event-condition-action rules and coupling modes. The execution of these rules is governed by an extended nested transaction model. Through a detailed example, we illustrate the utility of the various features of the model for chaining related steps without sacrificing concurrency, for enforcing integrity constraints, and for providing flexible failure and exception handling.

This paper describes two techniques that are only loosely related. The first is a method for constructing a highly available service for use in a distributed system. The service presents its clients with a consistent view of its state, but the view may contain old information. Clients can indicate how recent the information must be. The method can be used in any application in which the property of interest is stable: once the property becomes true, it remains true forever. The paper also describes a fault-tolerant garbage collection method for a distributed heap. The method is practical and efficient. Each computer that contains part of the heap does local garbage collection independently, using whatever algorithm it chooses, and without needing to communicate with the other computers that contain parts of the heap. The highly available central service is used to store information about inter.computer references. 1.