episciences.org_489_1660011608
1660011608
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Discrete Mathematics & Theoretical Computer Science
13658050
01
01
2010
Vol. 12 no. 1
Distributed Computing and...
Tight Bounds for DelaySensitive Aggregation
Yvonne Anne
Pignolet
Stefan
Schmid
Roger
Wattenhofer
Distributed Computing and Networking
This article studies the fundamental tradeoff 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 valuesensitive aggregation, where the cost depends on the number of transmissions and the error at the root.
01
01
2010
489
https://hal.archivesouvertes.fr/hal00990442v1
10.46298/dmtcs.489
https://dmtcs.episciences.org/489

https://dmtcs.episciences.org/489/pdf