THE COMPLEXITY OF SYSTOLIC DISSEMINATION OF INFORMATION IN INTERCONNECTION NETWORKS

Authors
HROMKOVIC J KLASING R UNGER W WAGENER H
Citation
J. Hromkovic et al., THE COMPLEXITY OF SYSTOLIC DISSEMINATION OF INFORMATION IN INTERCONNECTION NETWORKS, Informatique theorique et applications, 28(3-4), 1994, pp. 303-342
Citations number
17
Categorie Soggetti
Computer Sciences","Computer Science Information Systems
Journal title
Informatique theorique et applications → ACNP
ISSN journal
09883754
Volume
28
Issue
3-4
Year of publication
1994
Pages
303 - 342
Database
ISI
SICI code
0988-3754(1994)28:3-4<303:TCOSDO>2.0.ZU;2-A
Abstract
A concept of systolic dissemination of information in interconnection networks is presented, and the complexity of systolic gossip and broad cast in one-way (telegraph) and two-way (telephone) communication mode is investigated. The following main results are established: (i) a ge neral relation between systolic broadcast and systolic gossip, (ii) op timal systolic gossip algorithms on paths in both communication modes, and (iii) optimal systolic gossip algorithms for complete k-ary trees in both communication modes.