Distributed Self-Stabilizing MIS with Few States and Weak Communication

DOI10.1145/3583668.3594581arXiv2301.05059OpenAlexW4380881644WikidataQ130816717 ScholiaQ130816717MaRDI QIDQ6202267

Isabella Ziccardi, George Giakkoupis

Publication date: 26 March 2024

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

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 systems (68M14) Distributed algorithms (68W15)

Cites Work

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

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