Broadcasting and Gossiping in de Bruijn Networks

Abstract

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.