×

Fast gossiping for the hypercube. (English) Zbl 0747.68010

Summary: The gossip problem involves communicating a unique item from every node in a graph to every other node. The minimum time required to do this for the binary hypercube under two models of communication is studied. In the first model, all communication links may be used concurrently but each may only carry information in one direction at a time. In the second, weaker model each node may be involved in only one communication at a time either as sender or receiver. In both cases, simple algorithms exist that are close to optimal. This paper shows that neither of these algorithms is optimal by exhibiting faster algorithms. In the first case, an optimal algorithm is obtained.

MSC:

68M10 Network design and communication in computer systems
68R10 Graph theory (including graph drawing) in computer science
90B18 Communication networks in operations research
68W10 Parallel algorithms in computer science
PDFBibTeX XMLCite
Full Text: DOI Link