Improved one-to-all broadcasting algorithms on faulty SIMD hypercubes

Consider an n-dimensional SIMD hypercube Hn with ⌊3n/2⌋-1 faulty nodes. With n+3log(n-1)+7,n+2log(n-1)+9,n+log(n-1)+O(loglog(n-1)),n+log(n-1)+12, and n+19 steps, this paper presents some one-to-all broadcasting algorithms on the faulty SIMD Hn. The sequence of dimensions used for broadcasting in each algorithm is the same regardless of which node is the source. The proposed one-to-all broadcasting algorithms can tolerate ⌊n/2⌋ more faulty nodes than Raghavendra and Sridhar's algorithms (J. Parallel Distrb. Comput. 35 (1996) 57) although 8 extra steps are needed. The fault-tolerance improvement of this paper is about 50%.