Efficient and Scalable Algorithms for Inferring Likely Invariants in Distributed Systems
Authors:
- Guofei JiangGJGuofei Jiang
- Haifeng ChenHCHaifeng Chen
- Kenji YoshihiraKYKenji Yoshihira
- 8 October 2007
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 19 (11) , 1508-1523
Abstract
Distributed systems generate a large amount of monitoring data such as log files to track their operational status. However, it is hard to correlate such monitoring data effectively across distributed systems and along observation time for system management. In previous work, we proposed a concept named flow intensity to measure the intensity with which internal monitoring data reacts to the volume of user requests. We calculated flow intensity measurements from monitoring data and proposed an algorithm to automatically search constant relationships between flow intensities measured at various points across distributed systems. If such relationships hold all the time, we regard them as invariants of the underlying systems. Invariants can be used to characterize complex systems and support various system management tasks. However, the computational complexity of the previous invariant search algorithm is high so that it may not scale well in large systems with thousands of measurements. In this paper, we propose two efficient but approximate algorithms for inferring invariants in large-scale systems. The computational complexity of new randomized algorithms is significantly reduced, and experimental results from a real system are also included to demonstrate the accuracy and efficiency of our new algorithms.Keywords
This publication has 18 references indexed in Scilit:
- Modeling and Tracking of Transaction Flow Dynamics for Fault Detection in Complex SystemsIEEE Transactions on Dependable and Secure Computing, 2006
- Discovering Likely Invariants of Distributed Transaction Systems for Autonomic System Management2006
- Tracking Probabilistic Correlation of Monitoring Data for Fault Detection in Complex Systems2006
- Efficient incremental algorithms for dynamic detection of likely invariants2004
- Discovering Web access patterns and trends by applying OLAP and data mining technology on Web logs2002
- Tracking down software bugs using automatic anomaly detection2002
- Mining web logs for prediction models in WWW caching and prefetching2001
- Improving the Effectiveness of a Web Site with Web Usage Mining2000
- Web usage miningACM SIGKDD Explorations Newsletter, 2000
- Trends in the application of model-based fault detection and diagnosis of technical processesControl Engineering Practice, 1997