Loosely-stabilizing maximal independent set algorithms with unreliable communications

Self-stabilization is a promising paradigm for designing highly adaptive distributed systems. However, it cannot be realized when the communication between processes is unreliable with some constant probability. To circumvent such impossibility, this paper adopts the concept of for the first time, which is a practical alternative of self-stabilization, and proposes three systematic approaches to realize loose-stabilization in the atomic-state model with , namely, the approach, the approach, and the approach. Further, we apply these approaches to design three corresponding loosely-stabilizing algorithms for the maximal independent set problem.