On anomalies correction in reconstruction graphs of Linux process trees

The paper discusses an example of the Linux process tree on which the use of greedy reconstruction algorithms gives anomalous results. Analysis of dependencies between states of processes in the reconstruction graph is performed. Then the violation of semilattice ordering by dependencies in the resulting graphs is concluded. Corrections in to the original methods for constructing a reconstruction graph by copying states with target attributes are proposed, the complexity of the obtained corrections is analyzed. We give estimates of the growth of a set of intermediate states for the process group and session attributes using both the original and corrected methods for constructing a reconstruction graph. The estimation of the computational complexity depending on the vertices number in the input process tree is given as well.