A Distributed Algorithm for Topological Sorting

This paper presents a distributed algorithm for topological sorting of AOE networks on an asynchronous communication computational model.The key to design this algorithm is using a kind of dynamic spanning-tree structure.The results are that the proposed algorithm communication complexity is O（dm） and the time complexity is O（d²）,where d is the diameter of the network,m is the number of communication links and n is the number of processors （d<n）.