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

• We give an algorithm for the (f,g)(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.

Given two functions ff and gg mapping nodes to non-negative integers, we give a silent self-stabilizing algorithm that computes a minimal (f,g)(f,g)-alliance in an asynchronous network with unique node IDs, assuming that every node pp has a degree at least g(p)g(p) and satisfies f(p)≥g(p)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)(f,g)-alliance in at most four rounds, and then continues to converge to a minimal one in at most 5n+45n+4 additional rounds, where nn 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 Θ(logn)Θ(logn) bits per process, and it takes O(n⋅Δ3)O(n⋅Δ3) steps to stabilize, where ΔΔ is the degree of the network.