Gerando orientações acíclicas com algoritmos probabilísticos distribuídos

Pesquisa Operacional

Gladstone M. Arantes Jr²  Felipe M. G. França²  Carlos A Martinhon¹ 

[1] ,Universidade Federal do Rio de Janeiro Eng. de Sistemas e Computação Rio de Janeiro RJ

关键词: algoritmos distribuídos probabilísticos;    quebra de simetria;    sistemas anônimos;    randomized distributed algorithms;    symmetry breaking;    anonymous systems;   

DOI  :  10.1590/S0101-74382005000300001

来源: SciELO

【 摘 要 】

Este artigo apresenta um novo algoritmo distribuído probabilístico para a geração de orientações acíclicas em um sistema distribuído anônimo de topologia arbitrária. O algoritmo é analisado tanto em termos de correção e complexidade esperada quanto velocidade de convergência. Em particular, é demonstrado que este novo algoritmo, chamado Alg-Arestas, é capaz de produzir, com alta probabilidade, orientações acíclicas quase instantaneamente, isto é, em menos de dois passos. Duas aplicações para essa forma de quebra de simetria serão discutidas: (i) inicialização do Escalonamento por Reversão de Arestas (ERA), um simples e poderoso algoritmo de escalonamento distribuído, e (ii) uma estratégia de distribuição de uploads em redes de computadores.

【 授权许可】

CC BY   
 All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License