Efficient Broadcasting Algorithms in Faulty Hypercubes and Star Graphs

概要

論文の詳細を見る
In this paper, we consider the fault tolerant broadcasting problem in hypercube/star-graph connected multi-port, MIMD multiprocessor systems in which each processor can send message to all its neighbors at a single time step. We give efficient broadcasting algorithms in the faulty hypercube and star graph when each node has at least one fault-free neighbor and the global faulty information is known. Our algorithm for the n-dimensional hypercube H_n, given a set F with |F| ≤ 2n-3 of faulty nodes in H_n, completes the broadcasting in at most n+2 time steps and 2^n-|F| traffic steps. The algorithm is optimal in both time steps and traffic steps. Our algorithm for the n-dimensional star graph G_n, given |F| ≤ 2n-5, completes the broadcasting in d(G_n)+c time steps and n!+O(n) traffic steps, where d(G_n)=[3(n-1)/2] is the diameter of G_n and c is a constant.
一般社団法人電子情報通信学会の論文
1996-06-14