Exposing complex bug-triggering conditions in distributed systems via graph mining

Eunsoo Seo, Mohammad Maifi Hasan Khan, Prasant Mohapatra, Jiawei Han, Tarek Abdelzaher

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Software bugs in distributed systems are notoriously hard to find due to the large number of components involved and the non-determinism introduced by race conditions between messages. This paper introduces PopMine, a tool for diagnosing corner-case bugs by finding the minimal causal directed acyclic graph (DAG) of events, spanning multiple processes, which captures a bug-triggering condition. Being based on causal order, a global notion of time is not required in uncovering bugtriggering distributed event patterns. Bug triggering event DAGs can be identified by comparing execution graphs from successful runs to those where bug manifestations were observed, and exposing the minimal discriminative event DAGs that may be responsible for the problem. This is a significant extension to prior debugging tools, in that prior work considered much simpler bug-triggering conditions such as single events, event sets, or ordered chains of events. To the authors' knowledge, this is the first paper that considers bug-triggering conditions in the form of distributed event graphs. To prove the effectiveness of our approach, we applied our tool to VCP, Chord and GreenGPS and diagnosed bugs. We also present performance analysis results to demonstrate the scalability of our approach.

Original languageEnglish (US)
Title of host publicationProceedings - 2011 International Conference on Parallel Processing, ICPP 2011
Pages186-195
Number of pages10
DOIs
StatePublished - 2011
Event40th International Conference on Parallel Processing, ICPP 2011 - Taipei City, Taiwan, Province of China
Duration: Sep 13 2011Sep 16 2011

Publication series

NameProceedings of the International Conference on Parallel Processing
ISSN (Print)0190-3918

Other

Other40th International Conference on Parallel Processing, ICPP 2011
Country/TerritoryTaiwan, Province of China
CityTaipei City
Period9/13/119/16/11

Keywords

  • Data mining
  • Fault diagnosis
  • Software debugging

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Exposing complex bug-triggering conditions in distributed systems via graph mining'. Together they form a unique fingerprint.

Cite this