distributed computation of the mode
This paper studies the problem of computing the most frequent element (the mode) by means of a distributed algorithm where the elements are located at the nodes of a network. Let k denote the number of distinct elements and further let m i be the number of occurrences of the element e i in the ordered list of occurrences m 1 m 2 ? ... ? m k . We give a deterministic distributed algorithm with time complexity O(D+k) where D denotes the diameter of the graph, which is essentially tight. As our main contribution, a Monte Carlo algorithm is presented which computes the mode in O(D + F 2 /m 1 2 *log k) time with high probability, where the frequency moment F t is defined as F t = sum i=1 k m i t . This algorithm is substantially faster than the deterministic algorithm for various relevant frequency distributions. Moreover, we provide a lower bound of Omega(D+F 5 /(m 1 5 B)), where B is the maximum message size, that captures the effect of the frequency distribution on the time complexity to compute the mode.
mode most frequent element distributed algorithms aggregation