A self-stabilizing distributed algorithm for the Steiner tree problem
Self-stabilization is a theoretical framework of non-masking fault-tolerant distributed algorithms. In this paper, we investigate the Steiner tree problem in distributed systems, and propose a self-stabilizing heuristic solution to the problem. Our algorithm is constructed by four layered modules (sub-algorithms): construction of a shortest path forest, transformation of the network, construction of a minimum spanning tree, and pruning unnecessary links and processes. Competitiveness is 2(1 - 1/l), where l is the number of leaves of optimal solution.
distributed algorithm steiner tree problem fault-tolerant self-stabilizing algorithm fair composition