Gerando orientações acíclicas com algoritmos probabilísticos distribuídos
AUTOR(ES)
Arantes Jr, Gladstone M., França, Felipe M. G., Martinhon, Carlos A
FONTE
Pesquisa Operacional
DATA DE PUBLICAÇÃO
2005-12
RESUMO
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.
ASSUNTO(S)
algoritmos distribuídos probabilísticos quebra de simetria sistemas anônimos
Documentos Relacionados
- Algoritmos para eleição de lider em sistemas distribuidos
- Algoritmos distribuidos para localização de falhas e difusão de mensagens em hipercubos defeituosos
- Congelamento com abono salarial gerando excesso de demanda
- A hibridação com a tecnologia digital gerando linhas de fuga
- Estudo de algoritmos de controle de admissão em servidores Web distribuídos com QoS