direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Es gibt keine deutsche Übersetzung dieser Webseite.

Publications by Type: Conference and Workshop Publications

see also conference papers, workshop papers, demos, and posters. (under construction)

Tight Bounds for Delay-Sensitive Aggregation
Zitatschlüssel OSW-TBDSA-08
Autor Oswald, Yvonne Anne and Schmid, Stefan and Wattenhofer, Roger
Buchtitel 27th ACM Symposium on Principles of Distributed Computing (PODC)
Seiten 195–202
Jahr 2008
ISBN 978-1-59593-989-0
DOI http://dx.doi.org/10.1145/1400751.1400778
Ort Toronto, Canada
Monat August
Zusammenfassung This paper studies the fundamental trade-off between communication cost and delay cost arising in various contexts such as control message aggregation or organization theory. An optimization problem is considered where nodes are organized in a tree topology. The nodes seek to minimize the time until the root is informed about their states and to use as few transmissions as possible at the same time. We derive an upper bound on the competitive ratio of O(min(h,c)) where h is the tree's height, and c is the transmission cost per edge. Moreover, we prove that this upper bound is tight in the sense that any oblivious algorithm has a ratio of at least Ω(min(h,c)). For chain networks, we prove a tight competitive ratio of Θ(min(h,c)). Furthermore, the paper introduces a new model for online event aggregation where the importance of an event depends on its difference to previous events.
Link zur Publikation Download Bibtex Eintrag

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe

Under Construction

This page/section is
still under construc-
tion. Please try again