Implementación de algoritmos distribuidos en Erlang para comunicaciones en redes de procesos

Abstract

El objetivo de este trabajo es implementar en Erlang algunos algoritmos distribuidos conocidos sobre grafos. Además implementamos un servidor genérico incorporando estos algoritmos. En concreto, hemos elegido dos algoritmos distribuidos existentes para el cómputo del árbol de recubrimiento, y otro para el árbol de recubrimiento mínimo. Después hemos desarrollado herramientas para la visualización de dichos árboles, y algoritmos de comunicación (broadcast y convergecast) entre los procesos del grafo, utilizando los árboles calculados para mejorar el rendimiento. Hemos desarrollado además una extensión de un comportamiento (behaviour) de Erlang para encapsular estos algoritmos. Como resultado obtenemos una implementación útil para resolver problemas reales en este área.

The aim of this work is to implement in Erlang some well-known distributed algorithms on graphs. In addition, we implement a generic server by including these algorithms. In particular, we have chosen two distributed algorithms for computing an spanning tree of a graph, and another one for computing its minimum spanning tree. Afterwards we have developed tools for displaying these trees, and two algorithms (convergecast and broadcast) for communicating the nodes of a graph, by using the previously computed trees, in order to improve performance. Besides this, We have developed an extension of an Erlang behaviour in order to encapsulate these algorithms. As a result, we have obtained an useful implementation that addresses actual problems in this area.