An all-to-all broadcasting algorithm for faulty hypercubes

Summary form only given. In this paper, for all-to-all broadcasting on an n-dimensional hypercube, the validity of applying a one-to-all broadcasting algorithm at most as many times as the number of nodes in the divided sub-cube is studied. With n+12 steps, Raghavendra and Sridhar presented a one-to-all broadcasting algorithm on an n-dimensional hypercube with n-1 faulty nodes. On the other hand, Park and Bose presented an all-to-all broadcasting algorithm required total step time O((2ÿn - l)/(n - f)) for an n-dimensional hypercube with up to f = |_n/2_| faulty nodes. Then, new algorithm is demanded the total step time under O((2ÿn -l )/(n - f)). or the number of fault-tolerant faults under |_n/2_|. In this paper, a new algorithm which satisfies these bounds is presented.