## Abstract

Broadcasting and multicasting are fundamental operations. In this work we develop algorithms for performing broadcast and multicast in clusters of workstations. In this model, sending a message from one machine to another machine in the same cluster takes 1 time unit, and sending a message to a machine in a different cluster takes C time units. Lowekamp and Beguelin proposed heuristics for this model, but their algorithms may produce broadcast times that are arbitrarily worse than optimal. We develop the first constant factor approximation algorithms for this model. Algorithm LCF (Largest Cluster First) for the basic model is simple, efficient and has a worst case approximation guarantee of 2. We then extend these models to more complex models where we remove the assumption that an unbounded amount of simultaneous communication may happen using the global network. The algorithms for these models build on the LCF method developed for the basic problem. Finally, we develop broadcasting algorithms for the postal model where the sending processor does not block for C time units when the message is in transit. Moreover, we assume that the messages are small and so the bottleneck is the latency.

Original language | English (US) |
---|---|

Pages | 279-288 |

Number of pages | 10 |

DOIs | |

State | Published - 2005 |

Event | Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures - Las Vegas, NV, United States Duration: Jul 18 2005 → Jul 20 2005 |

### Conference

Conference | Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures |
---|---|

Country/Territory | United States |

City | Las Vegas, NV |

Period | 7/18/05 → 7/20/05 |

## Keywords

- Approximation Algorithms
- Broadcasting
- Multicasting

## ASJC Scopus subject areas

- General Engineering