The Library
Algorithms for distributed functional monitoring
Tools
Cormode, Graham, Muthukrishnan, S. and Yi, Ke (2011) Algorithms for distributed functional monitoring. ACM Transactions on Algorithms , 7 (2). pp. 1-20. doi:10.1145/1921659.1921667 ISSN 1549-6325.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1145/1921659.1921667
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 Ai(t). The coordinator's task is to monitor a given function f computed over the union of the inputs ∪i Ai(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−&epsis;)τ. This defines the (k,f,τ,&epsis;) 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,τ,&epsis;) problem for some of the basic f's. In particular, we study the frequency moments Fp for p=0,1,2. For F0 and F1, we obtain monitoring algorithms with cost almost the same as algorithms that compute the function for a single instance of time. However, for F2 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,F2,τ,&epsis;) problem with communication Õ(k2/&epsis; + k3/2/&epsis;3). Our algorithmic techniques are likely to be useful for other functional monitoring problems as well.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | ACM Transactions on Algorithms | ||||
Publisher: | Association for Computing Machinery, Inc. | ||||
ISSN: | 1549-6325 | ||||
Official Date: | March 2011 | ||||
Dates: |
|
||||
Volume: | 7 | ||||
Number: | 2 | ||||
Page Range: | pp. 1-20 | ||||
DOI: | 10.1145/1921659.1921667 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |