Tight Bounds for Broadcasting in the Linear Cost Model

Bruno Beauquier 1 Olivier Delmas Stéphane Pérennes
1 SLOOP - Simulation, Object Oriented Languages and Parallelism
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : This work considers broadcast protocols made of successive communication rounds in the linear cost model: the time needed to send a message of length L is defined as \alpha +L\tau. In this model, the communication time of any algorithm \mathcal{A} is expressed as the sum R_\mathcalA\cdot\alp- ha +T_\mathcal{A} \cdot\tau, where R_\mathcalA is the number of rounds and T_\mathcalA the transmission cost of the algorithm. In order to design an efficient algorithm realizing a given communication pattern, it appears that minimizing R_\mathcalA and T_\mathcalA are antinomic goals. We study this trade-off issue for broadcast protocols. Surprisingly, such a general theoretical study has almost never been done. In the literature, only the two opposite issues are actually considered: minimizing the number of rounds in the case of short messages, or minimizing the transmission cost in the case of large messages. Our results concern the fully-connected N-nodes network K_N, with N=(k+1)^T, in the bidirectional k-ports mode. We derive tight bounds on the communication time for broadcasting in T+r rounds, our lower bounds holding for any network.
Type de document :
RR-3827, INRIA. 1999
Liste complète des métadonnées

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

Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 11:03:49
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:24:08



  • HAL Id : inria-00072831, version 1



Bruno Beauquier, Olivier Delmas, Stéphane Pérennes. Tight Bounds for Broadcasting in the Linear Cost Model. RR-3827, INRIA. 1999. 〈inria-00072831〉



Consultations de la notice


Téléchargements de fichiers