On multicast algorithms for heterogeneous networks of workstations

Networks of workstations (NOWs) provide an economical platform for high per formance parallel computing. Such networks may comprise a variety of differ ent types of workstations and network devices. This paper addresses the pro blem of efficient multicast in a heterogeneous communication model. Althoug h the problem of finding optimal multicast schedules is known to be NP-comp lete in this model, a greedy algorithm has been shown experimentally to fin d good solutions in practice. In this paper we show that the greedy algorit hm finds provably near-optimal schedules in polynomial time and that optima l schedules can be found in polynomial time when the number of distinct typ es of workstations is bounded by a constant. Specifically, this paper prese nts three results. First, when there are n workstations of some constant k distinct types, the greedy algorithm is shown to find schedules that comple te at most a constant additive term later than optimal. Second, an algorith m is given that finds optimal schedules in time O(n(2k)). Finally, it is sh own that for the general problem, the greedy algorithm finds solutions that complete the multicast in at most twice the optimal time. (C) 2001 Academi c Press.