A self-stabilizing 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 solution to the problem. Our solution is based on the pruned-MST technique, a heuristic technique to find a minimal cost Steiner tree by pruning unnecessary nodes and edges in a minimum cost spanning tree, provided that a minimum spanning tree is available. Finally we propose an algorithm to reduce the cost of the solution.