Abstract |
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_l* is defined as *F_l = Sum_(i=1)^k m_i^l*. This algorithm is substantially faster than the deterministic algorithm for various relevant frequency distributions. Moreover, we provide a lower bound of *Ω(D + F_5/(m_1^5 B))*, where *B* is the maximum message size, that captures the eect of the frequency distribution on the time complexity to compute the mode. |