Algoritmo Branch-and-Bound Distribuído e Tolerante a Falhas para um Ambiente em Grade

Abstract

This work introduces a new fault tolerant anddistributed branch-and-bound algorithm, applied tothe Steiner Problem in Graphs (SPG), to be run oncomputational Grids. Many Grids are composed ofcluster of processors connected via high-speed linksand the clusters, geographically distant, are connectedthrough low-speed links, in a hierarchical fashion. Thealgorithm proposed has the following features: i) itdoes not employ the usual master-worker paradigm; ii)it considers the hierarchical structure of such Grids inits procedures; and iii) it contains load balance andfault tolerance mechanisms. Good speepuds wereobtained, allowing the resolution of hard instances invery reasonable times.