Abstract
This paper addresses the cornerstone family of local problems in distributed computing, and investigates the curious gap between randomized and deterministic solutions under bandwidth restrictions. Our main contribution is in providing tools for derandomizing solutions to local problems, when the n nodes can only send O(log n)-bit messages in each round of communication. Our framework mostly follows by the derandomization approach of Luby (J Comput Syst Sci 47(2):250-286, 1993) combined with the power of all to all communication. Our key results are as follows: first, we show that in the congested clique model, which allows all-to-all communication, there is a deterministic maximal independent set algorithm that runs in O(log(2) Delta) rounds, where. is the maximum degree. When Delta = O(n(1/3)), the bound improves to O(log.). In addition, we deterministically construct a (2k- 1)-spanner with O(kn(1+1/k) log n) edges in O(k log n) rounds in the congested clique model.
| Original language | English |
|---|---|
| Pages (from-to) | 349-366 |
| Number of pages | 18 |
| Journal | Distributed Computing |
| Volume | 33 |
| Issue number | 3-4 |
| DOIs | |
| Publication status | Published - 18 Apr 2020 |
Funding
We are very grateful to Mohsen Ghaffari for many helpful discussions and useful observations involving the derandomization of his MIS algorithm. Keren Censor-Hillel: Supported in part by the Israel Science Foundation (Grant 1696/14). This project has received funding from the European Union’s Horizon 2020 Research And Innovation Program under grant Agreement No. 755839. Gregory Schwartzman: This work was supported by JSPS KAKENHI Grant Numbers 19K20216 and JP18H05291.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Hardware and Architecture
- Computer Networks and Communications
- Computational Theory and Mathematics