Computing end-to-end delays in stream query processing

• We define denotational semantics for stream data processing that explains time information propagation.
• We design an algorithm to measure the end-to-end delays in a stream graph.
• We provide experimental evaluation to show the efficiency and effectiveness of our approach.

Real-time data processing is essential in many stream-based applications including disaster area monitoring, health monitoring, and intrusion detection. In this work, we propose an approach that measures time delays in stream query processing. We represent a stream query as a graph consisting of operators that process data and channels that transport data tokens between operators. Our model establishes a causality relationship between consumed and produced data tokens at each operator and their corresponding occurrence times. The total time taken for the computation from the input to the output of a query, i.e., end-to-end delay, is computed by the causality relationships and periodic schedules for stream queries. Experiments are conducted to validate the proposed technique.