Giakkoupis, GeorgeGeorgeGiakkoupisTurau, VolkerVolkerTurauZiccardi, IsabellaIsabellaZiccardi2024-11-262024-11-262024-08-13Information Processing Letters 188: 106531 (2025)https://tore.tuhh.de/handle/11420/52099We 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.en1872-61192024Elsevierhttps://creativecommons.org/licenses/by/4.0/Distributed computing | Fault tolerance | Maximal independent set (MIS) | Self-stabilizationComputer Science, Information and General Works::004: Computer SciencesJournal Articlehttps://doi.org/10.15480/882.1372310.1016/j.ipl.2024.10653110.15480/882.13723Journal Article