Faster gossiping on butterfly networks
In: Theoretical Computer Science, Jg. 331 (2005-02-01), Heft 1, S. 53-72
Online
unknown
Zugriff:
Gossiping has been considered intensively for butterflies and “simple” butterflies (which have no wrap-around connections). In the “telephone” communication model, for a butterfly of order k, the best previous gossiping algorithms require 212k and 3k communication rounds, respectively. By new asymptotic methods we break through these bounds. We show that gossiping on a class of “column-based” networks, which also contains the cube-connected cycles, can be reduced to the simpler problem of “row-gossiping”. Row-gossiping in turn is reduced to “coherent row-broadcasting”. This latter problem is sufficiently simple to be solved by a sophisticated computer program for butterflies with up to 15×215 nodes. Out of the produced solutions a pattern is distilled, which can be used to perform gossiping on butterflies and simple butterflies of order k in 214k+o(k) and 212k+o(k) rounds, respectively, for any k, considerably reducing the gap with the lower bounds. The new upper bounds also hold for gossiping in the weaker “telegraph” model.
Titel: |
Faster gossiping on butterfly networks
|
---|---|
Autor/in / Beteiligte Person: | Sibeyn, Jop F. |
Link: | |
Zeitschrift: | Theoretical Computer Science, Jg. 331 (2005-02-01), Heft 1, S. 53-72 |
Veröffentlichung: | Elsevier BV, 2005 |
Medientyp: | unknown |
ISSN: | 0304-3975 (print) |
DOI: | 10.1016/j.tcs.2004.09.032 |
Schlagwort: |
|
Sonstiges: |
|