Broadcasting and Gossiping in de Bruijn Networks

Communication schemes based on store and forward routing, in which a processor can communicate simultaneously with all its neighbors (in parallel) are considered. Moreover, the authors assume that sending a message of length $L$ from a node to a neighbor takes time $\beta + L \tau$. The authors give efficient broadcasting and gossiping protocols for the de Bruijn networks. To do this, arc-disjoint spanning trees of small depth rooted at a given vertex in de Bruijn digraphs are constructed.