Fault-Tolerant Optimal Broadcast Algorithm for the Hypercube Topology

Authors: Lokendra Singh Umrao, Ravi Shankar Singh

Abstract:

This paper presents an optimal broadcast algorithm for the hypercube networks. The main focus of the paper is the effectiveness of the algorithm in the presence of many node faults. For the optimal solution, our algorithm builds with spanning tree connecting the all nodes of the networks, through which messages are propagated from source node to remaining nodes. At any given time, maximum n − 1 nodes may fail due to crashing. We show that the hypercube networks are strongly fault-tolerant. Simulation results analyze to accomplish algorithm characteristics under many node faults. We have compared our simulation results between our proposed method and the Fu’s method. Fu’s approach cannot tolerate n − 1 faulty nodes in the worst case, but our approach can tolerate n − 1 faulty nodes.

Keywords: Fault tolerance, hypercube, broadcasting, link/node faults, routing.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1105517

References:

[1] Lin, Jeng-Wei, “Broadcast scheduling for a p2p spanning tree”, IEEE International Conference on Communications. ICC’08, pp. 5614–5618, 2008.
[2] Saad, Youcef and Schultz, Martin H, “Topological properties of hypercubes”, IEEE Transactions on Computers, vol. 37, no. 7, pp. 867–872, 1988.
[3] Figueira, Silvia M and Mendes, Christine, “Dynamically adaptive binomial trees for broadcasting in heterogeneous networks of workstations”, High Performance Computing for Computational Science-VECPAR 2004, pp. 480–495, 2005.
[4] Dunigan, Thomas H., “Performance of the Intel iPSC/860 and Ncube 6400 hypercubes”, Parallel Computing, vol. 17, no. 10, pp. 1285–1302, 1991.
[5] Palmer, John and Steele Jr, Guy L, “Connection Machine model CM-5 system overview”, Fourth Symposium on the Frontiers of Massively Parallel Computation., pp. 474–483, 1992.
[6] Whitney, Steve and McCalpin, John and Bitar, Nawaf and Richardson, John L and Stevens, Luis, “The SGI Origin software environment and application performance”, IEEE Proceedings, Compcon’97., pp. 165–170, 1997.
[7] Lee, Tze Chiang and Hayes, John P., “A fault-tolerant communication scheme for hypercube computers””, IEEE Transactions on Computers, vol. 41, no. 10, pp. 1242–1256, 1992,
[8] Wu, Jie and Fernandez, Eduardo B, “Broadcasting in faulty hypercubes”, Microprocessing and microprogramming, vol. 39, no. 1, pp. 43–53, 1993.
[9] Lee, Peter Alan and Anderson, Thomas, “Fault tolerance”, 1990.
[10] Blough, Douglas M and Bagherzadeh, Nader, “Near-optimal message routing and broadcasting in faulty hypercubes”, International Journal of Parallel Programming, vol. 19, no. 5, pp. 405–423, 1990.
[11] Blough, Douglas M and Wang, HY, “Cooperative diagnosis and routing in fault-tolerant multiprocessor systems”, Journal of Parallel and Distributed Computing, vol. 27, no. 2, pp. 205–211, 1995.
[12] Krull, Jace W and Wu, Jie and Molina, Andres M, “Evaluation of a fault tolerant distributed broadcast algorithm in hypercube multicomputers”, Proceedings of the 1992 ACM annual conference on Communications, pp. 459–466, 1992.
[13] Xiang, Dong, “Fault-tolerant routing in hypercube multicomputers using local safety information”, IEEE Transactions on Parallel and Distributed Systems, vol. 12, no. 9, pp. 942–951, 2001.
[14] Xiang, Dong and Chen, Ai, “Partial path set-up for fault-tolerant routing in hypercubes”, International Proceedings on Parallel and Distributed Processing Symposium, pp. 8–18, 2003.
[15] Xiang, Dong and Chen, Ai and Wu, Jie, “Local-safety-information-based fault-tolerant broadcasting in hypercubes”, J. Inf. Sci. Eng., vol. 19, no. 3, pp. 467–478, 2003.
[16] Liu, Fangai and Song, Ying, “Broadcast in the locally k-subcube-connected hypercube networks with faulty tolerance”, Networking and Mobile Computing, pp. 305–313, 2005.
[17] Xiang, Dong, “Fault-tolerant routing in hypercubes using partial path set-up”, Future Generation Computer Systems, vol. 22, no. 7, pp. 812–819, 2006.
[18] Jiang, Zhen and Wu, Jie and Wang, Dajin, “A new fault-information model for adaptive & minimal routing in 3-D meshes”, IEEE Transactions on Reliability, vol. 57, no. 1, pp. 149–162, 2008.
[19] Chen, Jianer and Wang, Guojun and Chen, Songqiao, “Locally subcube-connected hypercube networks: Theoretical analysis and experimental results”, Computers, IEEE Transactions on, vol. 51, no. 5, pp. 530–540, 2002.
[20] Huang, Huang-Ming and Yang, Chang-Biau and Tseng, Kuo-Tsung and others, “Broadcasting on uni-directional hypercubes and its applications”, J. Inf. Sci. Eng., vol. 19, no. 2, pp. 183–203, 2003.
[21] Xiang, Dong and Chen, Ai and Wu, Jie, “Reliable broadcasting in wormhole-routed hypercube-connected networks using local safety information”, IEEE Transactions on Reliability, vol. 52, no. 2, pp. 245–256, 2003.
[22] Chen, Jianer and Kanj, Iyad A and Wang, Guojun, “Hypercube network fault tolerance: A probabilistic approach”, Journal of Interconnection Networks, vol. 6, no. 01, pp. 17–34, 2005.
[23] Chen, Yu-Wei, “Improved one-to-all broadcasting algorithms on faulty SIMD hypercubes”, Journal of Parallel and Distributed Computing, vol. 65, no. 12, pp. 1596–1600, 2005.
[24] Dong, Qiang and Yang, Xiao-Fan, “Fault-Tolerant Cycle Embedding in Restricted Hypercube-like Networks with More Faulty Nodes”, Journal of Information Science and Engineering, vol. 28, pp. 419–426, 2012.
[25] Fu, Jung-Sheng, “Longest fault-free paths in hypercubes with vertex faults”, Information Sciences, vol. 176, no. 7, pp. 759–771, 2006.