Broadcasting on networks of workstations

Samir Khuller*, Yoo Ah Kim, Yung Chun Wan

*Corresponding author for this work

Research output: Contribution to conferencePaperpeer-review

5 Scopus citations

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 languageEnglish (US)
Pages279-288
Number of pages10
DOIs
StatePublished - Dec 1 2005
EventSeventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures - Las Vegas, NV, United States
Duration: Jul 18 2005Jul 20 2005

Conference

ConferenceSeventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures
CountryUnited States
CityLas Vegas, NV
Period7/18/057/20/05

Keywords

  • Approximation Algorithms
  • Broadcasting
  • Multicasting

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Broadcasting on networks of workstations'. Together they form a unique fingerprint.

Cite this