Premium
A self‐stabilizing distributed algorithm for the local ( 1 , | N i | ) ‐critical section problem
Author(s) -
Kamei Sayaka,
Kakugawa Hirotsugu
Publication year - 2019
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.5628
Subject(s) - daemon , disjoint sets , mutual exclusion , self stabilization , critical section , mathematics , combinatorics , discrete mathematics , distributed algorithm , computer science , algorithm , theoretical computer science , distributed computing , computer network
Summary We consider the local (1,| N i |)‐critical section (CS) problem where N i 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. That is, in the system G =( V , E ), there are always two disjoint dominating sets A 1 (⊂ V ) and A 2 (= V \ A 1 ) and each process alternates between its rule A 1 and A 2 infinitely. It is useful for sleep scheduling or cluster head scheduling in sensor networks. In this paper, first, we show the necessary and sufficient conditions to solve the problem without any deadlock detection. To discuss the conditions, we consider an inefficient (costly) self‐stabilizing algorithm for the local (1,| N i |)‐CS problem. After that, an efficient self‐stabilizing algorithm for the local (1,| N i |)‐CS problem is proposed under an additional assumption that the graph does not have a special matching, which we call unpreventable colorable maximal matching. The convergence time of the proposed algorithm is O ( n ) rounds under the weakly fair distributed daemon.