Derandomizing local distributed algorithms under bandwidth restrictions

DOI10.4230/LIPICS.DISC.2017.11zbMATH Open1515.68362MaRDI QIDQ6487482FDOQ6487482

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

Publication date: 3 February 2023

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

zbMATH Keywords

derandomizationlocal problemscongested clique

Mathematics Subject Classification ID

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

Cited In (7)

• 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
• Title not available (Why is that?)
• Deterministic Massively Parallel Connectivity
• Improved distributed approximations for maximum independent set
• Distributed Symmetry Breaking on Power Graphs via Sparsification

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)