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

randomnesslocal modeldistributed symmetry breakingcongest modelshared randomness

Mathematics Subject Classification ID

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

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

(4)

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

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)