Title: Algorithms for Distributed Functional Monitoring
Speaker:  Ke Yi
HKUST

Date: Friday, November 23, 2007
Time 11:30-12:30PM
Venue: Room 3501, HKUST

 
Abstract:
We study what we call functional monitoring problems. We have k
players each tracking their inputs, say player i tracking a multiset
A_i(t) up until time t, and communicating with a central coordinator.
The coordinator's task is to monitor a given function f computed over
the union of the inputs, 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 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>tau and 0 if
f<tau(1-eps). This defines the (k; f; tau; eps) 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; tau; eps) problem for some of the basic f's. In particular,
we study frequency moments (F0; F1; F2), the "holy grail" problem in
streaming algorithms.

This is joint work with Graham Cormode and S. Muthukrishnan.