Cited references and notes

1. A. Frenkiel and H. Lee, “EPP: A Framework for Measuring the End-to-End Performance of Distributed Applications,” Proceedings of Performance Engineering 'Best Practices' Conference, IBM Academy of Technology (1999).
2. Using Keynote Measurements to Evaluate Content Delivery Networks, KEYNOTE, 2855 Campus Drive, San Mateo, CA 94403 (2000); available at www.keynote.com/services/html/product_lib.html.
3. J. Pearl, Probabilistic Reasoning in Intelligent Systems, Morgan Kaufmann Publishers, San Francisco, CA (1988).
4. If the problems are not marginally independent, appropriate edges must be added between them.
5. G. F. Cooper, “The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks,” Artificial Intelligence 42, Nos. 2–3, 393–405 (1990).
6. S. Kliger, S. Yemini, Y. Yemini, D. Ohsie, and S. Stolfo, “A Coding Approach to Event Correlation,” Proceedings of the Fourth International Symposium on Intelligent Network Management (1995), pp. 266–277.
7. M. Brodie, I. Rish, and S. Ma, “Optimizing Probe Selection for Fault Localization,” Twelfth International Workshop on Distributed Systems Operation and Management (October 15–17, 2001).
8. T. M. Cover and J. A. Thomas, Elements of Information Theory, John Wiley & Sons, Inc., New York (1991).
9. A paper on the NP-hardness result is to be submitted to the NIPS (Neural Information Processing Systems) 2002 Conference to be held December 10–12, 2002.
10. D. Heckerman and J. Breese, Causal Independence for Probability Assessment and Inference Using Bayesian Networks, Technical Report MSR-TR-94-08, Microsoft Research, Redmond, WA (1995).
11. Note that this noisy-AND definition is equivalent to the noisy-OR definition in Henrion et al.12 if we replace every value by its logical negation (all zeroes will be replaced by ones and vice versa). We also note that instead of considering the leak probability separately, we may assume there is an additional “leak node” always set to zero that affects an outcome of a probe T_i according to its link probability (1 - l_i ).
12. M. Henrion, M. Pradhan, B. Del Favero, K. Huang, G. Provan, and P. O'Rorke, “Why Is Diagnosis Using Belief Networks Insensitive to Imprecision in Probabilities?” Proceedings of the Twelfth Conference on Uncertainty in Artificial Intelligence (1996), pp. 307–314.
13. Clearly, finding a set of probes that may actually achieve the bound, if such a set of probes exists, is a much harder task.
14. R. Dechter and J. Pearl, “Network-Based Heuristics for Constraint Satisfaction Problems,” Artificial Intelligence 34, 1–38 (1987).
15. Algorithm Quickscore,16 specifically derived for noisy-OR networks, has the complexity
    O(2^p), where p is the number of “positive findings” (failed probes in our case). However, the algorithm is tailored to belief updating and cannot be used for finding MPE.
16. D. Heckerman, “A Tractable Inference Algorithm for Diagnosing Multiple Diseases,” Proceedings of the Fifth Conference on Uncertainty in Artificial Intelligence (1989), pp. 174–181.
17. R. Dechter and I. Rish, “A Scheme for Approximating Probabilistic Inference,” Proceedings of the Thirteenth Conference on Uncertainty in Artificial Intelligence (1997), pp. 132–141.
18. K. Kask, I. Rish, and R. Dechter, “Empirical Evaluation of Approximation Algorithms for Probabilistic Decoding,” Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence (1998), pp. 455–463.
19. I. Rish, Efficient Reasoning in Graphical Models, Ph.D. thesis, University of California, Irvine, Irvine, CA (1999).
20. A closely related example is local belief propagation,3 a linear-time approximation that became a surprisingly effective state-of-the-art technique in error-correcting coding.²¹
21. B. J. Frey and D. J. C. MacKay, “A Revolution: Belief Propagation in Graphs with Cycles,” Advances in Neural Information Processing Systems, Vol. 10, M. I. Jordan, M. J. Kearns, and S. A. Solla, Editors, MIT Press, Cambridge, MA (1998).
22. F. P. Preparata, G. Metze, and R. T. Chien, “On the Connection Assignment Problem of Diagnosable Systems,” IEEE Transactions on Electronic Computers 16, No. 6, 848–854 (December 1967).
23. J. D. Russell and C. R. Kime, “System Fault Diagnosis: Closure and Diagnosability with Repair,” IEEE Transactions on Computers C-24, No. 11, 1078–1089 (November 1975).
24. A. T. Dahbura, “System Level Diagnosis,” Concurrent Computation: Algorithms, Architectures, Technologies, Plenum Publishers, New York (1988), pp. 411–434.
25. A. Leinwand and K. Fang-Conroy, Network Management: A Practical Perspective, 2nd Edition, Addison-Wesley Publishing Co., Reading, MA (1995).
26. B. Gruschke, “Integrated Event Management: Event Correlation Using Dependency Graphs,” Proceedings of the 9th IFIP/IEEE International Workshop on Distributed Systems Operations and Management (1998).
27. J. F. Huard and A. A. Lazar, Fault Isolation Based on Decision-Theoretic Troubleshooting, Technical Report 442-96-08, Center for Telecommunications Research, Columbia University, New York (1996).
28. I. Katzela and M. Schwartz, “Fault Identification Schemes in Communication Networks,” Vol. 3, IEEE/ACM Transactions on Networking (1995).
29. C.-S. Hood and C. Ji, “Proactive Network Fault Detection,” Proceedings of IEEE INFOCOM, Kobe, Japan (April 7–12, 1997), pp. 1147–1155.