On the Use of Randomness in Local Distributed Graph Algorithms

DOI10.1145/3293611.3331610MaRDI QIDQ5145222zbMATH OpenOpenAlexWikidataFDO

Authors Mohsen Ghaffari, Fabian Kuhn

Publication date 20 January 2021

Published in Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1906.00482

zbMATH Keywords

congest modeldistributed symmetry breakinglocal modelrandomnessshared randomness

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Recommendations

• On the complexity of local distributed graph problems
• Towards a complexity theory for local distributed computing
• Polylogarithmic-time deterministic network decomposition and distributed derandomization

Cited in

(5)

• Network Decomposition and Distributed Derandomization (Invited Paper)
• Random Node-Asynchronous Updates on Graphs
• Component stability in low-space massively parallel computation
• Shared randomness in locally checkable problems: the role of computational assumptions
• The influence of random number generators on graph partitioning algorithms

This page was built for publication: On the Use of Randomness in Local Distributed Graph Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5145222)