×

The \(t/k\)-diagnosability and diagnosis algorithm of pancake networks. (Chinese. English summary) Zbl 1324.68006

Summary: Fault tolerance is especially important for multiprocessor systems since the growing size of a multiprocessor system increases its vulnerability to component failures. The \(t/k\)-diagnosis is a kind of diagnostic strategy at system level that can significantly enhance the multiprocessor system’s self-diagnosing capability. It can detect up to \(t\) faulty processors (or nodes, units) which might include at most \(k\) misdiagnosed processors. This paper first explores the fault tolerance of pancake networks \(P_n(n\geqslant 5)\), and then proves that \(P_n\) is \(((k+1)n-3k-1)/k\)-diagnosable under the PMC model, \(1\leqslant k\leqslant 3\). Finally, it proposes a quick diagnosis algorithm with complexity \(O(N \log N)\) to identify all the faulty nodes.

MSC:

68M10 Network design and communication in computer systems
05C82 Small world graphs, complex networks (graph-theoretic aspects)
68M15 Reliability, testing and fault tolerance of networks and computer systems
68W15 Distributed algorithms