Distributed maximal independent set computation driven by finite-state dynamics. Issue 1 (2nd January 2023)

• Record Type: Journal Article
• Authors: Goles, Eric; Leal, Laura; Montealegre, Pedro; Rapaport, Ivan; Ríos-Wilson, Martín
• Is Part Of: International journal of parallel, emergent and distributed systems. Volume 38:Issue 1(2023)
• Page Start: 85
• Page End: 97
• Publication Date: 2023-01-02
• Subjects: Maximal independent set -- local algorithms -- distributed algorithms -- randomized algorithms; Parallel computers -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Computer algorithms -- Periodicals; 004.35
• DOI: 10.1080/17445760.2022.2153248
• Languages: English
• ISSNs: 1744-5760

Abstract

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.