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((2yn - l)/(n - f)) for an n-dimensional hypercube with up to f = |/spl I.bar/n/2/spl I.bar/| faulty nodes. Then, new algorithm is demanded the total step time under O((2yn -l )/(n - f)). or the number of fault-tolerant faults under |/spl I.bar/n/2/spl I.bar/|. In this paper, a new algorithm which satisfies these bounds is presented.