Root cause diagnosis in error-propagating networks

Eunsoo Seo, Gulustan Dogan, Tarek Abdelzaher, Theodore Brown

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)1297-1308
Number of pages12
JournalSecurity and Communication Networks
Issue number11
StatePublished - Jul 25 2016


  • distributed systems
  • error classification
  • error propagation
  • error-propagating networks
  • root cause diagnosis

ASJC Scopus subject areas

  • Information Systems
  • Computer Networks and Communications


Dive into the research topics of 'Root cause diagnosis in error-propagating networks'. Together they form a unique fingerprint.

Cite this