Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLCL problems on grids
65
0
0.0
(
0
)
Added by
Janne H. Korhonen
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
LCLs or locally checkable labelling problems (e.g. maximal independent set, maximal matching, and vertex colouring) in the LOCAL model of computation are very well-understood in cycles (toroidal 1-dimensional grids): every problem has a complexity of $O(1)$, $Theta(log^* n)$, or $Theta(n)$, and the design of optimal algorithms can be fully automated. This work develops the complexity theory of LCL problems for toroidal 2-dimensional grids. The complexity classes are the same as in the 1-dimensional case: $O(1)$, $Theta(log^* n)$, and $Theta(n)$. However, given an LCL problem it is undecidable whether its complexity is $Theta(log^* n)$ or $Theta(n)$ in 2-dimensional grids. Nevertheless, if we correctly guess that the complexity of a problem is $Theta(log^* n)$, we can completely automate the design of optimal algorithms. For any problem we can find an algorithm that is of a normal form $A circ S_k$, where $A$ is a finite function, $S_k$ is an algorithm for finding a maximal independent set in $k$th power of the grid, and $k$ is a constant. Finally, partially with the help of automated design tools, we classify the complexity of several concrete LCL problems related to colourings and orientations.
rate research
Read More
We present a complete classification of the deterministic distributed time complexity for a family of graph problems: binary labeling problems in trees. These are locally checkable problems that can be encoded with an alphabet of size two in the edge labeling formalism. Examples of binary labeling problems include sinkless orientation, sinkless and sourceless orientation, 2-vertex coloring, perfect matching, and the task of coloring edges red and blue such that all nodes are incident to at least one red and at least one blue edge. More generally, we can encode e.g. any cardinality constraints on indegrees and outdegrees. We study the deterministic time complexity of solving a given binary labeling problem in trees, in the usual LOCAL model of distributed computing. We show that the complexity of any such problem is in one of the following classes: $O(1)$, $Theta(log n)$, $Theta(n)$, or unsolvable. In particular, a problem that can be represented in the binary labeling formalism cannot have time complexity $Theta(log^* n)$, and hence we know that e.g. any encoding of maximal matchings has to use at least three labels (which is tight). Furthermore, given the description of any binary labeling problem, we can easily determine in which of the four classes it is and what is an asymptotically optimal algorithm for solving it. Hence the distributed time complexity of binary labeling problems is decidable, not only in principle, but also in practice: there is a simple and efficient algorithm that takes the description of a binary labeling problem and outputs its distributed time complexity.
Determining the space complexity of $x$-obstruction-free $k$-set agreement for $xleq k$ is an open problem. In $x$-obstruction-free protocols, processes are required to return in executions where at most $x$ processes take steps. The best known upper bound on the number of registers needed to solve this problem among $n>k$ processes is $n-k+x$ registers. No general lower bound better than $2$ was known. We prove that any $x$-obstruction-free protocol solving $k$-set agreement among $n>k$ processes uses at least $lfloor(n-x)/(k+1-x)rfloor+1$ registers. Our main tool is a simulation that serves as a reduction from the impossibility of deterministic wait-free $k$-set agreement: if a protocol uses fewer registers, then it is possible for $k+1$ processes to simulate the protocol and deterministically solve $k$-set agreement in a wait-free manner, which is impossible. A critical component of the simulation is the ability of simulating processes to revise the past of simulated processes. We introduce a new augmented snapshot object, which facilitates this. We also prove that any space lower bound on the number of registers used by obstruction-free protocols applies to protocols that satisfy nondeterministic solo termination. Hence, our lower bound of $lfloor(n-1)/krfloor+1$ for the obstruction-free ($x=1$) case also holds for randomized wait-free free protocols. In particular, this gives a tight lower bound of exactly $n$ registers for solving obstruction-free and randomized wait-free consensus. Finally, our new techniques can be applied to get a space lower of $lfloor n/2rfloor+1$ for $epsilon$-approximate agreement, for sufficiently small $epsilon$. It requires participating processes to return values within $epsilon$ of each other. The best known upper bounds are $lceillog(1/epsilon)rceil$ and $n$, while no general lower bounds were known.
In this work we introduce the graph-theoretic notion of mendability: for each locally checkable graph problem we can define its mending radius, which captures the idea of how far one needs to modify a partial solution in order to patch a hole. We explore how mendability is connected to the existence of efficient algorithms, especially in distributed, parallel, and fault-tolerant settings. It is easy to see that $O(1)$-mendable problems are also solvable in $O(log^* n)$ rounds in the LOCAL model of distributed computing. One of the surprises is that in paths and cycles, a converse also holds in the following sense: if a problem $Pi$ can be solved in $O(log^* n)$, there is always a restriction $Pi subseteq Pi$ that is still efficiently solvable but that is also $O(1)$-mendable. We also explore the structure of the landscape of mendability. For example, we show that in trees, the mending radius of any locally checkable problem is $O(1)$, $Theta(log n)$, or $Theta(n)$, while in general graphs the structure is much more diverse.
The locality of a graph problem is the smallest distance $T$ such that each node can choose its own part of the solution based on its radius-$T$ neighborhood. In many settings, a graph problem can be solved efficiently with a distributed or parallel algorithm if and only if it has a small locality. In this work we seek to automate the study of solvability and locality: given the description of a graph problem $Pi$, we would like to determine if $Pi$ is solvable and what is the asymptotic locality of $Pi$ as a function of the size of the graph. Put otherwise, we seek to automatically synthesize efficient distributed and parallel algorithms for solving $Pi$. We focus on locally checkable graph problems; these are problems in which a solution is globally feasible if it looks feasible in all constant-radius neighborhoods. Prior work on such problems has brought primarily bad news: questions related to locality are undecidable in general, and even if we focus on the case of labeled paths and cycles, determining locality is $mathsf{PSPACE}$-hard (Balliu et al., PODC 2019). We complement prior negative results with efficient algorithms for the cases of unlabeled paths and cycles and, as an extension, for rooted trees. We introduce a new automata-theoretic perspective for studying locally checkable graph problems. We represent a locally checkable problem $Pi$ as a nondeterministic finite automaton $mathcal{M}$ over a unary alphabet. We identify polynomial-time-computable properties of the automaton $mathcal{M}$ that near-completely capture the solvability and locality of $Pi$ in cycles and paths, with the exception of one specific case that is $mbox{co-$mathsf{NP}$}$-complete.
Machine scheduling problems are a long-time key domain of algorithms and complexity research. A novel approach to machine scheduling problems are fixed-parameter algorithms. To stimulate this thriving research direction, we propose 15 open questions in this area whose resolution we expect to lead to the discovery of new approaches and techniques both in scheduling and parameterized complexity theory.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
