Distributed Acyclic Orientation of Asynchronous Anonymous Networks

A very simple randomised distributed algorithm imposing an acyclic orientation on any arbitrary anonymous asynchronous network is presented in this paper. The problem is faced under the noinfo assumption: no network attribute is available and when the algorithm starts each processor only knows the number of its input/output ports (i.e. the number of its immediate neighbours). The presented algorithm terminates explicitly (process termination) in O(logn)-time on a non complete graph only exchanging messages of constant size among immediate neighbours (i.e. nodes connected through a direct link).