Neighbourhood Broadcasting in Hypercubes

Jean-Claude Bermond (1) , Afonso Ferreira (1) , Stéphane Pérennes (1) , Joseph Peters (2)

1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
2 School of Computing Science

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.

Mots clés: broadcasting; hypercubes; neighbourhood communication

Domaines: Algorithme et structure de données [cs.DS]; Réseaux et télécommunications [cs.NI]

Jean-Claude Bermond, Afonso Ferreira, Stéphane Pérennes, Joseph Peters. Neighbourhood Broadcasting in Hypercubes. SIAM Journal on Discrete Mathematics, 2007, 21 (4), pp.823-843. ⟨hal-00429191⟩