## Algorithms for distributed functional monitoring, Aug. 2008.
Talk at Dagstuhl Seminar on Sublinear Algorithms.

We study what we call *functional monitoring* problems. 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 U_{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 problems in streaming algorithms, 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
some of the basic *f*'s. In particular, we study frequency moments (*F*_{0},
*F*_{1}, *F*_{2}). For *F*_{0} and *F*_{1}, we obtain continuously monitoring
algorithms with costs almost the same as their one-shot computation
algorithms. However, for *F*_{2} the monitoring problem seems much harder.
We give a carefully constructed multi-round algorithm that uses “sketch
summaries” at multiple levels of detail and solves the
(*k*,*F*_{2},τ,ε) problem with communication *O* (*k*^{2}/ε
+ *k*^{3/2}/ε^{3}).

[ bib |
slides ]
Back

*This file was generated by
bibtex2html 1.92.*