Algoritmo distribuído detector de ciclos baseado em busca e difusão

Abstract

O presente trabalho tem como objetivo principal a modelagem de um algoritmo distribuído baseado em busca e difusão para detectar ciclos simples em uma rede de topologia qualquer. Existem, na literatura, uma série de algoritmos de busca em grafos. De acordo com o tipo de estrutura utilizada para armazenamento, a ordem em que o grafo é percorrido é alterada, caracterizando um tipo de busca com aplicações diferentes. Trabalhos prévios definem, em geral, métodos cujo objetivo é a descoberta de rotas acíclicas, caracterizada por cobrir todos os nodos de uma rede conexa, através da formação de uma spanning tree do grafo. Inversamente, este trabalho centra-se na modelagem de um algoritmo distribuído capaz de capturar rotas cíclicas a partir de nodos previamente escolhidos. Para tanto, um modelo simples de difusão, com busca exaustiva de caminhos, é utilizado sobre uma rede, devidamente abstraída por meio de um dígrafo.

The main goal of this paper is the modelling of a distributed algorithm based in search and diffusion computations in order to detect cycles in any network topology. There are, in the literature, many graph-search algorithms. Each storage structure defines a order in which the graph is traversed and different applications of this search. Previous works define, in general, methods whose goal is the discovery of acyclic routes, carachterized by covering all nodes of a connected network by discovering a spanning tree of the graph. Instead of it, this paper is centered in the modelling of a distributed algorithm able to detect cyclic routes starting of initial nodes previously chosen. In order to perform it, a simple diffusing computation model that searches exaustively paths is utilized in a network, properly represented by a digraph.