The authors present a methodology for the characterization of event recognitions based on the relationship between the system state at recognition time and its state when the event actually occurred. The methodology incorporates characteristics of the event and computation with a technique for collecting and organizing state information, thus providing an integrated approach to recognition characterization. Since the processes of a distributed computation are located at different processors in a system, the task of recognizing an event occurrence actually consists of two subtasks. First, the information pertaining to the activity described in an event definition must be collected and organized into a view of the computation's behavior which reflects the temporal relationships between the activity at the various processes. Second, this view must be analyzed in light of the user-provided event definitions to determine whether the behavior specified by the user occurred.>

A technique is presented by which state information can be organized into unified, consistent representations of the system state through the creation of simultaneous regions. This method provides a general, yet efficient means of establishing the simultaneous relationship necessary for the monitoring and recognition of event occurrences. The types of events for which a computation can be monitored are described. The methods of utilizing logical clocks and global snapshots are then presented and the reasons why they are not appropriate for use in event evaluation are discussed. The technique for establishing simultaneous regions is then presented and the behaviour of the monitoring and recognition protocol is examined in the context of specific monitoring examples. The correctness of the protocol is proved.>

Over the past fifteen years, empirical studies of the reference behavior of a number of database systems have produced seemingly contradictory results. The presence or absence of locality of reference and sequentiality have both been reported (or denied) in various papers. As such, the performance analyst or database implementor is left with little concrete guidance in the form of expected reference behavior of a database system under a realistic workload. We present empirical evidence that all of the previous results about database reference behavior are correct (or incorrect). That is, if the database reference sequence is viewed on a per-transaction instance or per-database basis, almost any reference behavior is discernible. Previous results which report the absolute absence or presence of a certain form of reference behavior were almost certainly derived from reference traces which were dominated by transactions or databases which exhibited a certain behavior. Our sample consists of roughly twenty-five million block references, from 350,000 transaction executions, directed at 175 operational on-line databases at two major corporations. As such, the sample is an order of magnitude more comprehensive than any other reported in the literature.

The protocol for synchronous approximate agreement presented by D. Dolev, et al., (J. ACM, vol.33, no. 3, pp. 499-516, 1986) exhibits the undesirable property that a fault processor, by the dissemination of a value far removed from the values held by good processors, can delay the termination of the protocol by an arbitrary amount of time. Such behavior is clearly undesirable in a fault-tolerant control system subject to hard real-time constraints. A mechanism is proposed by which discarding data suspected of being from failed processors can lead to quicker, predictable, convergence on an agreement value. Under specific assumptions about the nature of values transmitted by failed processors relative to those transmitted by good processors, Monte Carlo simulation results are presented that illuminate the tradeoff between accelerated convergence and the accuracy of the agreed-upon value.>

A generalized approach to the task of monitoring a distributed computation for event occurrences is presented that involves analyzing the characteristics of both the behavior to be recognized and the environment in which it can occur. The monotonicity of an event, which is a measurement of the stableness of its state, is the primary feature used in characterizing events. A general classification system for monitoring strategies is also presented. The classifications are based on the view of time used by the monitoring system, the delay between the occurrence of an event and its recognition, and the assertions that can be made about the system state at the point of recognition. The properties of an event and a computation can be used to determine the applicability of various types of monitoring strategies.>

An evaluation stack, used exclusively to store temporary values in expression evaluation, is known to be an effective mechanism in the implementation of high level languages. This work considers the efficient management of evaluation stacks for concurrent programming languages. Techniques for sharing a single evaluation stack among many processes, without copying on process switches, are developed. The best strategy for managing the evaluation stack is shown to depend strongly upon the scheduling paradigm adopted by the run-time support of the language. Simulation studies, driven by synthetic workloads, show that the techniques described in this paper exhibit substantial performance improvements over traditional temporary storage management schemes for concurrent languages.

Localized information referencing is a long-known and much-exploited facet of program behavior. The existence of such behavior in the data accessing patterns produced by database management systems is not currently supported by empirical results. We present experimental results which demonstrate that in certain environments and under certain important applications, locality of reference is an undeniable characteristic of the information accessing behavior of a hierarchical database management system. Furthermore, database locality of reference is in a sense more regular, predictable, and hence, more exploitable than the localized reference activity found in programs in general. The implications of these results for the performance enhancement and workload characterization of database management systems are discussed.

A methodology for the experimental investigation of the implementation of control in programming languages is presented. The methodology specifies a data-collection technique, the environment for driving simulations of control implementations, and a meaningful metric for performance evaluation. The key in the methodology is the separation of activity which is affected by the control implementation from that which is not.