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

S. Fujita (Japan)


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


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:

Go Back