Edge-disjoint spanning trees for the generalized butterfly networks and their applications

The generalized butterfly GBN ( d , n ) has recently gained some interest as a point-to-point interconnection network rather than the well known multi-stage butterfly networks. We construct edges-disjoint spanning trees (abbreviated EDSTs) for the GBN ( d , n ) . Our construction is based on the dec...

Full description

Saved in:
Bibliographic Details
Published in:Journal of parallel and distributed computing 2005-11, Vol.65 (11), p.1384-1396
Main Authors: Touzene, Abderezak, Day, Khaled, Monien, Burkhard
Format: Article
Language:English
Subjects:
Broadcast
Butterfly networks
Edge-disjoint trees
Fault-tolerance
Interconnection networks
Spanning trees
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The generalized butterfly GBN ( d , n ) has recently gained some interest as a point-to-point interconnection network rather than the well known multi-stage butterfly networks. We construct edges-disjoint spanning trees (abbreviated EDSTs) for the GBN ( d , n ) . Our construction is based on the decomposition of the GBN ( d , n ) into d n vertex-disjoint cycles of length n. As an application, we propose an efficient broadcasting algorithm and its fault-tolerant version for the GBN ( d , n ) . Our fault-tolerant broadcasting algorithm is optimal in terms of fault-tolerance, because it resists 2 d - 1 edge failures ( 2 d is the degree of the GBN ( d , n ) ). We also propose an efficient scattering algorithm and its fault-tolerant version which resists 2 d - 3 edge faults.
ISSN:0743-7315
1096-0848
DOI:10.1016/j.jpdc.2005.05.009