Topological ordering algorithm for LDAG

Directed Acyclic Graph (DAG) is an important tool for workflow modeling and data provenance management. In these applications, DAG usually performs well. Yet for some workflow applications, except data or control dependencies between atomic tasks, there exists another requirement that each atomic task should be accomplished at an expected stage. Therefore, this paper proposes an improved DAG model – LDAG, in which each vertex has a level. Three cases of the level of vertices are discussed. For a reasonable one of these cases, this paper proposes a topological ordering algorithm and proves its correctness. In addition, it discusses the complexity of the algorithm and some other relevant problems.

► We propose an improved model, LDAG, for modeling some special workflow applications.
► We analyse three cases of the level of atomic tasks in LDAG.
► For a reasonable one of these cases, we propose a topological ordering algorithm.
► The algorithm consists of two phases, Level Adjusting and Topological Ordering.
► We prove the correctness of the algorithm.