Technical Report MSC-2012-09

Title: Violation Resolution in Distributed Stream Networks
Authors: David Ben-David
Supervisors: Assaf Schuster and Daniel Keren
Abstract: Threshold monitoring applications in distributed stream networks continuously track the global score of the network and alert whenever a given threshold is crossed. The network's global score is computed by applying a scoring function over the aggregated streams. However, the sheer volume and dynamic nature of the streams impose excessive communication overhead.

Most recent approaches eliminate the need for continuous communication, by using local constraints assigned at the individual streams. These constraints guarantee that as long as no constraint is violated, the threshold is not crossed, and therefore no communication is necessary. Regrettably, local constraint violations become more and more frequent as the network grows and, in the presence of such violations, communication is inevitable.

In this work, we show that in most cases the violations can be resolved efficiently. Although our solution requires only a reduced subset of the network streams, finding the minimum resolving set is NP-hard. Through analysis of the probability for resolution, we suggest methods to select the resolving set so as to minimize the expected communication overhead and the expected latency of the process. Experimental results with both synthetic and real-life data sets demonstrate that our methods yield considerable improvements over existing approaches.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF or PS files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2012
To the main CS technical reports page

Computer science department, Technion