Self-stabilizing (f,g)-alliances with safe convergence

Given two functions f and g mapping nodes to non-negative integers, we give a silent self-stabilizing algorithm that computes a minimal ( f , g ) -alliance in an asynchronous network with unique node IDs, assuming that every node p has a degree at least g ( p ) and satisfies f ( p ) ? g ( p ) . Our algorithm is safely converging in the sense that starting from any configuration, it first converges to a (not necessarily minimal) ( f , g ) -alliance in at most four rounds, and then continues to converge to a minimal one in at most 5 n + 4 additional rounds, where n is the size of the network. Our algorithm is written in the shared memory model. It is proven assuming an unfair (distributed) daemon. Its memory requirement is ? ( log n ) bits per process, and it takes O ( n ? Δ 3 ) steps to stabilize, where Δ is the degree of the network. We give an algorithm for the ( f , g ) -alliance, a generalization of several problems.Our algorithm is distributed, self-stabilizing, silent, and safe converging.The complexity analysis shows that it is better than many other related solutions.