A Fault Tolerant Broadcast Scheme in Pancake Interconnection Networks under the Single-Port, Half-Duplex Communication Model

S. Fujita (Japan)

Keywords

Broadcast, pancake graph, fault-tolerance, single port half-duplex model

Abstract

In this paper, we propose a simple and non-adaptive fault tolerant broadcast scheme in pancake interconnection networks under the single-port, half-duplex communication model. The proposed scheme is given the maximum number of possible faults as an input, and can tolerate up to n−2 vertex and/or edge faults in the pancake graph with n! vertices. The execution time of the scheme is at most n + 4 more time units than an optimal non-adaptive broadcast scheme when the number of faults is n − 2. Since it takes at least log2(n!) = Θ(n log n) time units to complete a broadcast under the single-port model, the gap between the lower and upper bounds is fairly small.

Important Links:

• DOI:
• From Proceeding (368) Networks, Parallel and Distributed Processing, and Applications - 2002

Go Back