
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.

In a recent breakthrough, Paz and Schwartzman (SODA'17) presented a
singlepass ($2+\epsilon$)approximation algorithm for the maximum weight
matching problem in the semistreaming model. Their algorithm uses $O(n\log^2
n)$ bits of space, for any constant $\epsilon>0$.
We present two simplified and more intuitive analyses, for essentially the
same algorithm, which also improve the space complexity to the optimal bound of
$O(n\log n)$ bits  this is optimal as the output matching requires
$\Omega(n\log n)$ bits. Our analyses rely on a simple use of the primaldual
method and a simple accounting method.

The \emph{UndecidedState Dynamics} is a wellknown protocol for distributed
consensus. We analyze it in the parallel \pull\ communication model on the
complete graph for the \emph{binary} case (every node can either support one of
\emph{two} possible colors, or be in the undecided state).
An interesting open question is whether this dynamics \emph{always} (i.e.,
starting from an arbitrary initial configuration) reaches consensus
\emph{quickly} (i.e., within a polylogarithmic number of rounds) in a complete
graph with $n$ nodes. Previous work in this setting only considers initial
color configurations with no undecided nodes and a large \emph{bias} (i.e.,
$\Theta(n)$) towards the majority color.
In this paper we present an \textit{unconditional} analysis of the
UndecidedState Dynamics that answers to the above question in the affirmative.
We prove that, starting from \textit{any} initial configuration, the process
reaches a monochromatic configuration within $O(\log n)$ rounds, with high
probability. This bound turns out to be tight. Our analysis also shows that, if
the initial configuration has bias $\Omega(\sqrt{n\log n})$, then the dynamics
converges toward the initial majority color, with high probability.

Computing shortest paths is one of the central problems in the theory of
distributed computing. For the last few years, substantial progress has been
made on the approximate single source shortest paths problem, culminating in an
algorithm of Becker et al. [DISC'17] which deterministically computes
$(1+o(1))$approximate shortest paths in $\tilde O(D+\sqrt n)$ time, where $D$
is the hopdiameter of the graph. Up to logarithmic factors, this time
complexity is optimal, matching the lower bound of Elkin [STOC'04].
The question of exact shortest paths however saw no algorithmic progress for
decades, until the recent breakthrough of Elkin [STOC'17], which established a
sublineartime algorithm for exact single source shortest paths on undirected
graphs. Shortly after, Huang et al. [FOCS'17] provided improved algorithms for
exact all pairs shortest paths problem on directed graphs.
In this paper, we present a new singlesource shortest path algorithm with
complexity $\tilde O(n^{3/4}D^{1/4})$. For polylogarithmic $D$, this improves
on Elkin's $\tilde{O}(n^{5/6})$ bound and gets closer to the
$\tilde{\Omega}(n^{1/2})$ lower bound of Elkin [STOC'04]. For larger values of
$D$, we present an improved variant of our algorithm which achieves complexity
$\tilde{O}\left( n^{3/4+o(1)}+ \min\{ n^{3/4}D^{1/6},n^{6/7}\}+D\right)$, and
thus compares favorably with Elkin's bound of $\tilde{O}(n^{5/6} +
n^{2/3}D^{1/3} + D ) $ in essentially the entire range of parameters. This
algorithm provides also a qualitative improvement, because it works for the
more challenging case of directed graphs (i.e., graphs where the two directions
of an edge can have different weights), constituting the first sublineartime
algorithm for directed graphs. Our algorithm also extends to the case of exact
$\kappa$source shortest paths...

The gap between the known randomized and deterministic local distributed
algorithms underlies arguably the most fundamental and central open question in
distributed graph algorithms. In this paper, we develop a generic and clean
recipe for derandomizing randomized LOCAL algorithms and transforming them into
efficient deterministic LOCAL algorithm. We also exhibit how this simple recipe
leads to significant improvements on a number of problems, in cases resolving
known open problems. Two sample endresults are as follows:
 An improved distributed hypergraph maximal matching algorithm, which
improves on that of Fischer, Ghaffari, and Kuhn [FOCS'17], and leads to
improved algorithms for edgecoloring, maximum matching approximation, and low
outdegree edge orientation. The first gives an improved algorithm for Open
Problem 11.4 of the book of Barenboim and Elkin, and the last gives the first
positive resolution of their Open Problem 11.10.
 An improved distributed algorithm for the Lov\'{a}sz Local Lemma, which
gets closer to a conjecture of Chang and Pettie [FOCS'17], and moreover leads
to improved distributed algorithms for problems such as defective coloring and
$k$SAT.

We present a randomized distributed algorithm that computes a
$\Delta$coloring in any noncomplete graph with maximum degree $\Delta \geq 4$
in $O(\log \Delta) + 2^{O(\sqrt{\log\log n})}$ rounds, as well as a randomized
algorithm that computes a $\Delta$coloring in $O((\log \log n)^2)$ rounds when
$\Delta \in [3, O(1)]$. Both these algorithms improve on an $O(\log^3 n/\log
\Delta)$round algorithm of Panconesi and Srinivasan~[STOC'1993], which has
remained the state of the art for the past 25 years. Moreover, the latter
algorithm gets (exponentially) closer to an $\Omega(\log\log n)$ round lower
bound of Brandt et al.~[STOC'16].

We present $O(\log\log n)$round algorithms in the Massively Parallel
Computation (MPC) model, with $\tilde{O}(n)$ memory per machine, that compute a
maximal independent set, a $1+\epsilon$ approximation of maximum matching, and
a $2+\epsilon$ approximation of minimum vertex cover, for any $n$vertex graph
and any constant $\epsilon>0$. These improve the state of the art as follows:
 Our MIS algorithm leads to a simple $O(\log\log \Delta)$round MIS
algorithm in the Congested Clique model of distributed computing. This result
improves exponentially on the $\tilde{O}(\sqrt{\log \Delta})$round algorithm
of Ghaffari [PODC'17].
 Our $O(\log\log n)$round $(1+\epsilon)$approximate maximum matching
algorithm simplifies and improves on a rather complex $O(\log^2\log n)$round
$(1+\epsilon)$approximation algorithm of Czumaj et al. [STOC'18].
 Our $O(\log\log n)$round $(2+\epsilon)$approximate minimum vertex cover
algorithm improves on an $O(\log\log n)$round $O(1)$approximation of Assadi
et al. [arXiv'17].

\emph{Sampling} constitutes an important tool in a variety of areas: from
machine learning and combinatorial optimization to computational physics and
biology. A central class of sampling algorithms is the \emph{Markov Chain Monte
Carlo} method, based on the construction of a Markov chain with the desired
sampling distribution as its stationary distribution. Many of the traditional
Markov chains, such as the \emph{Glauber dynamics}, do not scale well with
increasing dimension. To address this shortcoming, we propose a simple local
update rule based on the Glauber dynamics that leads to efficient parallel and
distributed algorithms for sampling from Gibbs distributions.
Concretely, we present a Markov chain that mixes in $O(\log n)$ rounds when
Dobrushin's condition for the Gibbs distribution is satisfied. This improves
over the \emph{LubyGlauber} algorithm by Feng, Sun, and Yin [PODC'17], which
needs $O(\Delta \log n)$ rounds, and their \emph{LocalMetropolis} algorithm,
which converges in $O(\log n)$ rounds but requires a considerably stronger
mixing condition. Here, $n$ denotes the number of nodes in the graphical model
inducing the Gibbs distribution, and $\Delta$ its maximum degree. In
particular, our method can sample a uniform proper coloring with
$(2+\eps)\Delta$ colors in $O(\log n)$ rounds, for any constant $\eps >0$,
which almost matches the threshold of the sequential Glauber dynamics and
improves on the $(2 +\sqrt{2}+\eps)\Delta$ threshold of Feng et al.

Graph coloring is one of the central problems in distributed graph
algorithms. Much of the research on this topic has focused on coloring with
$\Delta+1$ colors, where $\Delta$ denotes the maximum degree. Using $\Delta+1$
colors may be unsatisfactory in sparse graphs, where not all nodes have such a
high degree; it would be more desirable to use a number of colors that improves
with sparsity. A standard measure that captures sparsity is arboricity, which
is the smallest number of forests into which the edges of the graph can be
partitioned.
We present simple randomized distributed algorithms that, with high
probability, color any $n$node $\alpha$arboricity graph:
 using $(2+\varepsilon)\cdot \alpha$ colors, for constant $\varepsilon>0$,
in $O(\log n)$ rounds, if $\alpha=\tilde{\Omega}(\log n)$, or
 using $O(\alpha \log \alpha )$ colors, in $O(\log n)$ rounds, or
 using $O(\alpha)$ colors, in $O(\log n \cdot \min\{\log\log n,\; \log
\alpha\})$ rounds.
These algorithms are nearlyoptimal, as it is known by results of Linial
[FOCS'87] and Barenboim and Elkin [PODC'08] that coloring with $\Theta(\alpha)$
colors, or even poly$(\alpha)$ colors, requires $\Omega(\log_{\alpha} n)$
rounds. The previously bestknown $O(\log n)$time result was a deterministic
algorithm due to Barenboim and Elkin [PODC'08], which uses $\Theta(\alpha ^2)$
colors. Barenboim and Elkin stated improving this number of colors as an open
problem in their Distributed Graph Coloring Book.

We present a simple distributed $\Delta$approximation algorithm for maximum
weight independent set (MaxIS) in the $\mathsf{CONGEST}$ model which completes
in $O(\texttt{MIS}(G)\cdot \log W)$ rounds, where $\Delta$ is the maximum
degree, $\texttt{MIS}(G)$ is the number of rounds needed to compute a maximal
independent set (MIS) on $G$, and $W$ is the maximum weight of a node. %Whether
our algorithm is randomized or deterministic depends on the \texttt{MIS}
algorithm used as a blackbox.
Plugging in the best known algorithm for MIS gives a randomized solution in
$O(\log n \log W)$ rounds, where $n$ is the number of nodes.
We also present a deterministic $O(\Delta +\log^* n)$round algorithm based
on coloring.
We then show how to use our MaxIS approximation algorithms to compute a
$2$approximation for maximum weight matching without incurring any additional
round penalty in the $\mathsf{CONGEST}$ model. We use a known reduction for
simulating algorithms on the line graph while incurring congestion, but we show
our algorithm is part of a broad family of \emph{local aggregation algorithms}
for which we describe a mechanism that allows the simulation to run in the
$\mathsf{CONGEST}$ model without an additional overhead.
Next, we show that for maximum weight matching, relaxing the approximation
factor to ($2+\varepsilon$) allows us to devise a distributed algorithm
requiring $O(\frac{\log \Delta}{\log\log\Delta})$ rounds for any constant
$\varepsilon>0$. For the unweighted case, we can even obtain a
$(1+\varepsilon)$approximation in this number of rounds. These algorithms are
the first to achieve the provably optimal round complexity with respect to
dependency on $\Delta$.

We present a tight analysis for the wellstudied randomized 3majority
dynamics of stabilizing consensus, hence answering the main open question of
Becchetti et al. [SODA'16].
Consider a distributed system of n nodes, each initially holding an opinion
in {1, 2, ..., k}. The system should converge to a setting where all
(noncorrupted) nodes hold the same opinion. This consensus opinion should be
\emph{valid}, meaning that it should be among the initially supported opinions,
and the (fast) convergence should happen even in the presence of a malicious
adversary who can corrupt a bounded number of nodes per round and in particular
modify their opinions. A wellstudied distributed algorithm for this problem is
the 3majority dynamics, which works as follows: per round, each node gathers
three opinions  say by taking its own and two of other nodes sampled at
random  and then it sets its opinion equal to the majority of this set; ties
are broken arbitrarily, e.g., towards the node's own opinion.
Becchetti et al. [SODA'16] showed that the 3majority dynamics converges to
consensus in O((k^2\sqrt{\log n} + k\log n)(k+\log n)) rounds, even in the
presence of a limited adversary. We prove that, even with a stronger adversary,
the convergence happens within O(k\log n) rounds. This bound is known to be
optimal.

Locally Checkable Labeling (LCL) problems include essentially all the classic
problems of $\mathsf{LOCAL}$ distributed algorithms. In a recent enlightening
revelation, Chang and Pettie [arXiv 1704.06297] showed that any LCL (on bounded
degree graphs) that has an $o(\log n)$round randomized algorithm can be solved
in $T_{LLL}(n)$ rounds, which is the randomized complexity of solving (a
relaxed variant of) the Lov\'asz Local Lemma (LLL) on bounded degree $n$node
graphs. Currently, the best known upper bound on $T_{LLL}(n)$ is $O(\log n)$,
by Chung, Pettie, and Su [PODC'14], while the best known lower bound is
$\Omega(\log\log n)$, by Brandt et al. [STOC'16]. Chang and Pettie conjectured
that there should be an $O(\log\log n)$round algorithm.
Making the first step of progress towards this conjecture, and providing a
significant improvement on the algorithm of Chung et al. [PODC'14], we prove
that $T_{LLL}(n)= 2^{O(\sqrt{\log\log n})}$. Thus, any $o(\log n)$round
randomized distributed algorithm for any LCL problem on bounded degree graphs
can be automatically sped up to run in $2^{O(\sqrt{\log\log n})}$ rounds.
Using this improvement and a number of other ideas, we also improve the
complexity of a number of graph coloring problems (in arbitrary degree graphs)
from the $O(\log n)$round results of Chung, Pettie and Su [PODC'14] to
$2^{O(\sqrt{\log\log n})}$. These problems include defective coloring, frugal
coloring, and list vertexcoloring.

We present a deterministic distributed algorithm that computes a
$(2\Delta1)$edgecoloring, or even listedgecoloring, in any $n$node graph
with maximum degree $\Delta$, in $O(\log^7 \Delta \log n)$ rounds. This answers
one of the longstanding open questions of \emph{distributed graph algorithms}
from the late 1980s, which asked for a polylogarithmictime algorithm. See,
e.g., Open Problem 4 in the Distributed Graph Coloring book of Barenboim and
Elkin. The previous best round complexities were $2^{O(\sqrt{\log n})}$ by
Panconesi and Srinivasan [STOC'92] and $\tilde{O}(\sqrt{\Delta}) + O(\log^* n)$
by Fraigniaud, Heinrich, and Kosowski [FOCS'16]. A corollary of our
deterministic listedgecoloring also improves the randomized complexity of
$(2\Delta1)$edgecoloring to poly$(\log\log n)$ rounds.
The key technical ingredient is a deterministic distributed algorithm for
\emph{hypergraph maximal matching}, which we believe will be of interest beyond
this result. In any hypergraph of rank $r$  where each hyperedge has at most
$r$ vertices  with $n$ nodes and maximum degree $\Delta$, this algorithm
computes a maximal matching in $O(r^5 \log^{6+\log r } \Delta \log n)$ rounds.
This hypergraph matching algorithm and its extensions lead to a number of
other results. In particular, a polylogarithmictime deterministic distributed
maximal independent set algorithm for graphs with bounded neighborhood
independence, hence answering Open Problem 5 of Barenboim and Elkin's book, a
$((\log \Delta/\varepsilon)^{O(\log (1/\varepsilon))})$round deterministic
algorithm for $(1+\varepsilon)$approximation of maximum matching, and a
quasipolylogarithmictime deterministic distributed algorithm for orienting
$\lambda$arboricity graphs with outdegree at most $(1+\varepsilon)\lambda$,
for any constant $\varepsilon>0$, hence partially answering Open Problem 10 of
Barenboim and Elkin's book.

This paper is centered on the complexity of graph problems in the
wellstudied LOCAL model of distributed computing, introduced by Linial [FOCS
'87]. It is widely known that for many of the classic distributed graph
problems (including maximal independent set (MIS) and $(\Delta+1)$vertex
coloring), the randomized complexity is at most polylogarithmic in the size $n$
of the network, while the best deterministic complexity is typically
$2^{O(\sqrt{\log n})}$. Understanding and narrowing down this exponential gap
is considered to be one of the central longstanding open questions in the area
of distributed graph algorithms. We investigate the problem by introducing a
complexitytheoretic framework that allows us to shed some light on the role of
randomness in the LOCAL model. We define the SLOCAL model as a sequential
version of the LOCAL model. Our framework allows us to prove completeness
results with respect to the class of problems which can be solved efficiently
in the SLOCAL model, implying that if any of the complete problems can be
solved deterministically in $\log^{O(1)} n$ rounds in the LOCAL model, we can
deterministically solve all efficient SLOCALproblems (including MIS and
$(\Delta+1)$coloring) in $\log^{O(1)} n$ rounds in the LOCAL model. We show
that a rather rudimentary looking graph coloring problem is complete in the
above sense: Color the nodes of a graph with colors red and blue such that each
node of sufficiently large polylogarithmic degree has at least one neighbor of
each color. The problem admits a trivial zeroround randomized solution. The
result can be viewed as showing that the only obstacle to getting efficient
determinstic algorithms in the LOCAL model is an efficient algorithm to
approximately round fractional values into integer values.

We study a family of closelyrelated distributed graph problems, which we
call degree splitting, where roughly speaking the objective is to partition (or
orient) the edges such that each node's degree is split almost uniformly. Our
findings lead to answers for a number of problems, a sampling of which
includes:
 We present a $poly(\log n)$ round deterministic algorithm for
$(2\Delta1)\cdot (1+o(1))$edgecoloring, where $\Delta$ denotes the maximum
degree. Modulo the $1+o(1)$ factor, this settles one of the longstanding open
problems of the area from the 1990's (see e.g. Panconesi and Srinivasan
[PODC'92]). Indeed, a weaker requirement of $(2\Delta1)\cdot poly(\log
\Delta)$edgecoloring in $poly(\log n)$ rounds was asked for in the 4th open
question in the Distributed Graph Coloring book by Barenboim and Elkin.
 We show that sinkless orientationi.e., orienting edges such that each
node has at least one outgoing edgeon $\Delta$regular graphs can be solved
in $O(\log_{\Delta} \log n)$ rounds randomized and in $O(\log_{\Delta} n)$
rounds deterministically. These prove the corresponding lower bounds by Brandt
et al. [STOC'16] and Chang, Kopelowitz, and Pettie [FOCS'16] to be tight.
Moreover, these show that sinkless orientation exhibits an exponential
separation between its randomized and deterministic complexities, akin to the
results of Chang et al. for $\Delta$coloring $\Delta$regular trees.
 We present a randomized $O(\log^4 n)$ round algorithm for orienting
$a$arboricity graphs with maximum outdegree $a(1+\epsilon)$. This can be also
turned into a decomposition into $a (1+\epsilon)$ forests when $a=\Omega(\log
n)$ and into $a (1+\epsilon)$ pseduoforests when $a=o(\log n)$. Obtaining an
efficient distributed decomposition into less than $2a$ forests was stated as
the 10th open problem in the book by Barenboim and Elkin.

In this paper, we study PUSHPULL style rumor spreading algorithms in the
mobile telephone model, a variant of the classical telephone model in which
each node can participate in at most one connection per round; i.e., you can no
longer have multiple nodes pull information from the same source in a single
round. Our model also includes two new parameterized generalizations: (1) the
network topology can undergo a bounded rate of change (for a parameterized rate
that spans from no changes to changes in every round); and (2) in each round,
each node can advertise a bounded amount of information to all of its neighbors
before connection decisions are made (for a parameterized number of bits that
spans from no advertisement to large advertisements). We prove that in the
mobile telephone model with no advertisements and no topology changes,
PUSHPULL style algorithms perform poorly with respect to a graph's vertex
expansion and graph conductance as compared to the known tight results in the
classical telephone model. We then prove, however, that if nodes are allowed to
advertise a single bit in each round, a natural variation of PUSHPULL
terminates in time that matches (within logarithmic factors) this strategy's
performance in the classical telephone modeleven in the presence of frequent
topology changes. We also analyze how the performance of this algorithm
degrades as the rate of change increases toward the maximum possible amount. We
argue that our model matches well the properties of emerging peertopeer
communication standards for mobile devices, and that our efficient PUSHPULL
variation that leverages small advertisements and adapts well to topology
changes is a good choice for rumor spreading in this increasingly important
setting.

We present a nearoptimal distributed algorithm for $(1+o(1))$approximation
of singlecommodity maximum flow in undirected weighted networks that runs in
$(D+ \sqrt{n})\cdot n^{o(1)}$ communication rounds in the \Congest model. Here,
$n$ and $D$ denote the number of nodes and the network diameter, respectively.
This is the first improvement over the trivial bound of $O(n^2)$, and it nearly
matches the $\tilde{\Omega}(D+ \sqrt{n})$ round complexity lower bound.
The development of the algorithm contains two results of independent
interest:
(i) A $(D+\sqrt{n})\cdot n^{o(1)}$round distributed construction of a
spanning tree of average stretch $n^{o(1)}$.
(ii) A $(D+\sqrt{n})\cdot n^{o(1)}$round distributed construction of an
$n^{o(1)}$congestion approximator consisting of the cuts induced by $O(\log
n)$ virtual trees. The distributed representation of the cut approximator
allows for evaluation in $(D+\sqrt{n})\cdot n^{o(1)}$ rounds.
All our algorithms make use of randomization and succeed with high
probability.

The Maximal Independent Set (MIS) problem is one of the basics in the study
of locality in distributed graph algorithms. This paper presents an extremely
simple randomized algorithm providing a nearoptimal local complexity for this
problem, which incidentally, when combined with some recent techniques, also
leads to a nearoptimal global complexity.
Classical algorithms of Luby [STOC'85] and Alon, Babai and Itai [JALG'86]
provide the global complexity guarantee that, with high probability, all nodes
terminate after $O(\log n)$ rounds. In contrast, our initial focus is on the
local complexity, and our main contribution is to provide a very simple
algorithm guaranteeing that each particular node $v$ terminates after $O(\log
\mathsf{deg}(v)+\log 1/\epsilon)$ rounds, with probability at least
$1\epsilon$. The guarantee holds even if the randomness outside $2$hops
neighborhood of $v$ is determined adversarially. This degreedependency is
optimal, due to a lower bound of Kuhn, Moscibroda, and Wattenhofer [PODC'04].
Interestingly, this local complexity smoothly transitions to a global
complexity: by adding techniques of Barenboim, Elkin, Pettie, and Schneider
[FOCS'12, arXiv: 1202.1983v3], we get a randomized MIS algorithm with a high
probability global complexity of $O(\log \Delta) + 2^{O(\sqrt{\log \log n})}$,
where $\Delta$ denotes the maximum degree. This improves over the $O(\log^2
\Delta) + 2^{O(\sqrt{\log \log n})}$ result of Barenboim et al., and gets close
to the $\Omega(\min\{\log \Delta, \sqrt{\log n}\})$ lower bound of Kuhn et al.
Corollaries include improved algorithms for MIS in graphs of upperbounded
arboricity, or lowerbounded girth, for Ruling Sets, for MIS in the Local
Computation Algorithms (LCA) model, and a faster distributed algorithm for the
Lov\'asz Local Lemma.

We introduce the study of the ant colony househunting problem from a
distributed computing perspective. When an ant colony's nest becomes unsuitable
due to size constraints or damage, the colony must relocate to a new nest. The
task of identifying and evaluating the quality of potential new nests is
distributed among all ants. The ants must additionally reach consensus on a
final nest choice and the full colony must be transported to this single new
nest. Our goal is to use tools and techniques from distributed computing theory
in order to gain insight into the househunting process.
We develop a formal model for the househunting problem inspired by the
behavior of the Temnothorax genus of ants. We then show a \Omega(log n) lower
bound on the time for all n ants to agree on one of k candidate nests. We also
present two algorithms that solve the househunting problem in our model. The
first algorithm solves the problem in optimal O(log n) time but exhibits some
features not characteristic of natural ant behavior. The second algorithm runs
in O(k log n) time and uses an extremely simple and natural rule for each ant
to decide on the new nest.

All consensus hierarchies in the literature assume that we have, in addition
to copies of a given object, an unbounded number of registers. But why do we
really need these registers?
This paper considers what would happen if one attempts to solve consensus
using various objects but without any registers. We show that under a
reasonable assumption, objects like queues and stacks cannot emulate the
missing registers. We also show that, perhaps surprisingly, initialization,
shown to have no computational consequences when registers are readily
available, is crucial in determining the synchronization power of objects when
no registers are allowed. Finally, we show that without registers, the number
of available objects affects the level of consensus that can be solved.
Our work thus raises the question of whether consensus hierarchies which
assume an unbounded number of registers truly capture synchronization power,
and begins a line of research aimed at better understanding the interaction
between readwrite memory and the powerful synchronization operations available
on modern architectures.

The broadcast throughput in a network is defined as the average number of
messages that can be transmitted per unit time from a given source to all other
nodes when time goes to infinity.
Classical broadcast algorithms treat messages as atomic tokens and route them
from the source to the receivers by making intermediate nodes store and forward
messages. The more recent network coding approach, in contrast, prompts
intermediate nodes to mix and code together messages. It has been shown that
certain wired networks have an asymptotic network coding gap, that is, they
have asymptotically higher broadcast throughput when using network coding
compared to routing. Whether such a gap exists for wireless networks has been
an open question of great interest. We approach this question by studying the
broadcast throughput of the radio network model which has been a standard
mathematical model to study wireless communication.
We show that there is a family of radio networks with a tight $\Theta(\log
\log n)$ network coding gap, that is, networks in which the asymptotic
throughput achievable via routing messages is a $\Theta(\log \log n)$ factor
smaller than that of the optimal network coding algorithm. We also provide new
tight upper and lower bounds that show that the asymptotic worstcase broadcast
throughput over all networks with $n$ nodes is $\Theta(1 / \log n)$
messagesperround for both routing and network coding.

We study the multimessage broadcast problem using abstract MAC layer models
of wireless networks. These models capture the key guarantees of existing MAC
layers while abstracting away lowlevel details such as signal propagation and
contention. We begin by studying upper and lower bounds for this problem in a
{\em standard abstract MAC layer model}identifying an interesting dependence
between the structure of unreliable links and achievable time complexity. In
more detail, given a restriction that devices connected directly by an
unreliable link are not too far from each other in the reliable link topology,
we can (almost) match the efficiency of the reliable case. For the related
restriction, however, that two devices connected by an unreliable link are not
too far from each other in geographic distance, we prove a new lower bound that
shows that this efficiency is impossible. We then investigate how much extra
power must be added to the model to enable a new order of magnitude of
efficiency. In more detail, we consider an {\em enhanced abstract MAC layer
model} and present a new multimessage broadcast algorithm that (under certain
natural assumptions) solves the problem in this model faster than any known
solutions in an abstract MAC layer setting.

This paper presents a nearoptimal distributed approximation algorithm for
the minimumweight connected dominating set (MCDS) problem. The presented
algorithm finds an $O(\log n)$ approximation in $\tilde{O}(D+\sqrt{n})$ rounds,
where $D$ is the network diameter and $n$ is the number of nodes.
MCDS is a classical NPhard problem and the achieved approximation factor
$O(\log n)$ is known to be optimal up to a constant factor, unless P=NP.
Furthermore, the $\tilde{O}(D+\sqrt{n})$ round complexity is known to be
optimal modulo logarithmic factors (for any approximation), following [Das
Sarma et al.STOC'11].

We study coding schemes for error correction in interactive communications.
Such interactive coding schemes simulate any $n$round interactive protocol
using $N$ rounds over an adversarial channel that corrupts up to $\rho N$
transmissions. Important performance measures for a coding scheme are its
maximum tolerable error rate $\rho$, communication complexity $N$, and
computational complexity.
We give the first coding scheme for the standard setting which performs
optimally in all three measures: Our randomized nonadaptive coding scheme has
a nearlinear computational complexity and tolerates any error rate $\delta <
1/4$ with a linear $N = \Theta(n)$ communication complexity. This improves over
prior results which each performed well in two of these measures.
We also give results for other settings of interest, namely, the first
computationally and communication efficient schemes that tolerate $\rho <
\frac{2}{7}$ adaptively, $\rho < \frac{1}{3}$ if only one party is required to
decode, and $\rho < \frac{1}{2}$ if list decoding is allowed. These are the
optimal tolerable error rates for the respective settings. These coding schemes
also have near linear computational and communication complexity.
These results are obtained via two techniques: We give a general blackbox
reduction which reduces unique decoding, in various settings, to list decoding.
We also show how to boost the computational and communication efficiency of any
list decoder to become near linear.

We introduce collision free layerings as a powerful way to structure radio
networks. These layerings can replace hardtocompute BFStrees in many
contexts while having an efficient randomized distributed construction. We
demonstrate their versatility by using them to provide near optimal distributed
algorithms for several multimessage communication primitives.
Designing efficient communication primitives for radio networks has a rich
history that began 25 years ago when BarYehuda et al. introduced fast
randomized algorithms for broadcasting and for constructing BFStrees. Their
BFStree construction time was $O(D \log^2 n)$ rounds, where $D$ is the network
diameter and $n$ is the number of nodes. Since then, the complexity of a
broadcast has been resolved to be $T_{BC} = \Theta(D \log \frac{n}{D} + \log^2
n)$ rounds. On the other hand, BFStrees have been used as a crucial building
block for many communication primitives and their construction time remained a
bottleneck for these primitives.
We introduce collision free layerings that can be used in place of BFStrees
and we give a randomized construction of these layerings that runs in nearly
broadcast time, that is, w.h.p. in $T_{Lay} = O(D \log \frac{n}{D} +
\log^{2+\epsilon} n)$ rounds for any constant $\epsilon>0$. We then use these
layerings to obtain: (1) A randomized algorithm for gathering $k$ messages
running w.h.p. in $O(T_{Lay} + k)$ rounds. (2) A randomized $k$message
broadcast algorithm running w.h.p. in $O(T_{Lay} + k \log n)$ rounds. These
algorithms are optimal up to the small difference in the additive
polylogarithmic term between $T_{BC}$ and $T_{Lay}$. Moreover, they imply the
first optimal $O(n \log n)$ round randomized gossip algorithm.