Luby's MIS algorithms made self-stabilizing

We reconsider two well-known distributed randomized algorithms computing a maximal independent set, proposed in the seminal work of Luby (1986). We enhance these algorithms such that they become self-stabilizing without sacrificing their run-time, i.e., both stabilize in O(log⁡n) synchronous rounds with high probability on any n-node graph. The first algorithm gets along with three states, but needs to know an upper bound on the maximum degree. The second does not need any information about the graph, but uses a number of states that is linear in the node degree. Both algorithms use messages of logarithmic size.

Subjects

Distributed computing | Fault tolerance | Maximal independent set (MIS) | Self-stabilization

DDC Class

004: Computer Sciences

Funding(s)

Projekt DEAL

Lizenz

https://creativecommons.org/licenses/by/4.0/

Name

1-s2.0-S0020019024000619-main.pdf

Type

Main Article

Size

489.89 KB

Format

Adobe PDF

Options

Luby's MIS algorithms made self-stabilizing