Technical Report No. 285 - Abstract

Mohsen Ghaffari und Fabian Kuhn
Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set

This paper presents improved deterministic distributed algorithms, with O(log n)-bit messages, for a range of graph problems. The common ingredient in our results is a deterministic distributed algorithm for computing a certain hitting set, which can replace the random part of a number of standard randomized distributed algorithms. This deterministic hitting set algorithm itself is derived using a simple method of conditional expectations. As one main end-result, we get a deterministic distributed algorithm with round complexity 2^O(sqrt(log n loglog n)) for computing a (2k-1)-spanner of size \tilde{O}(n^(1+1/k)). This improves considerably on a recent algorithm of Grossman and Parter [DISC'17] which needs O(n^(1/2-1/k) * 2^k) rounds. We also get a 2^O(sqrt(log n loglog n))-round algorithm for computing an O(log n)-approximation of minimum dominating set; all prior algorithms for this problem were either randomized or required large messages.