TY - CONF
T1 - Broadcasting on networks of workstations
T2 - Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures
Y1 - 2005
A1 - Khuller, Samir
A1 - Kim,Yoo-Ah
A1 - Wan,Yung-Chun Justin
KW - Approximation algorithms
KW - Broadcasting
KW - multicasting
AB - 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.
JA - Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures
T3 - SPAA '05
PB - ACM
CY - New York, NY, USA
SN - 1-58113-986-1
UR - http://doi.acm.org/10.1145/1073970.1074017
M3 - 10.1145/1073970.1074017
ER -