The Algorithm of Pipelined Gossiping

Abstract

A family of gossiping algorithms depending on a parameter permutation is introduced, formalized, and discussed. Several of its members are analyzed and their asymptotic behaviour is revealed, including a member whose model and performance closely follows the one of hardware pipelined processors. This similarity is exposed. An optimizing algorithm is finally proposed and discussed as a general strategy to increase the performance of the base algorithms.

Paper published in the Journal of Systems Architecture, Vol. 52 (2006). Elsevier