www.elsevier.com/locate/dam On sequential diagnosis of multiprocessor systems

This paper considers the problem of sequential fault diagnosis for various multiprocessor sys-tems. We propose a simple sequential diagnosis algorithm and show that the degree of sequential diagnosability of any system with N processors is at least ( N). We also show upper bounds for various networks. These are the first nontrivial upper bounds for the degree of sequential diagnos-ability, to the best of our knowledge. Our upper bounds are proved in a unified manner, which is based on the very definition of sequential diagnosability.We show that a d-dimensional grid and torus with N vertices are sequentially O(Nd/(d+1))-diagnosable, and an N-vertex k-ary tree is O( kN)-diagnosable. Moreover, we prove that the degree of sequential diagnosability of an N-vertex hyper-cube is at least(N/ log N) and at most O(N log log N/ log N), and those of an N-vertex CCC, shuffle-exchange graph, and de Bruijn graph are(N / log N)