Search

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, MVCc 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 $3n$ moves). These results are an improvement over the existing literature. We also present experimental results to show performance gain demonstrating the benefit of lattice-linearity., Comment: arXiv admin note: text overlap with arXiv:2109.13216

Consider the execution of a sequential algorithm that requires the program to converge to an optimal state, and then terminate/stutter. To design such an algorithm, we need to ensure that the state space that it traverses forms a directed acyclic graph (DAG) and its sink nodes are optimal states. However, if we run the same algorithm on multiple computing nodes running in parallel, and without synchronization, it may not reach an optimal state. In most parallel processing algorithms designed in the literature, a synchronization primitive is assumed. Synchronization ensures that the nodes read fresh value, and the execution proceeds systematically, such that the subject algorithm traverses a DAG induced among the global states. With this observation, we investigate the conditions that guarantee that the execution of an algorithm is correct even if it is executed in parallel and without synchronization. To this end, we introduce DAG-inducing problems and DAG-inducing algorithms. We show that induction of a $\prec$-DAG (induced among the global states -- that forms as a result of a partial order induced among the local states visited by individual nodes) is a necessary and sufficient condition to allow an algorithm to run in asynchrony. In the paper, we first give a comprehensive description of DAG-inducing problems and DAG-inducing algorithms, along with some simple examples. Then we show some properties of an algorithm that is tolerant to asynchrony, which include the above-mentioned condition.

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

A procedure called \textit{graph burning} was introduced to facilitate the modelling of spread of an alarm, a social contagion, or a social influence or emotion on graphs and networks. Graph burning runs on discrete time-steps (or rounds). At each step $t$, first (a) an unburned vertex is burned (as a \textit{fire source}) from "outside", and then (b) the fire spreads to vertices adjacent to the vertices which are burned till step $t-1$. This process stops after all the vertices of $G$ have been burned. The aim is to burn all the vertices in a given graph in minimum time-steps. The least number of time-steps required to burn a graph is called its \textit{burning number}. The less the burning number is, the faster a graph can be burned. Burning a general graph optimally is an NP-Complete problem. It has been proved that optimal burning of path forests, spider graphs, and trees with maximum degree three is NP-Complete. We study the \textit{graph burning problem} on several sub-classes of \textit{geometric graphs}. We show that burning interval graphs (Section 7.1, Theorem 7.1), permutation graphs (Section 7.2, Theorem 7.2) and disk graphs (Section 7.3, Theorem 7.3) optimally is NP-Complete. In addition, we opine that optimal burning of general graphs (Section 9.2, Conjecture 9.1) cannot be approximated better than 3-approximation factor., Comment: Masters' dissertation

Graph burning runs on discrete time steps. The aim is to burn all the vertices in a given graph in the least number of time steps. This number is known to be the burning number of the graph. The spread of social influence, an alarm, or a social contagion can be modeled using graph burning. The less the burning number, the faster the spread. Optimal burning of general graphs is NP-Hard. There is a 3-approximation algorithm to burn general graphs where as better approximation factors are there for many sub classes. Here we study burning of grids; provide a lower bound for burning arbitrary grids and a 2-approximation algorithm for burning square grids. On the other hand, burning path forests, spider graphs, and trees with maximum degree three is already known to be NP-Complete. In this article we show burning problem to be NP-Complete on connected interval graphs, permutation graphs and several other geometric graph classes as corollaries., Comment: 17 pages, 5 figures