Lecture Notes in Computer Science vol:1823 pages:313-322
HPCN Europe 2000 edition:8 location:Amsterdam, The Netherlands date:May 2000
A family of gossiping algorithms depending on a combinatorial parameter is introduced, formalized, and discussed. Three members are analyzed. It is shown that, depending on the pattern of the parameter, gossiping can use from O(N-2) to O(N) time, N being the number of communicating members. The last and best-performing algorithm, whose activity follows the execution pattern of pipelined hardware processors, is shown to exhibit high throughput and efficiency that are constant with respect to N. This translates in unlimited scalability for the corresponding gossiping service provided by this algorithm.
Proceedings of 8th International Conference on High Performance Computing and Networking Europe (HPCN Europe 2000); Lecture Notes in Computer Science (Ed. M. Bubak, H. Afsarmanesh, R. Williams, B. Hertzberger), Springer-Verlag