Fault diagnosis in a small constant number of parallel testing rounds

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fault diagnosis in a small constant number of parallel testing rounds

Full text

Pdf (910 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures table of contents

Velen, Germany

Pages: 21 - 29

Year of Publication: 1993

ISBN:0-89791-599-2

Authors

Richard Beigel
Grigorii Margulis
Daniel A. Spielman

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
European Comp Soc : European Computer Society

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 10, Citation Count: 6

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/165231.165234 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	N. Alon , F. R. K. Chung, Explicit construction of linear sized tolerant networks, Discrete Mathematics, v.72 n.1-3, p.15-19, December 1988 [doi>10.1016/0012-365X(88)90189-6]
	2	R. Beigel , S. R. Kosaraju , G. F. Sullican, Locating faults in a constant number of parallel testing rounds, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.189-198, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72956]
	3	P. M. Blecher. On a logical problem. Discrete Math., 43:107-110, 1983.
	4	John Adrian Bondy, Graph Theory With Applications, Elsevier Science Ltd, 1976
	5	A.T. Dahbura and G. M. Masson. An O(n2"#) fault identification algorithm for diagnosable systems. IEEE Trans. Comput., 1984.
	6	S. L. Hakimi and K. Nakajima. On adaptive system diagnosis. IEEE Trans. Compnt., C-33(3):234-240, 1984.
	7	S. L. Hakimi and E. F. Schmeichel. An adaptive algorithm for system level diagnosis. J. of Alg., 5:526- 530, 1984.
	8	A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8(3):261-277, 1988.
	9	U. Manber. System diagnosis with repair. IEEE Trans. Compui., C-29:934-937, 1980.
	10	G. A. Margulis. Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators. Problems of Information Transmission, 24:39-46, 1988. Translated from Problemy Peredachi Informatsii, Vol. 24, No. 1, pp. 51-60, Jan-Mar, 1988.
	11	E. M. Palmer. Graphical Evolution. John Wiley & Sons, New York, 1985.
	12	F. P. Preparata, G. Metze, and R. T. Chien. On the connection assignment problem of diagnosable systems. IEEE Trans. Electron. Comput., EC-16:848-854, 1967.
	13	E. Schmeichel, S. Hakimi, M. Otsuka, and G. Sullivan. On minimizing testing rounds for fault identification. In 18th Int'l Syrup. Fault-Tolerant Comput., 1988.
	14	W. Smith, 1989. Personal communication.
	15	G. F. Sullivan. A polynomial time algorithm for fault diagnosability. In Proc. 25th FOGS, pp. 148-156, 1984.

CITED BY 6

	Michael T. Goodrich , Michael J. Nelson , Jonathan Z. Sun, The rainbow skip graph: a fault-tolerant constant-degree distributed data structure, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.384-393, January 22-26, 2006, Miami, Florida
	Andrzej Pelc, Optimal Diagnosis of Heterogeneous Systems with Random Faults, IEEE Transactions on Computers, v.47 n.3, p.298-304, March 1998
	Evangelos Kranakis , Andrzej Pelc, Better Adaptive Diagnosis of Hypercubes, IEEE Transactions on Computers, v.49 n.10, p.1013-1020, October 2000
	Andrzej Pelc , Eli Upfal, Reliable Fault Diagnosis with Few Tests, Combinatorics, Probability and Computing, v.7 n.3, p.323-333, September 1998
	Michael T. Goodrich , Daniel S. Hirschberg, Efficient parallel algorithms for dead sensor diagnosis and multiple access channels, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	Michael T. Goodrich, Pipelined algorithms to detect cheating in long-term grid computations, Theoretical Computer Science, v.408 n.2-3, p.199-207, November, 2008