We study what we callfunctional monitoringproblems. We havekplayers each receiving a stream of items, and communicating with a central coordinator. Let the multiset of items received by playeriup until timetbeA_{i}(t). The coordinator's task is to monitor a given functionfcomputed over the union of the inputs U_{i}A_{i}(t),continuouslyat all timest. 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 iff>=τ and 0 iff<=(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 basicf's. In particular, we study the frequency momentsF_{p}forp=0,1,2. ForF_{0}andF_{1}, we obtain monitoring algorithms with costs almost the same as their one-shot computation algorithms. However, forF_{2}the monitoring problem seems much harder. We give a carefully constructed multi-round algorithm that uses “sketch summaries” at multiple levels of details and solves the (k,F_{2},τ,ε) problem with communicationO~(k^{2}/ε+k^{3/2}/ε^{3}). Our algorithmic techniques are likely to be useful for other functional monitoring problems as well.

[ bib | Alternate Version | .pdf ] Back

*This file was generated by
bibtex2html 1.92.*