Generating non-cycle orientations with distributed probabilistic algorithms

This paper presents a new randomized distributed algorithm for the generation of acyclic orientations upon anonymous distributed systems of arbitrary topology. This algorithm is analyzed in terms of correctness and complexity as well as its convergence rate. In particular, it is shown that this new algorithm, called Alg-Arestas, is able to produce, with high probability, acyclic orientations quasi instantaneously, i.e., in less than two steps. Two applications of this form of symmetry breaking will be discussed: (i) initialization of Scheduling by Edge Reversal (SER), a simple and powerful distributed scheduling algorithm, and (ii) a strategy for distributed uploading in computer networks.