Tight Bounds for Delay-Sensitive Aggregation

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 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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (1), pp.38-58
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00990442
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 15:37:12
Dernière modification le : samedi 16 décembre 2017 - 07:18:04
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:02:19

Fichier

1346-4885-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990442, version 1

Collections

Citation

Yvonne Anne Pignolet, Stefan Schmid, Roger Wattenhofer. Tight Bounds for Delay-Sensitive Aggregation. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (1), pp.38-58. 〈hal-00990442〉

Partager

Métriques

Consultations de la notice

71

Téléchargements de fichiers

398