
The degree splitting problem requires coloring the edges of a graph red or
blue such that each node has almost the same number of edges in each color, up
to a small additive discrepancy. The directed variant of the problem requires
orienting the edges such that each node has almost the same number of incoming
and outgoing edges, again up to a small additive discrepancy.
We present deterministic distributed algorithms for both variants, which
improve on their counterparts presented by Ghaffari and Su [SODA'17]: our
algorithms are significantly simpler and faster, and have a much smaller
discrepancy. This also leads to a faster and simpler deterministic algorithm
for $(2+o(1))\Delta$edgecoloring, improving on that of Ghaffari and Su.

Consider a small group of mobile agents whose goal is to locate a certain
cell in a twodimensional infinite grid. The agents operate in an asynchronous
environment, where in each discrete time step, an arbitrary subset of the
agents execute one atomic lookcomputemove cycle. The protocol controlling
each agent is determined by a (possibly distinct) finite automaton. The only
means of communication is to sense the states of the agents sharing the same
grid cell. Whenever an agent moves, the destination cell of the movement is
chosen by the agent's automaton from the set of neighboring grid cells. We
study the minimum number of agents required to locate the target cell within
finite time and our main result states a tight lower bound for agents endowed
with a global compass. Furthermore, we show that the lack of such a compass
makes the problem strictly more difficult and present tight upper and lower
bounds for this case.

The complexity of distributed edge coloring depends heavily on the palette
size as a function of the maximum degree $\Delta$. In this paper we explore the
complexity of edge coloring in the LOCAL model in different palette size
regimes.
1. We simplify the \emph{round elimination} technique of Brandt et al. and
prove that $(2\Delta2)$edge coloring requires $\Omega(\log_\Delta \log n)$
time w.h.p. and $\Omega(\log_\Delta n)$ time deterministically, even on trees.
The simplified technique is based on two ideas: the notion of an irregular
running time and some general observations that transform weak lower bounds
into stronger ones.
2. We give a randomized edge coloring algorithm that can use palette sizes as
small as $\Delta + \tilde{O}(\sqrt{\Delta})$, which is a natural barrier for
randomized approaches. The running time of the algorithm is at most
$O(\log\Delta \cdot T_{LLL})$, where $T_{LLL}$ is the complexity of a
permissive version of the constructive Lovasz local lemma.
3. We develop a new distributed Lovasz local lemma algorithm for
treestructured dependency graphs, which leads to a $(1+\epsilon)\Delta$edge
coloring algorithm for trees running in $O(\log\log n)$ time. This algorithm
arises from two new results: a deterministic $O(\log n)$time LLL algorithm for
treestructured instances, and a randomized $O(\log\log n)$time graph
shattering method for breaking the dependency graph into independent $O(\log
n)$size LLL instances.
4. A natural approach to computing $(\Delta+1)$edge colorings (Vizing's
theorem) is to extend partial colorings by iteratively recoloring parts of the
graph. We prove that this approach may be viable, but in the worst case
requires recoloring subgraphs of diameter $\Omega(\Delta\log n)$. This stands
in contrast to distributed algorithms for Brooks' theorem, which exploit the
existence of $O(\log_\Delta n)$length augmenting paths.

Given two colorings of a graph, we consider the following problem: can we
recolor the graph from one coloring to the other through a series of elementary
changes, such that the graph is properly colored after each step?
We introduce the notion of distributed recoloring: The input graph represents
a network of computers that needs to be recolored. Initially, each node is
aware of its own input color and target color. The nodes can exchange messages
with each other, and eventually each node has to stop and output its own
recoloring schedule, indicating when and how the node changes its color. The
recoloring schedules have to be globally consistent so that the graph remains
properly colored at each point, and we require that adjacent nodes do not
change their colors simultaneously.
We are interested in the following questions: How many communication rounds
are needed (in the LOCAL model of distributed computing) to find a recoloring
schedule? What is the length of the recoloring schedule? And how does the
picture change if we can use extra colors to make recoloring easier?
The main contributions of this work are related to distributed recoloring
with one extra color in the following graph classes: trees, $3$regular graphs,
and toroidal grids.

Recently, studying fundamental graph problems in the \emph{Massive Parallel
Computation (MPC)} framework, inspired by the \emph{MapReduce} paradigm, has
gained a lot of attention. A standard assumption, common to most traditional
approaches, is to allow $\widetilde{\Omega}(n)$ memory per machine, where $n$
is the number of nodes in the graph and $\widetilde{\Omega}$ hides
polylogarithmic factors. However, as pointed out by Karloff et al.~[SODA'10]
and Czumaj et al.~[arXiv:1707.03478], it might be unrealistic for a single
machine to have linear or only slightly sublinear memory.
In this paper, we propose the study of a more practical variant of the MPC
model which only requires substantially sublinear or even subpolynomial memory
per machine. In contrast to the standard MPC model and also streaming, in this
lowmemory MPC setting, a single machine will only see a small number of nodes
in the graph. We introduce a new technique to cope with this imposed locality.
In particular, we show that the \emph{Maximal Independent Set (MIS)} problem
can be solved efficiently, that is, in $\bigO(\log^2 \log n)$ rounds, when the
input graph is a tree. This substantially reduces the local memory from
$\frac{n}{\poly\log n}$ required by the recent $\bigO(\log \log n)$round MIS
algorithm of Ghaffari et al., to $n^{\eps}$, without incurring a significant
loss in the round complexity. Moreover, it demonstrates how to make use of the
alltoall communication in the MPC model to exponentially improve on the
corresponding bound in the LOCAL and PRAM models by Lenzen and Wattenhofer
[PODC'11].

Like distributed systems, biological multicellular processes are subject to
dynamic changes and a biological system will not pass the
survivalofthefittest test unless it exhibits certain features that enable
fast recovery from these changes. In particular, a question that is crucial in
the context of biological cellular networks, is whether the system can keep the
changing components \emph{confined} so that only nodes in their vicinity may be
affected by the changes, but nodes sufficiently far away from any changing
component remain unaffected.
Based on this notion of confinement, we propose a new metric for measuring
the dynamic changes recovery performance in distributed network algorithms
operating under the \emph{Stone Age} model (Emek \& Wattenhofer, PODC 2013),
where the class of dynamic topology changes we consider includes
inserting/deleting an edge, deleting a node together with its incident edges,
and inserting a new isolated node. Our main technical contribution is a
distributed algorithm for maximal independent set (MIS) in synchronous networks
subject to these topology changes that performs well in terms of the
aforementioned new metric. Specifically, our algorithm guarantees that nodes
which do not experience a topology change in their immediate vicinity are not
affected and that all surviving nodes (including the affected ones) perform
$\mathcal{O}((C + 1) \log^{2} n)$ computationallymeaningful steps, where $C$
is the number of topology changes; in other words, each surviving node performs
$\mathcal{O}(\log^{2} n)$ steps when amortized over the number of topology
changes. This is accompanied by a simple example demonstrating that the linear
dependency on $C$ cannot be avoided.

Consider a small number of scouts exploring the infinite $d$dimensional grid
with the aim of hitting a hidden target point. Each scout is controlled by a
probabilistic finite automaton that determines its movement (to a neighboring
grid point) based on its current state. The scouts, that operate under a fully
synchronous schedule, communicate with each other (in a way that affects their
respective states) when they share the same grid point and operate
independently otherwise. Our main research question is: How many scouts are
required to guarantee that the target admits a finite mean hitting time?
Recently, it was shown that $d + 1$ is an upper bound on the answer to this
question for any dimension $d \geq 1$ and the main contribution of this paper
comes in the form of proving that this bound is tight for $d \in \{ 1, 2 \}$.

We show that any randomised Monte Carlo distributed algorithm for the
Lov\'asz local lemma requires $\Omega(\log \log n)$ communication rounds,
assuming that it finds a correct assignment with high probability. Our result
holds even in the special case of $d = O(1)$, where $d$ is the maximum degree
of the dependency graph. By prior work, there are distributed algorithms for
the Lov\'asz local lemma with a running time of $O(\log n)$ rounds in
boundeddegree graphs, and the best lower bound before our work was
$\Omega(\log^* n)$ rounds [Chung et al. 2014].

Consider the Ants Nearby Treasure Search (ANTS) problem introduced by
Feinerman, Korman, Lotker, and Sereni (PODC 2012), where $n$ mobile agents,
initially placed at the origin of an infinite grid, collaboratively search for
an adversarially hidden treasure. In this paper, the model of Feinerman et al.
is adapted such that the agents are controlled by a (randomized) finite state
machine: they possess a constantsize memory and are able to communicate with
each other through constantsize messages. Despite the restriction to
constantsize memory, we show that their collaborative performance remains the
same by presenting a distributed algorithm that matches a lower bound
established by Feinerman et al. on the runtime of any ANTS algorithm.

A local algorithm is a distributed algorithm that completes after a constant
number of synchronous communication rounds. We present local approximation
algorithms for the minimum dominating set problem and the maximum matching
problem in 2coloured and weakly 2coloured graphs. In a weakly 2coloured
graph, both problems admit a local algorithm with the approximation factor
$(\Delta+1)/2$, where $\Delta$ is the maximum degree of the graph. We also give
a matching lower bound proving that there is no local algorithm with a better
approximation factor for either of these problems. Furthermore, we show that
the stronger assumption of a 2colouring does not help in the case of the
dominating set problem, but there is a local approximation scheme for the
maximum matching problem in 2coloured graphs.