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 Ai(t). The coordinator's task is to monitor a given function f computed over the union of the inputs Ui 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-ε)τ. 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 (F0, F1, F2). For F0 and F1, we obtain continuously monitoring algorithms with costs almost the same as their one-shot computation algorithms. However, for F2 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,F2,τ,ε) problem with communication O (k2/ε + k3/2/ε3).
This file was generated by bibtex2html 1.92.