An optimal fault-tolerant broadcasting algorithm for a hypercube multiprocessor

摘要

In this paper we describe an optimal fault-tolerant broadcasting algorithm in the presence of n-1 faulty processors in the hypercube multiprocessor. This algorithm takes log2(N)+1 steps to broadcast the message to all other processors. Our broadcasting algorithm is a procedure by which a processor can pass a message to all other processors in the network non-redundantly.