A Self-Stabilizing Algorithm for the Local (1,Ni)-Critical Section Problem with Safe Convergence

摘要

This paper considers the local (1,|N_i|)-critical section (abbr. CS) problem where Ni is the set of neighboring processes for each process P_i. It dynamically maintains two disjoint dominating sets, and is one of the generalizations of the mutual exclusion problem. The problem is one of controlling the system in such a way that, for each process, among its neighbors and itself, at least one process must be in the CS and at least one process must be out of the CS at each time. In this paper, a self-stabilizing distributed algorithm for the local (1,|N_i|)-CS problem with safe convergence is proposed. We assume that the feasible legitimate configuration satisfies the condition that a dominating set is constructed, and the optimal legitimate configuration satisfies the condition that two disjoint dominating sets are constructed and maintained dynamically. The convergence time to a feasible legitimate configuration is O(1) rounds, and the convergence time to an optimal legitimate configuration is O(n) rounds.