Eventually lattice-linear algorithms

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.

Automated summary

Lattice-linear systems allow nodes to execute asynchronously. The eventually lattice-linear algorithms introduced in this study guarantee system transitions to optimal states within specified moves, leading to improved performance compared to existing literature. Experimental results further support the benefits of lattice-linearity.