Derandomizing distributed algorithms with small messages: Spanners and dominating set
OPEN ACCESS
Loading...
Author / Producer
Date
2018
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
This paper presents improved deterministic distributed algorithms, with O(log n)-bit messages, for some basic 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 of this derandomized hitting set, we get a deterministic distributed algorithm with round complexity 2^O(sqrt{log n * log log n}) for computing a (2k-1)-spanner of size 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 * log log n})-round deterministic distributed algorithm for computing an O(log^2 n)-approximation of minimum dominating set; all prior algorithms for this problem were either randomized or required large messages.
Permanent link
Publication status
published
External links
Book title
32nd International Symposium on Distributed Computing (DISC 2018)
Volume
121
Pages / Article No.
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Event
32nd International Symposium on Distributed Computing (DISC 2018)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Distributed Algorithms; Derandomization; Spanners; Dominating Set
Organisational unit
09587 - Ghaffari, Mohsen (ehemalig) / Ghaffari, Mohsen (former)