Consensus-Based Data Statistics in Distributed Network Systems
Yifan Cai, Jianping He, Wenbin Yu, Xinping Guan · 2018
Data has become increasingly important in network systems because a lot of data is needed in new technologies such as machine learning. To obtain statistics (e.g. maximum, average, and distribution) in a fully distributed way with low complexity is challenging. Existing research on consensus algorithms can successfully obtain the max/min, average and median in a distributed network, but little work has been done on how to compute other statistics, especially probability density function (PDF). In this paper, consensus-based algorithms are proposed to obtain PDF in a fully distributed way with low complexity. The key idea of our algorithms is to divide the range of nodes' values into several sections and calculate the proportions of values in each section in a fully distributed way. If nodes have their unique identifications (IDs), repeatedly run max/min consensus algorithm in the network to reach the partially max/min values and then erase them in order to reach all values exactly once. We prove that the algorithm converges in finite time. When nodes' IDs are not available, the main challenge is to solve the conflicts when two or more nodes have the same value. We propose an asymptotically converged algorithm to solve the problem in this scenario.