AN EFFICIENT ALGORITHM FOR MULTIPLE SIMULTANEOUS BROADCASTS IN THE HYPERCUBE

Authors
STAMOULIS GD TSITSIKLIS JN
Citation
Gd. Stamoulis et Jn. Tsitsiklis, AN EFFICIENT ALGORITHM FOR MULTIPLE SIMULTANEOUS BROADCASTS IN THE HYPERCUBE, Information processing letters, 46(5), 1993, pp. 219-224
Citations number
7
Categorie Soggetti
Information Science & Library Science","Computer Applications & Cybernetics
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
46
Issue
5
Year of publication
1993
Pages
219 - 224
Database
ISI
SICI code
0020-0190(1993)46:5<219:AEAFMS>2.0.ZU;2-Z
Abstract
We analyze the following problem: Each of K nodes of the d-cube wishes (at the same time) to broadcast a packet to all hypercube nodes. We p resent a simple distributed algorithm for performing this task efficie ntly for any value of K and for any K-tuple of broadcasting nodes, and some variations of this algorithm that apply to special cases. In par ticular, we obtain an easily implementable algorithm for the multinode broadcast task (K = 2d), which comes within a factor of 2 from the op timal.