Distributed maximal independent set computation driven by finite-state dynamics

Research output: Contribution to journalArticlepeer-review

Abstract

A Maximal Independent Set (MIS) is an inclusion maximal set of pairwise non-adjacent vertices. The computation of an MIS is one of the core problems in distributed computing. In this article, we introduce and analyze a finite-state distributed randomized algorithm for computing a Maximal Independent Set (MIS) on arbitrary undirected graphs. Our algorithm is self-stabilizing (reaches a correct output on any initial configuration) and can be implemented on systems with very scarce conditions. We analyze the convergence time of the proposed algorithm, showing that in many cases the algorithm converges in logarithmic time with high probability.

Original languageEnglish
Pages (from-to)85-97
Number of pages13
JournalInternational Journal of Parallel, Emergent and Distributed Systems
Volume38
Issue number1
DOIs
StatePublished - 2023
Externally publishedYes

Keywords

  • Maximal independent set
  • distributed algorithms
  • local algorithms
  • randomized algorithms

Fingerprint

Dive into the research topics of 'Distributed maximal independent set computation driven by finite-state dynamics'. Together they form a unique fingerprint.

Cite this