HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

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 , Laboratoire I3S - 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.
Document type :
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 11:03:49 AM
Last modification on : Friday, February 4, 2022 - 3:20:18 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:24:08 PM


  • 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⟩



Record views


Files downloads