Distributed Self-Stabilizing MIS with Few States and Weak Communication

George Giakkoupis, Isabella Ziccardi

We study a simple random process that computes a maximal independent set (MIS) on a general $n$-vertex graph. Each vertex has a binary state, black or white, where black indicates…