טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentBen-David David
SubjectViolation Resolution in Distributed Stream Networks
DepartmentDepartment of Computer Science
Supervisors Professor Assaf Schuster
Professor Daniel Keren
Full Thesis textFull thesis text - English Version


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.