Improved Algorithms for Distributed Entropy Monitoring

Modern data management systems often need to deal with massive, dynamic and inherently distributed data sources. We collect the data using a distributed network, and at the same time try to maintain a global view of the data at a central coordinator using a minimal amount of communication. Such applications have been captured by the distributed monitoring model which has attracted a lot of attention in recent years. In this paper we investigate the monitoring of the entropy functions, which are very useful in network monitoring applications such as detecting distributed denial‐of‐service attacks. Our results improve the previous best results by Arackaparambil et al. in ICLP 1: 95–106 (2009). Our technical contribution also includes implementing the celebrated AMS sampling method (by Alon et al. in J Comput Syst Sci 58(1): 137–147 1999) in the distributed monitoring model, which could be of independent interest.