Geração Quase-Instantânea de Orientações Acíclicas em Sistemas Distribuídos Anônimos

Abstract

This paper discusses a set of non-deterministic distributed algorithms for the generation of acyclic orientations upon anonymous distributed systems of arbitrary topology. Although other practical applications of this form of symmetry breaking may be devised, we'll be focusing on the problem of priming a target system for Scheduling by Edge Reversal (SER), a simple and powerful distributed scheduling algorithm. SER requires an initial acyclic orientation on the graph representing the target resource sharing system in order to work correctly and such initial orientation determines an amount of "concurrency" associated to the scheduling dynamics. The set of algorithms is analysed both in terms of convergency time and in terms of the amount of concurency produced. In particular, a new algorithm called Alg-Arestas is proposed which, under appropriate conditions, is able to produce acyclic orientations quasi instantaneously, i.e., in less than two (2) steps.