In:
ACM Transactions on Algorithms, Association for Computing Machinery (ACM), Vol. 7, No. 2 ( 2011-03), p. 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.
Type of Medium:
Online Resource
ISSN:
1549-6325
,
1549-6333
DOI:
10.1145/1921659.1921667
Language:
English
Publisher:
Association for Computing Machinery (ACM)
Publication Date:
2011
detail.hit.zdb_id:
2198259-4
Bookmarklink
