An algorithm for parallel topological sorting on distributed memory machines parallelizes the algorithm of Kahn for a DAG formula_2. On a high level, the algorithm of Kahn repeatedly removes the vertices of indegree 0 and adds them to the topological sorting in the order in which they were removed. Since the outgoing edges of the removed vertices are also removed, there will be a new set of vertices of indegree 0, where the procedure is repeated until no vertices are left. This algorithm performs formula_3 iterations, where is the longest path in . Each iteration can be parallelized, which is the idea of the following algorithm.