ISSN:
1432-0541
Keywords:
Gossiping
;
Broadcasting
;
Lower bounds
;
Communication in interconnection networks
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract The problems of gossiping and broadcasting in one-way communication mode are considered for some prominent families of graphs. The complexity is measured as the number of communication rounds in the gossip and broadcast algorithms. The main result of the paper is the precise estimation of the gossip-problem complexity in cycles. To obtain this result a new combinatorial analysis of gossiping in cycles is developed. This analysis leads to an optimal lower bound on the number of rounds, and also to the design of an optimal algorithm for gossiping in cycles. The optimal algorithm for gossiping is later used to design new, effective algorithms for gossiping in important families of interconnection networks (cube connected cycles, butterfly networks). Furthermore, a new, effective algorithm for broadcasting in shuffle-exchange networks is developed.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01908630
Permalink
