Brief announcement: Fully lattice linear algorithms

DOI10.1007/978-3-031-21017-4_24MaRDI QIDQ6155259zbMATH OpenFDO

Authors Arya Tanmay Gupta, Sandeep S. Kulkarni

Publication date 12 June 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

convergence timelattice linear algorithmslattice linear problemsminimal dominating setself-stabilization

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Abstract: This paper focuses on analyzing and differentiating between lattice linear problems and algorithms. It introduces a new class of algorithms called extit{(fully) lattice linear algorithms}. A property of these algorithms is that they induce a partial order among all states and form extit{multiple lattices}. An initial state locks in one of these lattices. We present a lattice linear self-stabilizing algorithm for minimal dominating set.

Recommendations

• Extending Lattice Linearity for Self-stabilizing Algorithms
• Brief Announcement
• A self-stabilizing algorithm for constructing weakly connected minimal dominating sets
• Self-stabilizing algorithms for minimal dominating sets and maximal independent sets
• Linear self-stabilizing algorithms for the independent and dominating set problems using an unfair distributed scheduler

Cites work

• A \(4n\)-move self-stabilizing algorithm for the minimal dominating set problem using an unfair distributed daemon
• Distributed Computing - IWDC 2003
• Extending Lattice Linearity for Self-stabilizing Algorithms

Cited in

(1)

• Tolerance to asynchrony in algorithms for multiplication and modulo

This page was built for publication: Brief announcement: Fully lattice linear algorithms

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