Scheinerman, Edward R. Almost sure fault tolerance in random graphs. (English) Zbl 0654.68015 SIAM J. Comput. 16, 1124-1134 (1987). Summary: We analyze the PMC model [F. P. Preparata, G. Metze, and R. T. Chien, IEEE Trans. Electron. Comput. EC-16, 848-854 (1967; Zbl 0189.169))] for fault tolerant systems by means of random directed graphs. Previous work has shown that the minimum in-degree of the testing digraph had to exceed the expected number of faulty units (vertices). We show, for much sparser digraphs than those described above, that the asymptotic probability of correct diagnosis of a faulty system tends to 1. Specifically we show that if our directed graph has n vertices, arc probability \(p=(c \log n)/n\) and vertex failure probability \(q<\) then a simple algorithm will correctly diagnose the system “almost always” when \(c>1/(1-q)\). However, when \(c<1/(1-q)\) no algorithm can correctly diagnose the system. We present a similar analysis for a family of directed graphs which are not random. We conclude with analogous results for undirected graphs. Cited in 7 Documents MSC: 68N99 Theory of software 05C80 Random graphs (graph-theoretic aspects) 68R10 Graph theory (including graph drawing) in computer science Keywords:connection assignment; diagnosis; permanent fault; random graph; self- diagnosable systems; syndrome; PMC model; fault tolerant systems Citations:Zbl 0189.169 PDFBibTeX XMLCite \textit{E. R. Scheinerman}, SIAM J. Comput. 16, 1124--1134 (1987; Zbl 0654.68015) Full Text: DOI