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

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