Functional Monitoring without Monotonicity

The notion of

distributed functional monitoring

was recently introduced by Cormode, Muthukrishnan and Yi to initiate a formal study of the communication cost of certain fundamental problems arising in distributed systems, especially sensor networks. In this model, each of

k

sites reads a stream of tokens and is in communication with a central coordinator, who wishes to continuously monitor some function

f

of

σ

, the union of the

k

streams. The goal is to minimize the number of bits communicated by a protocol that correctly monitors

f

(

σ

), to within some small error. As in previous work, we focus on a threshold version of the problem, where the coordinator’s task is simply to maintain a single output bit, which is 0 whenever

f

(

σ

) ≤ 

τ

(1 − 

ε

) and 1 whenever

f

(

σ

) ≥ 

τ

. Following Cormode et al., we term this the (

k

,

f

,

τ

,

ε

) functional monitoring problem.

In previous work, some upper and lower bounds were obtained for this problem, with

f

being a frequency moment function, e.g.,

F

0

,

F

1

,

F

2

. Importantly, these functions are

monotone

. Here, we further advance the study of such problems, proving three new classes of results. First, we provide nontrivial monitoring protocols when

f

is either

H

, the empirical Shannon entropy of a stream, or any of a related class of entropy functions (Tsallis entropies). These are the first nontrivial algorithms for distributed monitoring of non-monotone functions. Second, we study the effect of non-monotonicity of

f

on our ability to give nontrivial monitoring protocols, by considering

f

 = 

F

p

with deletions allowed, as well as

f

 = 

H

. Third, we prove new lower bounds on this problem when

f

 = 

F

p

, for several values of

p

.