Root cause diagnosis in error-propagating networks

Various types of errors can propagate in networks, and they are usually hard to diagnose. For example, social networks spread rumors as well as useful information. Computer networks can spread Internet worms or malicious packets. In many cases, it is very hard to find the root cause (a.k.a. initial rumor spreader) of such errors without complete knowledge of the error propagation. We aim to find the root cause node when there is limited information about error propagation. We assume that there are very small number of monitor nodes in the network reporting whether error reached them or not. With this assumption, we first propose an algorithm that finds the most probable root cause node. Second, to improve the accuracy of root cause analysis, we propose another algorithm that makes use of timestamp of error reception. Finally, we study how to select monitors effectively so that root cause analysis can be accurate. With real networks from various domains, our algorithms are shown to be very effective.