Distributed computation of the mode
Fabian Kühn, Thomas Locher, Stefan Schmid · 2008
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 mi be the number of occurrences of the element ei in the ordered list of occurrences m1m2≥ ... ≥ mk. 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 + F2/m12*log k) time with high probability, where the frequency moment Ft is defined as Ft = sumi=1k mit. This algorithm is substantially faster than the deterministic algorithm for various relevant frequency distributions. Moreover, we provide a lower bound of Omega(D+F5/(m15B)), where B is the maximum message size, that captures the effect of the frequency distribution on the time complexity to compute the mode.