Shared Randomness Helps with Local Distributed Problems
Loading...
Access rights
openAccess
CC BY
CC BY
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
Series
52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025, pp. 1-18, Leibniz International Proceedings in Informatics, LIPIcs ; Volume 334
Abstract
By prior work, we have many wonderful results related to distributed graph algorithms for problems that can be defined with local constraints; the formal framework used in prior work is locally checkable labeling problems (LCLs), introduced by Naor and Stockmeyer in the 1990s. It is known, for example, that if we have a deterministic algorithm that solves an LCL in o(log n) rounds, we can speed it up to O(log^* n) rounds, and if we have a randomized algorithm that solves an LCL in O(log^* n) rounds, we can derandomize it for free. It is also known that randomness helps with some LCL problems: there are LCL problems with randomized complexity Θ(log log n) and deterministic complexity Θ(log n). However, so far there have not been any LCL problems in which the use of shared randomness has been necessary; in all prior algorithms it has been enough that the nodes have access to their own private sources of randomness. Could it be the case that shared randomness never helps with LCLs? Could we have a general technique that takes any distributed graph algorithm for any LCL that uses shared randomness, and turns it into an equally fast algorithm where private randomness is enough? In this work we show that the answer is no. We present an LCL problem Π such that the round complexity of Π is Ω(√n) in the usual randomized LOCAL model (with private randomness), but if the nodes have access to a source of shared randomness, then the complexity drops to O(log n). As corollaries, we also resolve several other open questions related to the landscape of distributed computing in the context of LCL problems. In particular, problem Π demonstrates that distributed quantum algorithms for LCL problems strictly benefit from a shared quantum state. Problem Π also gives a separation between finitely dependent distributions and non-signaling distributions.Description
Other note
Citation
Balliu, A, Ghaffari, M, Kuhn, F, Modanese, A, Olivetti, D, Rabie, M, Suomela, J & Uitto, J 2025, Shared Randomness Helps with Local Distributed Problems. in K Censor-Hillel, F Grandoni, J Ouaknine & G Puppis (eds), 52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025., 16, Leibniz International Proceedings in Informatics, LIPIcs, vol. 334, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 1-18, International Colloquium on Automata, Languages, and Programming, Aarhus, Denmark, 08/07/2025. https://doi.org/10.4230/LIPICS.ICALP.2025.16