On diagnosability of large multiprocessor networks

Ahlswede R, Aydinian H (2008)
Discrete Applied Mathematics 156(18): 3464-3474.

Download
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Zeitschriftenaufsatz | Veröffentlicht | Englisch
Abstract / Bemerkung
We consider problems of fault diagnosis in Multi processor systems. Preparata, Metze and Chien [F.P. Preparata, G. Metze, R.T. Chien, On the connection assignment problem of diagnosable systems, IEEE Trans. Comput. EC 16 (12) (1967) 848-854] introduced a graph theoretical model for system-level diagnosis, in which processors perform tests on one another via links in the system. Fault-free processors correctly identify the Status of tested processors, while the faulty processors call give arbitrary test results. The goal is to identity faulty processors based oil the test results. A system is said to be t-diagnosable if faulty units can be identified, provided the number of faulty units present does not exceed t. We explore here diagnosis problems for n-cube systems and give bounds for diagnosability of the n-cube. We also describe a simple diagnosis algorithm A which is linear in time and which call be used for sequential diagnosis as well as for incomplete diagnosis in one step. In particular, the algorithm applied to arbitrary topology based interconnection systems G with N processors improves previously known ones. It has sequential diagnosability tA(G) >= inverted right perpendicular 2N(1/2) inverted left perpendicular - 3, which is optimal in the worst case. (C) 2008 Elsevier B.V. All rights reserved.
Erscheinungsjahr
Zeitschriftentitel
Discrete Applied Mathematics
Band
156
Ausgabe
18
Seite(n)
3464-3474
ISSN
PUB-ID

Zitieren

Ahlswede R, Aydinian H. On diagnosability of large multiprocessor networks. Discrete Applied Mathematics. 2008;156(18):3464-3474.
Ahlswede, R., & Aydinian, H. (2008). On diagnosability of large multiprocessor networks. Discrete Applied Mathematics, 156(18), 3464-3474. doi:10.1016/j.dam.2008.02.001
Ahlswede, R., and Aydinian, H. (2008). On diagnosability of large multiprocessor networks. Discrete Applied Mathematics 156, 3464-3474.
Ahlswede, R., & Aydinian, H., 2008. On diagnosability of large multiprocessor networks. Discrete Applied Mathematics, 156(18), p 3464-3474.
R. Ahlswede and H. Aydinian, “On diagnosability of large multiprocessor networks”, Discrete Applied Mathematics, vol. 156, 2008, pp. 3464-3474.
Ahlswede, R., Aydinian, H.: On diagnosability of large multiprocessor networks. Discrete Applied Mathematics. 156, 3464-3474 (2008).
Ahlswede, Rudolf, and Aydinian, Haratyun. “On diagnosability of large multiprocessor networks”. Discrete Applied Mathematics 156.18 (2008): 3464-3474.