OPTIMAL-ALGORITHMS FOR DISSEMINATION OF INFORMATION IN SOME INTERCONNECTION NETWORKS

The problems of gossiping and broadcasting in one-way communication mo de are considered for some prominent families of graphs. The complexit y is measured as the number of communication rounds in the gossip and broadcast algorithms. The main result of the paper is the precise esti mation of the gossip-problem complexity in cycles. To obtain this resu lt a new combinatorial analysis of gossiping in cycles is developed. T his 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, eff ective algorithms for gossiping in important families of interconnecti on networks (cube connected cycles, butterfly networks). Furthermore, a new, effective algorithm for broadcasting in shuffle-exchange networ ks is developed.