{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,25]],"date-time":"2023-10-25T09:11:13Z","timestamp":1698225073030},"reference-count":26,"publisher":"Wiley","issue":"8","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":4332,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1994,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study a probabilistic setting for distributed fault diagnosis in multiprocessor systems. A system is an undirected graph with nodes representing processors and edges representing communication links. Processors are assumed to fail independently with some probability <jats:italic>p<\/jats:italic>. They test their neighbors, and a fault\u2010free processor has probability 1 \u2212 <jats:italic>q<\/jats:italic> of discovering a fault of a failed neighbor in an individual test. Subsequently, fault\u2010free processors attempt to diagnose all the processors of the system with communication based on the test results. During communication, the behavior of faulty processors may be arbitrary (socalled malicious). For every <jats:italic>p<\/jats:italic> \u2264 \u00bd, <jats:italic>q<\/jats:italic> \u2264 1, we construct systems with <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic> log <jats:italic>n<\/jats:italic>) links in which distributed probabilistic diagnosis can be achieved with probability of correctness at least 1 \u2212 <jats:italic>n<\/jats:italic><jats:sup>\u22121<\/jats:sup>. We also show that for some small fixed <jats:italic>p<\/jats:italic> and <jats:italic>q<\/jats:italic> a similar result holds for the hypercube. On the other hand, we prove that for sufficiently small <jats:italic>k<\/jats:italic>, for a system with <jats:italic>n<\/jats:italic> processors and <jats:italic>kn<\/jats:italic> log <jats:italic>n<\/jats:italic> links, the probability of achieving correct diagnosis cannot exceed <jats:italic>n<\/jats:italic><jats:sup>\u22120.5<\/jats:sup>. \u00a9 1994 by John Wiley &amp; Sons, Inc.<\/jats:p>","DOI":"10.1002\/net.3230240803","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T19:18:27Z","timestamp":1178997507000},"page":"417-427","source":"Crossref","is-referenced-by-count":1,"title":["Reliable distributed diagnosis for multiprocessor systems with random faults"],"prefix":"10.1002","volume":"24","author":[{"given":"Piotr","family":"Berman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Pelc","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1976.1674658"},{"key":"e_1_2_1_3_2","first-page":"340","article-title":"Distributed probabilistic fault diagnosis for multiprocessor systems","volume":"20","author":"Berman P.","year":"1990","journal-title":"Dig. Pap."},{"key":"e_1_2_1_4_2","unstructured":"D. M.Blough Fault detection and diagnosis in multiprocessor systems. PhD Thesis. The John Hopkins University (1988)."},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.127443"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.177313"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.165394"},{"key":"e_1_2_1_8_2","first-page":"72","article-title":"Probabilistic treatment of diagnosis in digital systems","volume":"7","author":"Blount M. L.","year":"1977","journal-title":"Dig. Pap."},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(90)90057-C"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(81)90388-0"},{"key":"e_1_2_1_11_2","volume-title":"Concurrent Computations: Algorithms. Architectures, Technologies","author":"Dahbura A. T.","year":"1988"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1987.1676912"},{"key":"e_1_2_1_13_2","volume-title":"Probabilistic Methods in Combinatorics","author":"Erd\u00f6s P.","year":"1974"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1978.1675087"},{"key":"e_1_2_1_15_2","first-page":"560","article-title":"Probabilistic diagnosis of multiprocessor systems with arbitrary connectivity","volume":"19","author":"Fussell D.","year":"1989","journal-title":"Dig. Pap."},{"key":"e_1_2_1_16_2","doi-asserted-by":"crossref","unstructured":"J.Hastad T.Leighton andM.Newman Fast computation using faulty hypercubes Proceedings of the 21st ACM Symposium on Theory of Computing(May1989)251\u2013263.","DOI":"10.21236\/ADA211910"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.75141"},{"key":"e_1_2_1_18_2","doi-asserted-by":"crossref","unstructured":"J. G.KuhlandS. M.Reddy Distributed fault tolerance for large multiprocessor systems.Proceedings of the IEEE Symposium on Computer Architecture(1980) 23\u201330.","DOI":"10.1145\/800053.801905"},{"key":"e_1_2_1_19_2","first-page":"100","article-title":"Fault\u2010diagnosis in fully distributed systems","volume":"11","author":"Kuhl J. G.","year":"1981","journal-title":"Dig. Pap."},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1976.5009249"},{"key":"e_1_2_1_21_2","doi-asserted-by":"crossref","unstructured":"M.Malek A comparison connection assignment for diagnosis of multiprocessor systems.Proceedings of the 7th Symposium on Computer Architecture(May1980)31\u201335.","DOI":"10.1145\/800053.801906"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.21122"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.102832"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1982.1676101"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/PGEC.1967.264748"},{"key":"e_1_2_1_26_2","first-page":"278","article-title":"A probabilistic method for fault diagnosis of multiprocessor systems","volume":"18","author":"Rangarajan S.","year":"1988","journal-title":"Dig. Pap."},{"key":"e_1_2_1_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/0216071"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230240803","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230240803","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,24]],"date-time":"2023-10-24T03:22:57Z","timestamp":1698117777000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230240803"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,12]]},"references-count":26,"journal-issue":{"issue":"8","published-print":{"date-parts":[[1994,12]]}},"alternative-id":["10.1002\/net.3230240803"],"URL":"https:\/\/doi.org\/10.1002\/net.3230240803","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,12]]}}}