A self-stabilizing distributed algorithm for the 1-MIS problem under the distance-3 model

Fault-tolerance and self-organization are critical properties in modern distributed systems. Self-stabilization is a class of fault-tolerant distributed algorithms which has the ability to recover from any kind and any finite number of transient faults and topology changes. In this article, we propose a self-stabilizing distributed algorithm for the 1-MIS problem under the unfair central daemon assuming the distance-3 model. Here, in the distance-3 model, each process can refer to the values of local variables of processes within three hops. Intuitively speaking, the 1-MIS problem is a variant of the maximal independent set (MIS) problem with improved local optimizations. The time complexity (convergence time) of our algorithm is O(n)$$ O(n) $$ steps and the space complexity is O(logn)$$ O\left(\log n\right) $$ bits, where n$$ n $$ is the number of processes. Finally, we extend the notion of 1-MIS to p$$ p $$-MIS for each nonnegative integer p$$ p $$, and compare the set sizes of p$$ p $$-MIS (p=0,1,2,& mldr;$$ p=0,1,2,\dots $$) and the maximum independent set.