In many emerging time-critical applications, the exact time of event occurrences may not be known. In such cases, events can be represented as a probabilistic occurrence within a time interval. Thus, monitoring of timing constraints, generally used in time- critical systems, needs to incorporate the uncertainty of event occurrences. In this paper, we propose mechanisms to monitor the satisfaction/violation of timing constraints that can be assessed probabilistically. We assume a uniform distribution of event occurrence within a time interval. Our proposed algorithm determines whether the probability that a timing constraint has been satisfied exceeds a specified threshold value. A confidence threshold is a minimum satisfaction probability of the timing constraint. A timing constraint is violated if the confidence threshold is not reached. We design an efficient monitoring algorithm for detecting timing violations of a set of timing constraints by finding the earliest expiration time (EET) for each timing constraint. Since it is critical to derive implicit constraints for early detection of violation of timing constraints, we present the derivation of the implicit constraints under uncertainty using an all-pairs shortest path algorithm. Further, we propose pruning techniques to discard unnecessary implicit constraints. We present the properties and proofs of our approach.

Increasingly, business applications need to capture consumers' complex preferences interactively and monitor those preferences by translating them into event-condition-action (ECA) rules and syntactically correct processing specification. An expressive event model to specify primitive and composite events that may involve timing constraints among events is critical to such applications. Relying on the work done in active databases and real-time systems, this research proposes a new composite event model based on real-time logic (RTL). The proposed event model does not require fixed event consumption policies and allows the users to represent the exact correlation of event instances in defining composite events. It also supports a wide-range of domain-specific temporal events and constraints, such as future events, time-constrained events, and relative events. This event model is validated within an electronic brokerage architecture that unbundles the required functionalities into three separable components - business rule manager, ECA rule manager, and event monitor - with well-defined interfaces. A proof-of-concept prototype was implemented in the Java programming language to demonstrate the expressiveness of the event model and the feasibility of the architecture. The performance of the composite event monitor was evaluated by varying the number of rules, event arrival rates, and type of composite events.

We propose an algorithm for monitoring timing constraints to satisfy confidence threshold requirements when there is uncertainty in the exact timing of event occurrences. In our model, a timed event trace is examined for possible satisfaction/violation with respect to a given set of timing constraints. Every event occurrence has a timestamp given by a time interval. Assuming that the time of occurrence is uniformly distributed over the time interval, our algorithm determines whether the probability that a timing constraint has been satisfied exceeds a specified threshold value. Timing constraints are composed of deadline and delay constraints for which satisfaction probabilities are defined. A confidence threshold is a minimum satisfaction probability of the timing constraint. A timing constraint is violated if the confidence threshold is not reached by the timed event trace. We present a ptime monitoring algorithm for detecting timing violation by finding the earliest expiration time (EET) of the deadline timer for each of the cases P = 100%, 50% /spl les/ P < 100%, and 0% < P < 50%, where P is the confidence threshold of the timing constraint. We give a derivation of the implicit constraints needed for computing the EET, and we show how to use an all-pairs shortest path algorithm to compute the implicit constraints.

Efficient algorithms have been developed by a number of authors to detect constraint violation or satisfaction of timed events. In extant work, the time of every event occurrence is assumed to be known exactly. However there are practical situations where we are not sure about the exact time of occurrence of an event but we may be able to capture the uncertainty by a time interval. In this paper we propose new types of timing constraints: possible and certain constraints that are pertinent to an event model where timestamps are given by time intervals. We extend previous work in timed event monitoring that is time-point based to our interval-based model. We give an efficient algorithm for monitoring timing constraints under event timing uncertainty, and sketch its proof of correctness by extending the pruning algorithm on the constraint graph to cover interval timestamps.

Timeliness is an important attribute for e-brokerage both in the detection of opportunities in a narrow time window and also in facilitating differentiation of end-to-end quality of service (QoS). In this paper, we demonstrate how real-time event monitoring techniques can be applied to time-critical e-brokerage. We start with a formal timed event model which provides the semantics for specifying complex timing correlation rules in composite events. The formal event model of the system is based on RTL (Real Time Logic), which is important for disambiguating informal specifications when multiple instances of the same event type may appear in a timing correlation rule involving composite events. This leads to our design of an e-brokerage, online stock monitoring and alerting system which enables users to express their complex preferences and provides an alert service to users in a timely manner. The user's preferences are monitored by a real-time event monitor. We report the design of this system and some performance data characterizing some key timing parameters. Our system is being used by a class of MBA students in a field test.

In the future, automated stock trading (AST) databases will need to support execution of transactions with time constraints similar to that discussed in real-time databases. Transactions in AST databases repeat from a predictable set of transaction classes where the logical read-sets and write-sets of these classes can be established a priori. We propose a novel transaction management mechanism that exploits this a priori knowledge of data requirements to minimize wasted resources and transaction restarts inherent in existing real-time transaction processing mechanisms based on dynamic acquisition of resources. Preanalysis provides a mechanism to incorporate transaction semantics, identify potentially detrimental conflicts, and induce favorable serialization orders before transactions execute. By blocking potentially conflicting transactions, we incorporate an implicit overload management technique. Scheduling decisions can be made efficient to complement serialization orders, thus reducing unnecessary transaction restarts. Our protocol is evaluated using simulation and is shown to outperform existing real-time concurrency control mechanisms under various workload and resource parameters.