|
Abstract : |
The gossip problem involves communicating a unique item from every node in a graph to every other node. We study the minimum time required to do this for the binary hypercube under two models of communication. 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 which 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., |
