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.

Authors

Institutions

Publication Details

Journal
Information Processing Letters
Published
2024-08-13
DOI
https://doi.org/10.1016/j.ipl.2024.106531
Citations
2
Primary Topic
Complexity and Algorithms in Graphs
Type
article
Field-Weighted Citation Impact
0.72

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Luby's MIS algorithms made self-stabilizing

George Giakkoupis, Isabella Ziccardi, Volker Turau
2 citations
Information Processing Letters
Complexity and Algorithms in Graphs
0.72
article

Luby's MIS algorithms made self-stabilizing

George Giakkoupis, Isabella Ziccardi, Volker Turau
article en
2 citations

Abstract

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.

Information Processing LettersVol. 188
Centre National de la Recherche Scientifique (FR), Universität Hamburg (DE), Institut de Recherche en Informatique et Systèmes Aléatoires (FR), Université de Rennes (FR), Bocconi University (IT), Hamburg University of Technology (DE)
Agence Nationale de la Recherche, European Research Council, Horizon 2020, H2020 European Research Council
Openalex Percentile: Top 27%
Complexity and Algorithms in Graphs
0.72
DOIOpen Access PDFOpenAlex
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Luby's MIS algorithms made self-stabilizing — George Giakkoupis, Isabella Ziccardi, et al. · Information Processing Letters (2024) | TGRS Research Map | TGRS