Adaptive coherency maintenance techniques for time-varying data

Abstract

Often, data used in online decision making (for example, in determining how to react to changes in process behavior, traffic flow control, etc.) is dynamic in nature and hence the timeliness of the data delivered to the decision making process becomes very important. The delivered data must conform to certain time or value based application specific inconsistency bounds. A system designed to disseminate dynamic data can exploit user-specified coherency requirements by fetching and disseminating only those changes that are of interest to users and ignoring immediate changes. But, the design of mechanisms for such data delivery is challenging given that dynamic data changes rapidly and unpredictably, the latter making it very hard to use simple prediction techniques. In this paper, we address these challenges. Specifically, we develop mechanisms to obtain timely and consistency-preserving updates for dynamic data by pulling data from the source at strategically chosen points in time. Motivated by the need for practical system design, but using formal analytical techniques, we offer a systematic approach based on control-theoretic principles. Our solution is also unique from a control-theoretic perspective due to the presence of inherent nonlinear system components and the dependence between the sampled time and sampled value. A proportional controller with dynamically changing tuning criteria is used in this work as a means of deciding when to next refresh data from the source. Using real world traces of real-time data we show the superior performance of our feedback-driven control-theoretic approach by comparing with (i) a previously proposed adaptive refresh technique and (ii) a new pattern matching technique.