Trilhas, Otimização de Concorrência e Inicialização Probabilística em Sistemas Sob Reversão de Arestas

O Escalonamento por Reversão de Arestas (ERA) é um algoritmo de escalonamento para sistemas distribuídos com compartilhamento de recursos em alta carga. Este trabalho prova que os problemas de decisão relacionados à maximização e à minimização da concorrência do ERA são NP-completos para grafos com grau máximo menor ou igual a 4 e para grafos cúbicos planares, respectivamente. Também é provado que o problema de minimização do inverso da concorrência não é aproximável, se P é diferente de NP, por um fator igual ao do problema de coloração. Com o conceito de trilha, é provado que os ciclos principais determinam o máximo e o mínimo intervalo inoperante, além de outros atributos da execução do ERA. Sobre os algoritmos probabilísticos de inicialização do ERA, prova-se que Alg-Cor tem convergência sub-exponencial, para grafos completos, e linear, quando usa-se o número de faces do dado igual ao número de nós do grafo. Para Alg-Arestas, são analisadas expressões para P[T(m)>=u(m)+w] e P[T(m)=w], onde T(m) é o tempo de convergência do algoritmo em um grafo de m arestas, w é um inteiro positivo qualquer e u(m) é o tempo esperado de convergência do algoritmo.