Algorithms for distributed functional monitoring
Authors:
Open Access
- 31 March 2011
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 7 (2) , 1-20
Abstract
Consider the following problem: We have k players each receiving a stream of items, and communicating with a central coordinator. Let the multiset of items received by player i up until time t be A i ( t ). The coordinator's task is to monitor a given function f computed over the union of the inputs ∪ i A i ( t ), continuously at all times t . The goal is to minimize the number of bits communicated between the players and the coordinator. Of interest is the approximate version where the coordinator outputs 1 if f ≥ τ and 0 if f ≤ (1−ϵ)τ. This defines the ( k , f ,τ,ϵ) distributed functional monitoring problem. Functional monitoring problems are fundamental in distributed systems, in particular sensor networks, where we must minimize communication; they also connect to the well-studied streaming model and communication complexity. Yet few formal bounds are known for functional monitoring. We give upper and lower bounds for the ( k , f ,τ,ϵ) problem for some of the basic f 's. In particular, we study the frequency moments F p for p =0,1,2. For F 0 and F 1 , we obtain monitoring algorithms with cost almost the same as algorithms that compute the function for a single instance of time. However, for F 2 the monitoring problem seems to be much harder than computing the function for a single time instance. We give a carefully constructed multiround algorithm that uses “sketch summaries” at multiple levels of details and solves the ( k , F 2 ,τ,ϵ) problem with communication Õ ( k 2 /ϵ + k 3/2 /ϵ 3 ). Our algorithmic techniques are likely to be useful for other functional monitoring problems as well.Keywords
Funding Information
- National Science Foundation (414852)
This publication has 20 references indexed in Scilit:
- Optimal tracking of distributed heavy hitters and quantiles2009
- Functional Monitoring without Monotonicity2009
- Communication-efficient distributed monitoring of thresholded counts2006
- Holistic aggregates in a networked world2005
- TinyDB: an acquisitional query processing system for sensor networksACM Transactions on Database Systems, 2005
- Algorithms for dynamic geometric problems over data streams2004
- Distributed top-k monitoring2003
- Adaptive filters for continuous queries over distributed data streams2003
- The Space Complexity of Approximating the Frequency MomentsJournal of Computer and System Sciences, 1999
- Some complexity questions related to distributive computing(Preliminary Report)1979