ANALYSIS OF GOSSIPING ALGORITHMS WITH RESTRICTED BUFFERS
Jean‐Claude König, P.S. RAO, Denis Trystram · International Journal of Parallel Emergent and Distributed Systems · 1998
In this paper we present a new algorithm for gossiping in distributed-memory parallel architectures whose interconnection network is a two-dimensional torus. The results are presented for odd-sized square torus, but the extensions are discussed at the end of the paper. The gossiping communication routine corresponds to simultaneous broadcasts at each node. In this study we assume a store-and-forward routing mechanism where all processors send a message of same length on each link during the time step. As we briefly discuss at the end, this holds also for circuit-switched routing for large messages. The main result of this work is to establish a general lower bound for gossiping in a square torus and to analyze the influence of buffering. After a brief discussion of the existing solutions, we present the principle of a new algorithm. Then, we study its complexity with restricted buffers. This new algorithm is compared with the existing gossiping algorithms from its buffering capabilities and is found to be superior.