Broadcasting and gossiping in de Bruijn networks. (English) Zbl 0802.68094
Summary: 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.
MSC:
68R10 | Graph theory (including graph drawing) in computer science |
68M10 | Network design and communication in computer systems |
90B18 | Communication networks in operations research |
05C05 | Trees |
05C35 | Extremal problems in graph theory |