Distributed Self-Stabilizing MIS with Few States and Weak Communication

DOI10.1145/3583668.3594581arXiv2301.05059OpenAlexW4380881644WikidataQ130816717 ScholiaQ130816717MaRDI QIDQ6202267FDOQ6202267

Authors: George Giakkoupis, Isabella Ziccardi 

Publication date: 26 March 2024

Published in: Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Abstract: 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 inclusion into the MIS. The vertex states are arbitrary initially, and are updated in parallel: In each round, every vertex whose state is ``inconsistent with its neighbors', i.e., it is black and has a black neighbor, or it is white and all neighbors are white, changes its state with probability $1/2$. The process stabilizes with probability 1 on any graph, and the resulting set of black vertices is an MIS. It is also easy to see that the expected stabilization time is $O(logn)$ on certain graph families, such as cliques and trees. However, analyzing the process on graphs beyond these simple cases seems challenging. Our main result is that the process stabilizes in $mathrmpoly(logn)$ rounds w.h.p. on $G_{n,p}$ random graphs, for $0leqpleqmathrmpoly(logn)cdot{n}^{-1/2}$ and $pgeq1/mathrmpoly(logn)$. Further, an extension of this process, with larger but still constant vertex state space, stabilizes in $mathrmpoly(logn)$ rounds on $G_{n,p}$ w.h.p., for all $1leqpleq1$. We conjecture that this improved bound holds for the original process as well. In fact, we believe that the original process stabilizes in $mathrmpoly(logn)$ rounds on any given $n$-vertex graph w.h.p. Both processes readily translate into distributed/parallel MIS algorithms, which are self-stabilizing, use constant space (and constant random bits per round), and assume restricted communication as in the beeping or the synchronous stone age models. To the best of our knowledge, no previously known MIS algorithm is self-stabilizing, uses constant space and constant randomness, and stabilizes in $mathrmpoly(logn)$ rounds in general or random graphs.

Full work available at URL: https://arxiv.org/abs/2301.05059

zbMATH Keywords

maximal independent setself-stabilizing algorithmsbeeping modelparallel/distributed algorithms

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Cites Work

• Self-stabilization
• Self-stabilizing systems in spite of distributed control
• Decomposition of Finite Graphs Into Forests
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Deploying wireless networks with beeps
• Stone age distributed computing
• A biological solution to a fundamental distributed computing problem
• Linear self-stabilizing algorithms for the independent and dominating set problems using an unfair distributed scheduler
• An overview of computational complexity
• Self-stabilizing algorithms for minimal dominating sets and maximal independent sets
• Beeping a maximal independent set
• The Locality of Distributed Symmetry Breaking
• Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
• Lower Bounds for Maximal Matchings and Maximal Independent Sets
• Making randomized algorithms self-stabilizing
• Locally-iterative Distributed (Δ + 1)-coloring and Applications
• Distributed MIS via All-to-All Communication

Cited In (1)

• Luby's MIS algorithms made self-stabilizing

This page was built for publication: Distributed Self-Stabilizing MIS with Few States and Weak Communication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202267)