Optimal deadlock-free routing and broadcasting on Fibonacci cube networks

Abstract

Hsu recently proposed a new interconnection topology called Fibonacci cubes. In this correspondence we show that his routing and broadcasting algorithms do not work correctly and that a routing algorithm by Liu and Hsu does not run in optimal computation time. We also describe simple optimal deadlock-free routing and broadcasting algorithms. The routing algorithm sends a message from a source to a destination along the shortest possible path and with asymptotically optimal communication and computation times. The broadcasting procedure sends a message from source to all other nodes in optimal number of steps, equal to the diameter of the network, and uses one-port communication model.