Approximation Algorithms for Broadcasting and Gossiping

✍ Scribed by Pierre Fraigniaud; Sandrine Vial

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 152 KB
• Volume: 43
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1997.1318

✦ Synopsis

Broadcasting and gossiping are two basic communication patterns which commonly occur when programming parallel and distributed systems. This paper deals with approximation algorithms for solving these problems on arbitrary topologies. We present new strategies to derive efficient broadcasting and gossiping algorithms in any networks in the telephone model. Our objective is to minimize both round complexity and step complexity. Broadcasting strategies are based on the construction of edge-disjoint spanning trees. Gossiping strategies are based on on-line computation of matchings of maximum weight. Our approximation algorithms for broadcasting offer almost optimal complexity when the number of messages to be broadcast is large. We show that our approximation algorithm for gossiping performs optimally in many cases. We also show experimentally that it performs faster than the best-known handmade algorithms in some particular cases.