BROADCASTING AND GOSSIPING IN DEBRUIJN NETWORKS

被引：30

作者：

BERMOND, JC ^{[1
]}

FRAIGNIAUD, P ^{[1
]}

机构：

[1] ECOLE NORMALE SUPER LYON,LIP,IMAG,CNRS,F-69364 LYON 07,FRANCE

来源：

SIAM JOURNAL ON COMPUTING | 1994年 / 23卷 / 01期

关键词：

BROADCASTING; GOSSIPING; INTERCONNECTION NETWORKS; DEBRUIJN GRAPHS; DISJOINT SPANNING TREES;

D O I：

10.1137/S0097539791197852

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 + Ltau. 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.

引用

页码：212 / 225

页数：14

共 31 条

[1]

BERMOND JC, 1989, HYPERCUBE AND DISTRIBUTED COMPUTERS, P279

[2] LARGE FAULT-TOLERANT INTERCONNECTION NETWORKS [J].

BERMOND, JC ;

HOMOBONO, N ;

PEYRAT, C .

GRAPHS AND COMBINATORICS, 1989, 5 (02) :107-123

[3]

BERMOND JC, 1988, LECT NOTES COMPUT SC, V312, P41

[4]

BERMOND JC, 1988, C NUMER, V66, P267

[5]

BERMOND JC, 1992, GRAPH THEORY NOTES N, V22, P8

[6]

BERMOND JC, 1989, GENERAL EFFICIENT DE, V2, P199

[7]

CYPHER R, 1989, TR890201 U WASH DEP

[8]

DALLY WJ, 1987, IEEE T COMPUT, V36, P547, DOI 10.1109/TC.1987.1676939

[9]

de Bruijn N. G, 1946, KONINKLIJKE NEDERLAN, V49, P758

[10]

Edmonds J., 1972, COMBINATORIAL ALGORI, P91

← 1 2 3 4 →