Derandomizing local distributed algorithms under bandwidth restrictions

DOI10.4230/LIPICS.DISC.2017.11MaRDI QIDQ6487482zbMATH OpenFDO

Authors Keren Censor-Hillel, M. Parter, Gregory Schwartzman

Publication date 3 February 2023

Full work available at URL https://doi.org/10.4230/LIPICS.DISC.2017.11

zbMATH Keywords

congested cliquederandomizationlocal problems

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed algorithms (68W15) Randomized algorithms (68W20)

Recommendations

• Derandomizing local distributed algorithms under bandwidth restrictions
• Derandomizing distributed algorithms with small messages: spanners and dominating set
• Distributed MIS via all-to-all communication
• Distributed Maximal Independent Set using Small Messages
• An Improved Distributed Algorithm for Maximal Independent Set

Cited in

(9)

• Derandomizing local distributed algorithms under bandwidth restrictions
• Fooling views: a new lower bound technique for distributed computations under congestion
• Bounds for the optimal decentralized access protocol in a local area network
• \((\Delta+1)\) coloring in the congested clique model
• Local computation algorithms for spanners
• Derandomizing distributed algorithms with small messages: spanners and dominating set
• Distributed MIS via all-to-all communication
• Distributed Symmetry Breaking on Power Graphs via Sparsification
• Improved distributed approximations for maximum independent set

This page was built for publication: Derandomizing local distributed algorithms under bandwidth restrictions

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