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.
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$).