The Taub Faculty of Computer Science Events and Talks

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