# A Self-Stabilizing 1-Maximal Independent Set Algorithm

## Document Type

Article

## Publication Date

3-15-2021

## Publication Title

Journal of Information Processing

## Volume

29

## First page number:

247

## Last page number:

255

## Abstract

We consider the 1-maximal independent set (1-MIS) problem: given a graph G = (V, E), our goal is to find a 1-maximal independent set (1-MIS) of a given network G, that is, a maximal independent set (MIS) S ⊂ V of G such that S ∪ {v, w} \ {u} is not an independent set for any nodes u ∈ S, and v, w ∉ S (v ≠ w). We give a silent, self-stabilizing, and asynchronous distributed algorithm to construct a 1-MIS on a network of any topology. We assume the processes have unique identifiers and the scheduler is weakly-fair and distributed. The time complexity, i.e., the number of rounds to reach a legitimate configuration in the worst case of the proposed algorithm is O(nD), where n is the number of processes in the network and D is the diameter of the network. We use a composition technique called loop composition [Datta et al., 2017] to iterate the same procedure consistently, which results in a small space complexity, O(log n) bits per process.

## Keywords

1-maximal independent set; Distributed system; Loop composition; Self-stabilizing algorithm

## Disciplines

Computer Sciences

## Language

English

## Repository Citation

Tanaka, H.,
Sudo, Y.,
Kakugawa, H.,
Masuzawa, T.,
Datta, A.
(2021).
A Self-Stabilizing 1-Maximal Independent Set Algorithm.
*Journal of Information Processing, 29*
247-255.

http://dx.doi.org/10.2197/IPSJJIP.29.247