@inproceedings{KLS-DCM-08,
Title = {Distributed Computation of the Mode},
Author = {Fabian Kuhn and Thomas Locher and Schmid, Stefan},
Booktitle = {27th ACM Symposium on Principles of Distributed Computing (PODC)},
Pages = {15--24},
Year = {2008},
Isbn = {978-1-59593-989-0},
Doi = {http://dx.doi.org/10.1145/1400751.1400756},
Location = {Toronto, Canada},
Month = {August},
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 {\it k} denote the number of distinct elements and further let {\it m_i} be the number of occurrences of the element {\it e_i} in the ordered list of occurrences {\it m_1>m_2>=...>=m_k}. We give a deterministic distributed algorithm with time complexity {\it O(D+k)} where {\it 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 {\it O(D + F_2/m_1^2 log k)} time with high probability, where the frequency moment {\it F_l} is defined as {\it 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 {\it $\Omega$(D + F_5/(m_1^5 B))}, where {\it B} is the maximum message size, that captures the eect of the frequency distribution on the time complexity to compute the mode.},
Url = {http://www.net.t-labs.tu-berlin.de/papers/KLS-DCM-08.pdf},
Keywords = {dalgo},
Projectname = {distributed_systems and distr_sys_select and thisisimportant}
}