  Consider a network in which $n$ distributed nodes are connected to a single
server. Each node continuously observes a data stream consisting of one value
per discrete time step. The server has to continuously monitor a given
parameter defined over all information available at the distributed nodes. That
is, in any time step $t$, it has to compute an output based on all values
currently observed across all streams. To do so, nodes can send messages to the
server and the server can broadcast messages to the nodes. The objective is the
minimisation of communication while allowing the server to compute the desired
output.
  We consider monitoring problems related to the domain $D_t$ defined to be the
set of values observed by at least one node at time $t$. We provide randomised
algorithms for monitoring $D_t$, (approximations of) the size $|D_t|$ and the
frequencies of all members of $D_t$. Besides worst-case bounds, we also obtain
improved results when inputs are parameterised according to the similarity of
observations between consecutive time steps. This parameterisation allows to
exclude inputs with rapid and heavy changes, which usually lead to the
worst-case bounds but might be rather artificial in certain scenarios.

Data Structures and Algorithms