Tight Bounds for Delay-Sensitive Aggregation
Yvonne Anne Pignolet, Stefan Schmid, Roger Wattenhofer
Abstract
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
Ω(min(h,c)). For chain
networks, we prove a tight competitive ratio of
Θ(min(√ 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.
Full Text: PDF PostScript