Efficient Detection of Distributed Constraint Violations

In many distributed environments, the primary function of monitoring software is to detect anomalies, that is, instances when system behavior deviates substantially from the norm. Existing approaches for detecting such abnormal behavior record system state at all times, even during normal operation, and thus incur wasteful communication overhead. In this paper, we propose communication-efficient schemes for the anomaly detection problem, which we model as one of detecting the violation of global constraints defined over distributed system variables. Our approach eliminates the need to continuously track the global system state by decomposing global constraints into local constraints that can be checked efficiently at each site. Only in the occasional event that a local constraint is violated, do we resort to more expensive global constraint checking. We formulate the problem of selecting local constraints as an optimization problem that takes into account the frequency distribution of individual system variables, and whose objective is to minimize communication costs. After showing the problem to be NP-hard, we propose approximation algorithms for computing provably near-optimal (in terms of the number of messages) local constraints. In our experiments with real-life network traffic data sets, we found that our techniques for detecting global constraint violations can reduce message communication overhead by as much as 70% compared to existing data distribution-agnostic approaches.