David Ben-David, M.Sc. Thesis Seminar
Wednesday, 14.3.2012, 13:00
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.