Mining temporal invariants from partially ordered logs
by Ivan Beschastnikh, Yuriy Brun, Michael D. Ernst, Arvind Krishnamurthy, Thomas E. Anderson
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.
View PDF
Citation:
Ivan Beschastnikh, Yuriy Brun, Michael D. Ernst, Arvind Krishnamurthy, and Thomas E. Anderson, Mining temporal invariants from partially ordered logs, ACM SIGOPS Operating Systems Review, vol. 45, no. 3, December 2011, pp. 39–46.
Related:
A previous version appeared in the Proceedings of the Workshop on Managing Systems via Log Analysis and Machine Learning Techniques (SLAML), 2011.
Bibtex:
@article{Beschastnikh11osr,
  author = {Ivan Beschastnikh and Yuriy Brun and Michael D. Ernst and Arvind
  Krishnamurthy and Thomas E. Anderson},
  title =
  {\href{http://people.cs.umass.edu/brun/pubs/pubs/Beschastnikh11osr.pdf}{Mining
  temporal invariants from partially ordered logs}},
  journal = {ACM SIGOPS Operating Systems Review},
  venue = {SIGOSP},
  volume = {45},
  number = {3},
  month = {December},
  year = {2011},
  issn = {0163-5980},
  pages = {39--46},
  doi = {10.1145/2094091.2094101},

  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.},

  note = {A previous version appeared in the Proceedings of the Workshop on
  Managing Systems via Log Analysis and Machine Learning Techniques
  (SLAML), 2011. \href{https://doi.org/10.1145/2094091.2094101}{DOI:
  10.1145/2094091.2094101}},

  previous = {A previous version appeared in the Proceedings of the Workshop on
  Managing Systems via Log Analysis and Machine Learning Techniques (SLAML),
  2011.},

  fundedBy = {NSF CNS-0937060 to the CRA for the CIFellows Project, NSF CNS-0963754},
}