TU Berlin

Internet Network ArchitecturesDistributed Systems: Selected Publications

Inhalt

zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

Selected Publications on Distributed Systems

Distributed Computation of the Mode
Zitatschlüssel KLS-DCM-08
Autor Fabian Kuhn and Thomas Locher and Schmid, Stefan
Buchtitel 27th ACM Symposium on Principles of Distributed Computing (PODC)
Seiten 15–24
Jahr 2008
ISBN 978-1-59593-989-0
DOI http://dx.doi.org/10.1145/1400751.1400756
Ort Toronto, Canada
Monat August
Zusammenfassung 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 zur Publikation Download Bibtex Eintrag

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe