Optimal point-to-point broadcast algorithms via lopsided trees

We consider the broadcasting operation in point-to-point packet-switched pa rallel and distributed networks of processors. We develop a general techniq ue for the design of optimal broadcast algorithms on a wide range of such s ystems. The technique works by modelling broadcast algorithms using lopside d trees, i.e., trees in which different edges can have different lengths. T his technique makes it easier to design such algorithms and, furthermore, p rovides generating function and Mellin transform tools that can be used to derive precise analyses of their running times. As direct applications of t his method we give an exact analysis of a known algorithm for the POSTAL mo del, and design and analyze an optimal broadcast algorithm for the MUTI_POR T MULTI_MEDIA model. We then show how our method can be applied to networks with different underlying topologies, by designing and giving an exact ana lysis of an optimal broadcast algorithm for the OPTICAL_RING. (C) 1999 Else vier Science B.V. All rights reserved.