Title:
	Functional Monitoring Without Monotonicity

Abstract:

  The notion of distributed functional monitoring was recently introduced by
  Cormode, Muthukrishnan and Yi (2008) 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 streams.
  The goal is to minimize the number of bits communicated by a protocol that
  correctly monitors f, to within some small error.

  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
  prove new lower bounds on this problem when f = F_p, for several values of
  p. 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, the empirical Shannon entropy of a stream. Third,
  we provide nontrivial monitoring protocols when f is either H, or any of a
  related class of entropy functions (Tsallis entropies).  These are the first
  nontrivial algorithms for distributed monitoring of non-monotone functions.