The Taub Faculty of Computer Science Events and Talks

Threshold monitoring applications in distributed stream networks contin- uously monitor the global score of the network and alert whenever a given threshold is crossed. The network's global score is computed by applying a certain scoring function over the aggregated data derived from the network streams. However, the sheer volume and dynamic nature of the streams impose excessive communication overhead. Recently, the concept of local constraints have been presented in which the individual streams are assigned with local constraints that guaranty that as long as all the constraints are valid, the threshold is not crossed and thus, no communication over the network is required. While threshold crossings are fairly rare in most monitoring networks (e.g., natural hazard monitoring, fire detection, etc.), local constraint violations are not, and in the presence of such, a decision process should take place to determine the network status. This decision process is referred as violation resolution. Violation resolution should minimize communication cost and latency by polling the smallest subset of non-violating streams, referred as the resolving set, in the shortest time. We discuss the problem of violation resolution as a minimum resolving set detection problem and suggest bounds for the expected size of the resolving set. In addition, we present a generic algorithm for violation resolution and suggest two instances of it, designed for homogeneous and heterogeneous data setups.