ABSTRACT
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.
