1Strategies for Problem Determination using Probing

Abstract—As distributed systems continue to grow in size and complexity, scalable and cost-efficient techniques are needed for performing tasks such as problem determination and fault diagnosis. In this paper, we address these tasks using probes, or test transactions, which replace traditional “passive ” event-correlation techniques with a more active, real-time information-gathering approach. We provide a the-oretical foundation and a set of practical techniques for im-plementing efficient probing strategies- the main issue is minimizing the cost of probing while maximizing the diag-nostic accuracy of the probe set. We show that finding an optimal probe set is NP-hard and devise polynomial-time ap-proximation algorithms that demonstrate excellent empirical performance, even on large networks. We also implement an active, on-line probing strategy that yields a significant re-duction in the probe set size. I