Broadcasting on networks of workstations

Samir Khuller, Yoo Ah Kim, Yung Chun Justin Wan

Research output: Chapter in Book/Report/Conference proceedingChapter


Networks of workstations (NOWs) are a popular alternative to massively parallel machines and are widely used (e.g., the Condor project at Wisconsin [PL96] and the Berkeley NOW project [PCA95]). By simply using off-the-shelf PCs, a very powerful workstation cluster can be created, and this can provide a high amount of parallelism at relatively low cost. With the recent interest in grid computing [FK98] there is an increased interest to harness the computing power of these clusters to have them work together to solve large applications that involve intensive computation. Several projects such as Magpie [KHB+99, KBG00] are developing platforms to allow applications to run smoothly by providing primitives for performing basic operations such as broadcast, multicast, scatter, reduce, and so forth. Many of these primitives are implemented using simple heuristics. Our goal is to develop models, and an understanding of the difficult issues and challenges in implementing broadcast and multicast on such platforms. Several approximation algorithms have been developed in the theory literature, but they are for different models (typically an underlying communication graph exists that forbids any communication between nonadjacent nodes). The algorithms developed are computationally intensive and complex.

Original languageEnglish (US)
Title of host publicationHandbook of Parallel Computing
Subtitle of host publicationModels, Algorithms and Applications
PublisherCRC Press
ISBN (Electronic)9781420011296
ISBN (Print)9781584886235
StatePublished - Jan 1 2007

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)


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

Cite this