2026-07-25T01:16:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9818 2024-03-06T10:45:00Z ddc:004 open_access

Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set Ghaffari, Mohsen Kuhn, Fabian Distributed Algorithms Derandomization Spanners Dominating Set 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mohsen Ghaffari and Fabian Kuhn 2018 Is Part Of LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2018.29 urn:nbn:de:0030-drops-98181 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.29 eng https://creativecommons.org/licenses/by/3.0/legalcode