Distributed computation of the critical path from execution traces
Open Access
- 3 May 2023
- journal article
- research article
- Published by Wiley in Software: Practice and Experience
- Vol. 53 (8) , 1722-1737
Abstract
Due to the ever‐increasing number of computer nodes in distributed systems, efficient and effective tools have become crucial for their analysis. Although several efficient methods have been proposed to monitor and profile distributed systems, tracing remains the most effective solution for in‐depth system analysis. Tracing is the act of collecting a trace, which is a sequence of low‐level events generated by the kernel or the userspace. After data collection, the most important part is the event analysis. The paradigm and choice of graphs determine the ability of the user to detect abnormal behaviors and identify their root cause. Although tracing is a highly effective approach to analyzing complex systems, the scalability of the current analysis tools is limited. As a consequence, tracing is often impractical for large distributed systems. This paper identifies the shortcomings of the current approaches, most notably the critical path computation and the trace file transfer between nodes. Then, this paper proposes new solutions to these drawbacks, most notably a distributed algorithm to compute the critical path, that does not aggregate all traces in a single node, and an efficient architecture to perform tracing on distributed systems. These new solutions are made publically available.Keywords
Funding Information
- Advanced Micro Devices
- Telefonaktiebolaget LM Ericsson
- Natural Sciences and Engineering Research Council of Canada
This publication has 24 references indexed in Scilit:
- Efficient Model to Query and Visualize the System States Extracted from Trace Data2013
- Accurate offline synchronization of distributed traces using kernel-level eventsACM SIGOPS Operating Systems Review, 2010
- A practical scalable distributed B-treeProceedings of the VLDB Endowment, 2008
- MOM vs. RPC: communication models for distributed applicationsIEEE Internet Computing, 2005
- Where is is middlewareIEEE Internet Computing, 2002
- Critical path analysis in the network with fuzzy activity timesFuzzy Sets and Systems, 2001
- Critical path analysis of TCP transactionsACM SIGCOMM Computer Communication Review, 2001
- From Trace Generation to Visualization: A Performance Framework for Distributed Parallel Systems2000
- Critical path in an activity network with time constraintsEuropean Journal of Operational Research, 1997
- Critical path analysis and resource constrained project scheduling — Theory and practiceEuropean Journal of Operational Research, 1985