SPECIAL ISSUE FOR CATS 2009 Distributing Frequency-Dependent Data Stream Computations ∗

The data streaming model of computation processes a sequence of continuously arriving data in a single-pass over the input using sub-linear space. For efficiency purposes, it is often desirable to perform the computations in a highly distributed fashion, as are currently done in internet applications and sensor networks. The distributed computation is typically performed using a tree-topology, where the nodes are processing elements and the data resides in the leaves of the tree. A large class of interesting and practical functions are symmetric functions (i.e., invariant of the permutation of data at the leaves) of the inputs or their approximations. Flexible distributed processing refers to the class of distributed tree computations whose output remains within a pre-specified tolerance limit regardless of the permutation of the data on the leaves or the topology of the computation tree. We consider the question: Do efficient flexible distributed computations exist corre-sponding to data streaming algorithms for computing the same function/approximation? The work by [2] shows that corresponding to any deterministic algorithm that computes a total symmetric function of an input stream, there exists a flexible distributed algorithm for computing the same function of the concatenation of the input streams at the leaves of th