Mining temporal invariants from partially ordered logs

Download: PDF.

“Mining temporal invariants from partially ordered logs” by Ivan Beschastnikh, Yuriy Brun, Michael D. Ernst, Arvind Krishnamurthy, and Thomas E. Anderson. SIGOPS Operating Systems Review, vol. 45, no. 3, Dec. 2011, pp. 39-46.
A previous version appeared in SLAML 2011: Workshop on Managing Large-Scale Systems via the Analysis of System Logs and the Application of Machine Learning Techniques (SLAML '11), (Cascais, Portugal), Oct. 2011. Article No. 3.

Abstract

A common assumption made in log analysis research is that the underlying log is totally ordered. For concurrent systems, this assumption constrains the generated log to either exclude concurrency altogether, or to capture a particular interleaving of concurrent events. This paper argues that capturing concurrency as a partial order is useful and often indispensable for answering important questions about concurrent systems. To this end, we motivate a family of event ordering invariants over partially ordered event traces, give three algorithms for mining these invariants from logs, and evaluate their scalability on simulated distributed system logs.

Download: PDF.

BibTeX entry:

@article{BeschastnikhBEKA2011:OSR,
   author = {Ivan Beschastnikh and Yuriy Brun and Michael D. Ernst and
	Arvind Krishnamurthy and Thomas E. Anderson},
   title = {Mining temporal invariants from partially ordered logs},
   journal = {SIGOPS Operating Systems Review},
   volume = {45},
   number = {3},
   pages = {39--46},
   month = dec,
   year = {2011}
}

Back to Publications that describe invariant detection techniques in Daikon.