direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Es gibt keine deutsche Übersetzung dieser Webseite.

Selected Publications on Distributed Systems

about distributed systems
[1]

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 [2] Download Bibtex Eintrag [3]
------ Links: ------

Zusatzinformationen / Extras

Direktzugang:

Schnellnavigation zur Seite über Nummerneingabe

Copyright TU Berlin 2008