Exchanges in circulant networks: algorithms and lower bounds

In this paper we consider the routing, broadcast and gossiping problems in circulant networks. The circulant graphs are studied extensively as reliable interconnection networks for the multiprocessor systems. The optimal circulants have the minimum diameter and the minimum average distance and, respectively, maximum of the reliability and connectivity. Review of the earlier published results in Russia and also new results are presented in the paper. The distributed routing algorithm for the optimal circulants proposed here has constant complexity independent of the number of processors in the system and is adapted to failures of processors and links. We consider gossiping in the store-and-forward, full-duplex and shouting model for the case when communicating nodes can exchange up to a fixed number p of packets at each round of gossiping (p-gossiping). A general method for evaluation of the lower bounds for p-gossiping in circulant graphs is established. The efficient parallel decentralized broadcast and gossiping algorithms for two-dimensional optimal circulants are proposed.