In:
Journal of Interconnection Networks, World Scientific Pub Co Pte Ltd, Vol. 02, No. 02 ( 2001-06), p. 175-188
Kurzfassung:
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 α + Lτ, where α stands for a start-up time while Lτ represents the cost of sending L bits of data in a channel with bandwidth 1/τ. In this model, the communication time of any algorithm [Formula: see text] is expressed as the sum [Formula: see text] , where [Formula: see text] is the number of rounds and [Formula: see text] the transmission cost of the algorithm. In order to design an efficient algorithm realizing a given communication pattern, it appears that minimizing [Formula: see text] and [Formula: see text] 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.
Materialart:
Online-Ressource
ISSN:
0219-2659
,
1793-6713
DOI:
10.1142/S0219265901000312
Sprache:
Englisch
Verlag:
World Scientific Pub Co Pte Ltd
Publikationsdatum:
2001
Permalink