caa a22 4500 555285480 20190715031130.0 cr unu---uuuuu 190206s2018 xx s 100 0 eng 10.3929/ethz-b-000315335 doi 10.4230/LIPIcs.DISC.2018.29 doi (ETHRESEARCH)oai:www.research-collection.ethz.ch:20.500.11850/315335 Ghaffari Mohsen Derandomizing distributed algorithms with small messages: Spanners and dominating set [Elektronische Daten] [Mohsen Ghaffari, Fabian Kuhn, Ulrich Schmid (Editor), Josef Widder (Editor)] Leibniz int. proc. inform. Dagstuhl Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2018 Open access ethresearch 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. 32nd International Symposium on Distributed Computing (DISC 2018) in New Orleans, LA, USA (October 15-19, 2018) Creative Commons Attribution 3.0 Unported http://creativecommons.org/licenses/by/3.0 ethresearch Distributed Algorithms ethresearch Derandomization ethresearch Spanners ethresearch Dominating Set ethresearch Kuhn Fabian joint author Schmid Ulrich Editor edt Widder Josef Editor edt 32nd International Symposium on Distributed Computing (DISC 2018) Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatik pp. 29:1-29:17 978-3-95977-092-7 http://hdl.handle.net/20.500.11850/315335 text/html WWW-Backlink auf das Repository (Open access) 1 Conference Paper ethresearch ETHRESEARCH 856 40 http://hdl.handle.net/20.500.11850/315335 text/html WWW-Backlink auf das Repository (Open access) ETHRESEARCH 100 1- Ghaffari Mohsen ETHRESEARCH 700 1- Kuhn Fabian joint author ETHRESEARCH 700 1- Schmid Ulrich Editor edt ETHRESEARCH 700 1- Widder Josef Editor edt ETHRESEARCH 773 0- 32nd International Symposium on Distributed Computing (DISC 2018) Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatik pp. 29:1-29:17 978-3-95977-092-7 BK010053 XK010053 XK010000 ETHRESEARCH ETHRESEARCH ETHRESEARCH Conference Paper Open access