Visualization tools that illustrate communication in parallel programs use Fidge/Mattern timestamps to efficiently answer precedence queries. These timestamps have poor execution efficiency when the number of processes is large, limiting the scalability of the tool. Self-organizing hierarchical cluster timestamps can scale if the clusters they use capture communication locality. However, no clustering algorithm has been presented that enables these timestamps to work. We evaluate two clustering strategies for such timestamps, one static and one dynamic. The static algorithm was chosen to demonstrate an unproven assumption of cluster timestamps, namely that good clustering will always yield significant space saving, and to demonstrate that it is possible to select a range of cluster sizes that provide such a savings. We then assessed the merge-on-N/sup th/-communication approach. In all but two cases it provides a timestamp size that is with 20% of the best achievable. We present detailed results for the strategies evaluated.

Partial-order data structures used in distributed-system observation tools typically use vector timestamps to efficiently determine event precedence. Unfortunately all current dynamic vector-timestamp algorithms either require a vector of size equal to the number of processes in the computation or require a graph search operation to determine event precedence. This fundamentally limits the scalability of such observation systems. In this paper we present an algorithm for hierarchical, clustered vector time-stamps. We present results for a variety of computation environments that demonstrate such timestamps can reduce space consumption by more than an order-of-magnitude over Fidge/Mattern timestamps while still providing acceptable time bounds for computing timestamps and determining event precedence.

For large installations, event management is critical to ensuring service quality by responding rapidly to exceptional situations. The key to this is having experts encode their knowledge (e.g., in rules, state machines, codebooks) about the relationship between event patterns and actions to take. Unfortunately, doing so is time-consuming and knowledge-intensive. We propose reducing this burden by using offline decision support consisting of visualizing and mining event histories to discover patterns in event data. Our experience with a wide variety of production data has identified several patterns of interest such as, event bursts and partial periodicities. Herein, we use production data to illustrate how to visualize and mine event patterns, and we describe a tool we have developed to aid in pattern discovery.

Multiprocessor systems are widely used in many application programs to enhance system reliability and performance. However, reliability does not come naturally with multiple processors. We develop a multi-invariant data structure approach to ensure efficient and robust access to shared data structures in multiprocessor systems. Essentially, the data structure is designed to satisfy two invariants, a strong invariant, and a weak invariant. The system operates at its peak performance when the strong invariant is true. The system will operate correctly even when only the weak invariant is true, though perhaps at a lower performance level. The design ensures that the weak invariant will always be true in spite of fail-stop processor failures during the execution. By allowing the system to converge to a state satisfying only the weak invariant, the overhead for incorporating fault tolerance can be reduced. We present the basic idea of multi-invariant data structures. We also develop design rules that systematically convert fault-intolerant data abstractions into corresponding fault-tolerant versions. In this transformation, we augment the data structure and access algorithms to ensure that the system always converges to the weak invariant, even in the presence of fail-stop processor failures. We also design methods for the detection of integrity violations and for restoring the strong invariant. Two data structures, namely binary search tree and double-linked list, are used to illustrate the concept of multi-invariant data structures.

Designing and implementing a visual debugger for distributed programs is a significant challenge. Distributed applications are often large and frequently exhibit a high degree of complexity. Consequently, a debugger must address problems of complexity and scale in at least two ways. First, appropriate user interfaces should allow a user to manage the vast amount of information typically obtained from distributed executions. Second, the tool itself, in handling this information, should be implemented efficiently, providing a user with reasonable response times for interactive use. Our research efforts, concentrating on these problems, have led to the development of Poet, a tool for the collection and presentation of event-based traces of distributed executions. Poet makes as few assumptions as possible about characteristics that must be possessed by all target environments. Information describing each target environment is placed in configuration files, allowing a single set of Poet executables to be used for all target environments. Comparing Poet's performance to XPVM, the standard visualization tool for PVM executions, reveals that this target-system independence does not impose a performance penalty.

Debugging distributed applications presents many challenges in addition to those found in debugging sequential applications. This paper describes a tool, and the principles underlying it, that has been developed to assist in debugging such distributed applications. Although the tool can also be applied in other environments, this paper primarily describes its application to OSF DCE. Special attention is also given to a facility that has presently been implemented only for OSF DCE, the ability to replay an application, that is, to re-execute it with execution constrained to follow the partial order of an initial execution.

The work presents a new protocol, VELOS, for tolerating partitionings in distributed systems with replicated data. Our primary goals were influenced by efficiency and availability constraints. The proposed protocol achieves optimal availability, according to a well known metric, while ensuring one copy serializability. In addition, however, VELOS is designed to reduce the cost involved in achieving high availability. We have developed mechanisms through which transactions, in the absence of failures, can access replicated data objects and observe shorter delays than related protocols, and impose smaller loads on the network and the servers. Furthermore, VELOS offers high availability without relying on system transactions that must execute to restore availability when failures and recoveries occur. Such system transactions typically access all (replicas of all) data objects and thus introduce significant delays to user transactions and consume large quantities of resources such as network bandwidth and CPU cycles. Thus, we offer our protocol as a proof that high availability can be achieved inexpensively.

Replication techniques for transaction-based distributed systems generally achieve increased availability but with a significant performance penalty. We present a new replication paradigm, the location-based paradigm, which addresses availability and other performance issues. It provides availability similar to quorum-based replication protocols but with transaction-execution delays similar to one-copy systems. The paradigm further exploits replication to improve performance in two instances. First, it takes advantage of local or nearby replicas to further improve the response time of transactions, achieving smaller execution delays than one-copy systems. Second, it takes advantage of replication to facilitate the independent crash recovery of replica sites-a goal which is unattainable in one-copy systems. In addition to the above the location-based paradigm avoids bottlenecks, facilitates load balancing, and minimizes the disruption of service when failures and recoveries occur. In this paper we present the paradigm, a formal proof of correctness, and a detailed simulation study comparing our paradigm to one-copy systems and to other approaches to replication control.>

Research efforts in replication-control protocols primarily use replication as a means of increasing availability in distributed systems. It is well-known, however, that replication can reduce the costs of accessing remotely-stored data in distributed systems. We contribute a classification of replicas and a replication-control protocol which introduce the availability benefits of replication and, at the same time, exploit replication to improve performance, by reducing response time. Each replica class has different consistency requirements. Metareplicas keep track of up-to-date replicas for recently-accessed objects and help exploit data-reference localities. Thus they allow many transaction operations to execute synchronously at only a single (and often local) replica. Pseudoreplicas are nonpermanent replicas that facilitate "localized execution" of transaction operations. True replicas are ordinary, permanent replicas as used in other replication schemes. For many commonly occurring replication scenarios, the protocol outperforms both replication-control protocols in the literature and nonreplicated systems, while offering the availability benefits of replication.>

Replication has been primarily used as a means of increasing availability in distributed systems. It is known that replication can mitigate the costs of accessing remotely stored data in distributed systems. Replication control protocols in the literature have stopped short of addressing availability and performance concerns. These issues are addressed by contributing a classification of replicas with each class having different consistency requirements. Metareplicas keep track of up-to-date replicas for recently accessed objects and changes in data reference localities. Thus they allow many transaction operations to synchronously execute at only a single (and often local) replica. Pseudoreplicas are non-permanent replicas that facilitate localized execution of transaction operations. True replicas are permanent replicas that increase the availability of operations and data. A replication control protocol is presented.>

A new approach is presented for handling partitionings in replicated distributed databases. Mechanisms are developed through which transactions can access replicated data objects and observe delays similar to nonreplicated systems while enjoying the availability benefits of replication. The replication control protocol, called VELOS, achieves optimal availability, according to a well-known metric, while ensuring one-copy serializability. It is shown to provide better availability than other methods which meet the same optimality criterion. It offers these availability characteristics without relying on system transactions that must execute to restore availability, when failures and recoveries occur, but which introduce significant delays to user transactions.>

No abstract available.

A storage structure for B-trees is presented which is robust, in that many errors and combinations of errors in its structural data can be detected and corrected. The structure presented here is superior to a previous robust B-tree in a number of ways: insertion and deletion are simpler, the classes of errors which can be detected and corrected are larger, and it is simpler to implement a correction routine. These advantages are achieved without any significant increase in cost; storage space requirements and update time are almost unchanged. This paper describes briefly both the old and new B-tree implementations, and makes comparisons between them.

Abstract Research in robust data structures can be done both by theoretical analysis of properties of abstract implementations and by empirical study of real implementations. Empirical study requires a support environment for the actual implementation. In particular, if the response of the implementation to errors is being studied, a mechanism must exist for artificially injecting appropriate kinds of errors. This paper discusses techniques used in empirical investigations of data structure robustness, with particular reference to tools developed for this purpose at the University of Waterloo.

A robust storage structure is intended to provide the ability to detect and possibly correct damage to the structure. One possible source of damage is the partial completion of an update operation, due to a "crash" of the program or system performing the update. Since adding redundancy to a structure increases the number of fields which must be changed, it is not clear whether adding redundancy will help or hinder crash recovery. This paper examines some of the general principles of using robust storage structures for crash recovery. It also describes a particular class of linked list structures which can be made arbitrarily robust, and which are all suitable for crash recovery.

Some difficulties and complexities in atomic actions occur only when the concept of atomic actions is extended to allow concurrency within atomic actions and to allow a single atomic action to execute at a number of different sites. Also, providing facilities for both forward and backward recovery presents problems not found in the more usual case of allowing only backward recovery. The author presents an analysis of these problems and proposes a general structure for a solution. A syntax which might be used to specify this structure is also given and illustrated with examples. The practicality of the scheme is justified by sketching one possible implementation.

Error correction in robust data structures is a difficult problem. Several algorithms for correcting structural errors, in certain list and tree structures, are now known. These algorithms have been examined to determine common design features which may prove useful in the design of correction algorithms for other structures. This paper presents a summary of the algorithms studied and the design principles which were derived. The paper is not a "cookbook" for constructing error correction algorithms, but should prove useful to those designing such algorithms. Implications for the design of robust data structures, so that correction may be done easily, are also briefly discussed.

Abstract The addition of redundancy to data structures can be used to improve the ability of a software system to detect and correct errors, and to continue to operate according to its specifications. A case study is presented which indicates how such redundancy can be deployed and exploited at reasonable cost to improve software fault tolerance. Experimental results are reported for the small data base system considered.

The increasing cost of computer system failure has stimulated interest in improving software reliability. One way to do this is by adding redundant structural data to data structures. Such redundancy can be used to detect and correct (structural) errors in instances of a data structure. The intuitive approach of this paper, which makes heavy use of examples, is complemented by the more formal development of the companion paper, "Redundancy in Data Structures: Some Theoretical Results."

A companion paper, "Redundancy in Data Structures: Improving Software Fault Tolerance," provides an infonnal introduction to robust data structures. Here, we present the underlying theory for them, and use it to discuss the synthesis and cost effectiveness of robust data structures.