2021/09/27 by Arya Tanmay Gupta, Gupta, Arya Tanmay, Sandeep S. Kulkarni +2 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC) #cs.DC
paper · pdf · doi:10.48550/arxiv.2109.13216
openalex publication_date 2021/09/27 · arxiv created 2021/10/18 · arxiv updated 2021/10/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this article, we focus on extending the notion of lattice linearity to self-stabilizing programs. Lattice linearity allows a node to execute its actions with old information about the state of other nodes and still preserve correctness. It increases the concurrency of the program execution by eliminating the need for synchronization among its nodes. The extension -- denoted as eventually lattice linear algorithms -- is performed with an example of the service-demand based minimal dominating set (SDDS) problem, which is a generalization of the dominating set problem; it converges in 2n moves. Subsequently, we also show that the same approach could be used in various other problems including minimal vertex cover, maximal independent set and graph coloring.