Neighborhood Broadcasting in Hypercubes
Jean‐Claude Bermond, Afonso Ferreira, Stéphane Pérennès, Joseph G. Peters · SIAM Journal on Discrete Mathematics · 2007
In the broadcasting problem, one node needs to broadcast a message to all other nodes in a network. If nodes can only communicate with one neighbor at a time, broadcasting takes at least $\lceil \log_2 N \rceil$ rounds in a network of N nodes. In the neighborhood broadcasting problem, the node that is broadcasting needs to inform only its neighbors. In a binary hypercube with N nodes, each node has $\log_2 N$ neighbors, so neighborhood broadcasting takes at least $\lceil \log_2 \log_2 (N+1) \rceil$ rounds. In this paper, we present asymptotically optimal neighborhood broadcast protocols for binary hypercubes.