Optimal point-to-point broadcast algorithms via lopsided trees

Author

Golin, Mordecai ; Schuster, Assaf

Author_Institution

Dept. of Comput. Sci., Hong Kong Univ. of Sci. & Technol., Kowloon, Hong Kong

fYear

1997

fDate

17-19 Jun 1997

Firstpage

63

Lastpage

73

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

Keywords

distributed algorithms; message passing; packet switching; parallel algorithms; trees (mathematics); POSTAL model; lopsided trees; multiport multimedia model; optical ring; optimal broadcast algorithm; optimal broadcast algorithms; optimal point-to-point broadcast algorithms; point-to-point packet-switched processor networks; Algorithm design and analysis; Computer science; Delay; Digital multimedia broadcasting; High speed optical techniques; Multimedia communication; Multimedia databases; Network topology; Optical design; Optical network units;

fLanguage

English

Publisher

ieee

Conference_Titel

Theory of Computing and Systems, 1997., Proceedings of the Fifth Israeli Symposium on

Conference_Location

Ramat-Gan

Print_ISBN

0-8186-8037-7

Type

conf

DOI

10.1109/ISTCS.1997.595158

Filename

595158