Tight Bounds for Delay-Sensitive Aggregation
METADATA ONLY
Loading...
Author / Producer
Date
2008
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
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 Omega(min(h,c)).
For chain networks, we prove a tight competitive ratio of Theta(min(sqrt{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.
Permanent link
Publication status
published
External links
Editor
Book title
PODC '08: Proceedings of the Twenty-Seventh ACM Symposium on Principles of Distributed Computing
Journal / series
Volume
Pages / Article No.
195 - 202
Publisher
Association for Computing Machinery
Event
27th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2008)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Competitive analysis; Wireless sensor networks; Distributed algorithms; Aggregation
Organisational unit
02640 - Inst. f. Technische Informatik und Komm. / Computer Eng. and Networks Lab.
03604 - Wattenhofer, Roger / Wattenhofer, Roger