## Fast and Cheap Asynchronous Construction of Small $k$-Dominating Sets

by Yuval Emek

#### Oded's comments

The focus of this talk is on the asyncronbous message-passing
model in which the $n$ processors have $O(\log n)$-bit IDs, and
messages are of $O(\log n)$ length (i.e., `congest' model).
The KT1 assumption asserts that processors know (a priori)
the IDs of their neighbors, in contrast to KT0 in which they
only know their own IDs. Note that the difference mais significant
when we seek algorithms of message complexity $o(m)$,
where $m$ is the number of edges/links.

In contrast to prior beliefs, it was shown a few years ago that,
in the *syncronbous* message-passing model,
some non-trivial (and natural) computational tasks can be
performed using $o(m)$ messaages (assuming $m = omega(n^{3/2})$)
withing reasonable (say poly(n)) time.
The distributed algorithm is randomized,
and it seems that this may be essential for the result.
This work achieves an analogous result for the much
more challenging asyncronbous model.

For a parameter $k$, the new distributed algorithm
has message complexity $\tildeO(kn)$
and time complexity $\tildeO(k^2)$.
In fact, it constructs a partition of the vertex set such that
each part is spanned by a rooted tree of height at most $k$
that contains at least $k+1$ vertices.
(Indeed, the roots of these tree constitute a $k$-DS
of size $max(1,floor(n/(k+1)))$.

The starting point is that unique IDs induce the assignment
of unique weights to edges (i.e., the 2-set of the two endpoint IDs),
which are known to both endpoints, which in turn determine a unique MST.
The algorithm uses only the edges of the MST, and each edges
is used at most $\tildeO(k^2)$ times.

#### The original abstract

A $k$-dominating set ($k$-DS) is a node subset of distance at most $k$ from
any node in the graph.
The task of constructing a small (i.e., existentially optimal) $k$-DS
was suggested by Kutten and Peleg (Journal of Algorithms, 1998)
as a useful primitive for distributed graph algorithms
and received considerable attention ever since.
In the current paper, we advance the state-of-the-art of distributed
small $k$-DS construction by presenting a randomized asynchronous CONGEST KT1
algorithm for this task that runs in $\tilde{O}( k^{2} )$ time
and sends $\tilde{O}( n k )$ messages whp.
When $k \leq polylog( n )$, we obtain the first asynchronous algorithm
for a non-trivial distributed task whose communication cost is near-linear
(in $n$).

Back to
list of Oded's choices.