Fault-Tolerant Optimal Broadcast Algorithm for the Hypercube Topology

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.

Authors:

• Lokendra Singh Umrao
• Ravi Shankar Singh

Keywords:

• Fault tolerance
• hypercube
• broadcasting
• link/node faults
• routing.

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.