.png){kind=icon}
.png){kind=icon}
Return
Eventually lattice-linear algorithms
.png){kind=icon}
OA
AI
DOI：10.1016/j.jpdc.2023.104802.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Lattice-linear systems allow nodes to execute asynchronously. We introduce eventually lattice-linear algorithms, where lattices are induced only among the states in a subset of the state space. The algorithm guarantees that the system transitions to a state in one of the lattices. Then, the algorithm behaves lattice linearly while traversing to an optimal state through that lattice.We present a lattice-linear self-stabilizing algorithm for service demand based minimal dominating set (SDMDS) problem. Using this as an example, we elaborate the working of, and define, eventually lattice-linear algorithms. Then, we present eventually lattice-linear self-stabilizing algorithms for minimal vertex cover (MVC), maximal independent set (MIS), graph colouring (GC) and 2-dominating set problems (2DS).Algorithms for SDMDS, MVC and MIS converge in 1 round plus n moves (within 2n moves), GC in n + 4m moves, and 2DS in 1 round plus 2n moves (within 3nmoves). These results are an improvement over the existing literature. We also present experimental results to show performance gain demonstrating the benefit of lattice-linearity.
Keywords:
Eventually lattice-linear algorithms
Self-stabilization
Asynchrony
Concurrency
Eliminate synchronization cost
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
4
Papers:
3.8K
Citations:
4.8K