by Ivan Beschastnikh, Yuriy Brun, Michael D. Ernst, Arvind Krishnamurthy and 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.
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 Entry:
@article{Beschastnikh11osr,
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 = {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. 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},
}