Tight Bounds for Delay-Sensitive Aggregation

Autor: Roger Wattenhofer, Yvonne Anne Oswald, Stefan Schmid
Přispěvatelé: IBM Research Laboratory [Zurich], IBM Research [Zurich], NEC Europe Ltd., Network Laboratories, NEC Corporation, Telekom Innovation Laboratories [Berlin], Technische Universität Berlin (TU), Computer Engineering and Networks Laboratory (TIK), Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology [Zürich] (ETH Zürich)
Rok vydání: 2010
Předmět:
TheoryofComputation_MISCELLANEOUS
Optimization problem
General Computer Science
0102 computer and information sciences
02 engineering and technology
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Network topology
01 natural sciences
Upper and lower bounds
Theoretical Computer Science
Combinatorics
Aggregation
Chain (algebraic topology)
0202 electrical engineering
electronic engineering
information engineering
Discrete Mathematics and Combinatorics
Online algorithm
Event (probability theory)
Mathematics
Competitive analysis
020206 networking & telecommunications
Distributed Algorithms
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
Tree (data structure)
Transmission (telecommunications)
010201 computation theory & mathematics
Distributed algorithm
Competitive Analysis
Enhanced Data Rates for GSM Evolution
Wireless Sensor Networks
Zdroj: Discrete Mathematics and Theoretical Computer Science
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (1), pp.38-58
PODC
ISSN: 1365-8050
1462-7264
DOI: 10.46298/dmtcs.489
Popis: Distributed Computing and Networking
This article studies the fundamental trade-off between delay and communication cost in networks. We consider an online optimization problem where nodes are organized in a tree topology. The nodes seek to minimize the time until the root is informed about the changes of their states and to use as few transmissions as possible. 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 (root h, c)). Furthermore, we introduce a model for value-sensitive aggregation, where the cost depends on the number of transmissions and the error at the root.
Databáze: OpenAIRE
Externí odkaz: