On the Use of Randomness in Local Distributed Graph Algorithms

DOI10.1145/3293611.3331610OpenAlexW2962809442WikidataQ130860891 ScholiaQ130860891MaRDI QIDQ5145222FDOQ5145222

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

Recommendations

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

zbMATH Keywords

randomnesslocal modeldistributed symmetry breakingcongest modelshared randomness

Mathematics Subject Classification ID

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

Cited In (4)

• Random Node-Asynchronous Updates on Graphs
• The influence of random number generators on graph partitioning algorithms
• Network Decomposition and Distributed Derandomization (Invited Paper)
• Component stability in low-space massively parallel computation

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)