TU Berlin

Internet Network ArchitecturesStefan Schmid's Publications

Page Content

to Navigation

Stefan Schmid's Publications

Distributed Computation of the Mode
Citation key KLS-DCM-08
Author Fabian Kuhn and Thomas Locher and Schmid, Stefan
Title of Book 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 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.
Link to publication Download Bibtex entry

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe