.png){kind=icon}
返回
Eventually lattice-linear algorithms
.png){kind=icon}
OA
AI
DOI：10.1016/j.jpdc.2023.104802.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
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.
Keyword:
Eventually lattice-linear algorithms
Self-stabilization
Asynchrony
Concurrency
Eliminate synchronization cost
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
4
论文数:
3.8K
被引数:
4.8K
机构
引用论文
.png){kind=icon}
A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs关于图中的独立性，支配，着色和匹配的自稳定算法的调查
PREAI
分享收藏分享收藏 没有更多内容
没有更多内容