G. Cormode, S. Muthukrishnan, and K. Yi. Algorithms for distributed, functional monitoring. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2008.

We study what we call functional monitoring problems. We have k players each tracking their inputs, say Aj(t) up until time t, and communicating with a central coordinator. The coordinator's task is to compute a given function f over the union of the inputs Ui Aj(t), continuously at all times t. The goal is to minimize the number of bits communicated between the players and the coordinator. A simple example is when f is simply the sum, and the coordinator is required to alert when the sum of a distributed set of values exceeds a given threshold. Of interest is the approximate version where the coordinator outputs 1 if f >=τ and 0 is f<=τ-ε. 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 problems in communication complexity, communication theory, and signal processing. Yet few formal bounds are known for functional monitoring.

We give upper and lower bounds for the (k,f,τ,ε) problem for foundational f's. In particular, we study frequency moments (F0, F1, F2). We show that for the simplest cases, the cost of monitoring a function can be the same as the cost of its one-time computation. However, for F2 we show a carefully constructed multi-round algorithm which uses “sketch summaries” at multiple levels of detail and solves the (k,F2,τ,ε) problem with communication O (k2/ε+ k3/23). Since frequency moment estimation is central to other problems, our results have immediate applications to histograms, wavelet computations, and others. Our algorithmic techniques are likely to be useful for other functional monitoring problems.

bib | .pdf ] Back

This file was generated by bibtex2html 1.92.