Title :
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
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;
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
DOI :
10.1109/PCCC.1992.200534
