Algorithms for distributed functional monitoring

Graham Cormode, S. Muthukrishnan, Ke Yi

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    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 / computed over the union of the inputs ∪ iA iv(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 / 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 ≥ t and 0 if / ≤ (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 communication complexity, communication theory, and signal processing. Yet few formal bounds are known lor 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 Õ(k 2/∈ + (√k/∈) 3). 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 as well.

    Original languageEnglish (US)
    Title of host publicationProceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms
    Pages1076-1085
    Number of pages10
    StatePublished - 2008
    Event19th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, United States
    Duration: Jan 20 2008Jan 22 2008

    Publication series

    NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

    Other

    Other19th Annual ACM-SIAM Symposium on Discrete Algorithms
    CountryUnited States
    CitySan Francisco, CA
    Period1/20/081/22/08

    ASJC Scopus subject areas

    • Software
    • Mathematics(all)

    Fingerprint Dive into the research topics of 'Algorithms for distributed functional monitoring'. Together they form a unique fingerprint.

    Cite this