Technical Report LPCR9604

Title: Optimal Point-to-Point Broadcast Algorithms via Lopsided Trees
Authors: M. Golin and A. Schuster
PDFNot Available
Abstract: We consider the broadcasting operation in point-to-point packet-switched parallel and distributed networks of processors. We develop a general technique for the design of optimal broadcast algorithms on a wide range of such systems. Our technique makes it easier to design such algorithms and, furthermore, provides tools that can be used to derive precise analyses of their running times. As direct applications of this method we give an exact analysis of a known algorithm for the POSTAL model, and design and analyze an optimal broadcast algorithm for the MULTI_PORT MULTI_MEDIA model. We then show how our method can be applied to networks with different underlying topologies, by designing and giving an exact analysis of an optimal broadcast algorithm for the OPTICAL_RING.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the LPCR technical reports of 1996
To the main CS technical reports page

Computer science department, Technion