Broadcasting on networks of workstations

Samir Khuller, Yoo Ah Kim*, Yung Chun Justin Wan

*Corresponding author for this work

Research output: Contribution to journalArticle

1 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 to a machine in the same cluster takes 1 time unit, and sending a message to a machine in a different cluster takes C(≥1) time units. The clusters may have arbitrary sizes. 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 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 node does not block for C time units when the message is in transit.

Original languageEnglish (US)
Pages (from-to)848-868
Number of pages21
JournalAlgorithmica (New York)
Volume57
Issue number4
DOIs
StatePublished - Aug 1 2010

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

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

Cite this