Communication-Efficient Tracking of Distributed Triggers


There has been growing interest in large-scale distributed monitoring systems, such as Dynamic Denial of Service attack detectors and sensornet-based environmental monitors. Recent work has posited that these infrastructures lack a critical component, namely a distributed-triggering mechanism that fires when an aggregate of remote-site behavior exceeds some threshold. For several scenarios, the trigger conditions of interest are naturally cumulative, they continuously monitor the accumulation of threshold infractions (e.g., resource overuse) over time. In this paper, we develop a novel framework and communication-efficient protocols to support distributed cumulative triggers. In sharp contrast to earlier work focusing on instantaneous violations, we introduce a general model of threshold conditions that enables us to track distributed cumulative violations over time windows of any size. In our system, a central coordinator efficiently tracks aggregate time-series data at remote sites by adaptively informing the sites how to locally filter their data and when to ship new information. Our proposed algorithmic framework allows us to: (1) provide guarantees on the coordinators's triggering accuracy; (2) flexibly tradeoff communication overhead versus accuracy; and, (3) develop an analytic solution for computing local filtering parameters. Our work is the first to solve the problem of communication-efficient monitoring for distributed cumulative trigger conditions using principled solutions with accuracy guarantees. We evaluate our system using time-series data generated from SNORT logs on PlanetLab nodes and demonstrate that our methods yield significant communication overhead reductions while simultaneously achieving high detection accuracy, even for highly variable data streams.