Skip to content (access key 's')
Logo of Technion
Logo of CS Department

The Taub Faculty of Computer Science Events and Talks

Efficient Distributed Construction of Small k-Dominating Sets
event speaker icon
Ido Rafael (M.Sc. Thesis Seminar)
event date icon
Tuesday, 10.08.2021, 10:30
event location icon
Zoom Lecture: 3151462578
event speaker icon
Advisor: Prof. Y. Emek & Prof. S. Kutten
We improve the message efficiency of the time-efficient construction of a "small" (i.e. universaly optimal) k-dominating set (k-DS) under the Distributed CONGEST model. This task was suggested by Kutten and Peleg as a useful primitive in constructing other time-efficient algorithms such as a minimum spanning tree. It is also useful for constructing other local (i.e. sub-diameter time) algorithms such as partitioning the network into clusters (each a rooted tree) of diameter k. We first address the problem in the KT1 model (where a node knows the unique identity of each neighbor) that has been receiving increased attention in recent years. The new algorithm achieves time \tilde{O}(k^2) and message \tilde{O}(nk) complexities. It is thus the first small k-DS algorithm with o(m) messages (for k=o(m/n)) in the KT1 model. We also address the KT0 model used by Kutten and Peleg (where a node does not know the identities of its neighbors). For KT0, we present the first asynchronous sub-diameter time algorithm. Its message complexity is \tilde{O}(m+nk), compared to the O(m k log*n) complexity of the trivial asynchronous algorithm (that uses an alpha-synchronizer).