Distributed algorithms for shortest-path, deadlock-free routing and broadcasting in Fibonacci cubes

Author

Liu, Jenshiuh ; Hsu, Wen-Jing

Author_Institution

Dept. of Comput. Sci., Michigan State Univ., East Lansing, MI, USA

fYear

1992

fDate

1-3 April 1992

Firstpage

23

Lastpage

30

Abstract

Distributed routing and broadcasting algorithms for the Fibonacci cube are presented. The routing algorithm is shown to find shortest and deadlock-free paths. Two communication models are considered for the broadcasting. It is shown that the all-port broadcasting algorithm is optimal in terms of minimized routing steps. An upper bound is obtained for the one-port broadcasting algorithm, which is shown to be optimal for certain cases. The time complexities of the all- and one-port broadcasting algorithms are examined.<>

Keywords

computational complexity; concurrency control; hypercube networks; multiprocessor interconnection networks; Fibonacci cubes; all-port broadcasting algorithm; broadcasting; deadlock-free; one-port broadcasting algorithm; routing; shortest-path; time complexities; Application software; Broadcasting; Computer science; Data communication; Distributed algorithms; Fault tolerance; Hypercubes; Routing; System recovery; Topology;

fLanguage

English

Publisher

ieee

Conference_Titel

Computers and Communications, 1992. Conference Proceedings., Eleventh Annual International Phoenix Conference on

Conference_Location

Scottsdale, AZ, USA

Print_ISBN

0-7803-0605-8

Type

conf

DOI

10.1109/PCCC.1992.200534

Filename

200534