over the sizes of . So each step, there are vertices added to the topological sorting. In the first step, PE assigns the indices to the local vertices in . These vertices in are removed, together with their corresponding outgoing edges. For each outgoing edge with endpoint in another PE , the message is posted to PE . After all vertices in are removed, the posted messages are sent to their corresponding PE. Each message received updates the indegree of the local vertex . If the indegree drops to zero, is added to . Then the next iteration starts. In step , PE assigns the indices , where is the total amount of processed vertices after step . This procedure repeats until there are no vertices left to process, hence . Below is a high level, single program, multiple data pseudo code overview of this algorithm. Note that the prefix sum for the local offsets can be efficiently calculated in parallel. p processing elements with IDs from 0 to p-1 Input: G = (V, E) DAG, distributed to PEs, PE index j = 0, ..., p - 1 Output: topological sorting of G function traverseDAGDistributed δ incoming degree of local vertices V // All vertices with indegree 0 nrOfVerticesProcessed = 0 do global build prefix sum over size of Q // get offsets and total amount of vertices in this step offset = nrOfVerticesProcessed + sum(Qi, i = 0 to j - 1) // j is the processor index foreach u in Q localOrder[u] = index++; foreach (u,v) in E do post message (u, v) to PE owning vertex v nrOfVerticesProcessed += sum(|Qi|, i = 0 to p - 1) deliver all messages to neighbors of vertices in Q receive messages for local vertices V remove all vertices in Q foreach message (u, v) received: if --δ[v] = 0 add v to Q while global size of Q > 0 return localOrder The communication cost depends heavily on the given graph partition. As for runtime, on a CRCW-PRAM model that allows fetch-and-decrement in constant time, this algorithm runs in , where is again the longest path in and the maximum degree. Application to shortest path finding The topological ordering can also be used to quickly compute shortest paths through a weighted directed acyclic graph. Let be the list of vertices in such a graph, in topological order. Then the following