CensorHillel, Keren ;
Parter, Merav ;
Schwartzman, Gregory
Derandomizing Local Distributed Algorithms under Bandwidth Restrictions
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. We combine bounded independence, which we show to be sufficient for some algorithms, with the method of conditional expectations and with additional machinery, to obtain the following results.
First, we show that in the Congested Clique model, which allows alltoall communication, there is a deterministic maximal independent set (MIS) algorithm that runs in O(log^2 Delta) rounds, where Delta is the maximum degree. When Delta=O(n^(1/3)), the bound improves to O(log Delta).
Adapting the above to the CONGEST model gives an O(D log^2 n)round deterministic MIS algorithm, where D is the diameter of the graph. Apart from a previous unproven claim of a O(D log^3 n)round algorithm, the only known deterministic solutions for the CONGEST model are a coloringbased O(Delta + log^* n)round algorithm, where Delta is the maximal degree in the graph, and a 2^O(sqrt(log n log log n))round algorithm, which is superpolylogarithmic in n.
In addition, we deterministically construct a (2k1)spanner with O(kn^(1+1/k) log n) edges in O(k log n) rounds in the Congested Clique model. For comparison, in the more stringent CONGEST model, where the communication graph is identical to the input graph, the best deterministic algorithm for constructing a (2k1)spanner with O(kn^(1+1/k)) edges runs in O(n^(11/k)) rounds.
BibTeX  Entry
@InProceedings{censorhillel_et_al:LIPIcs:2017:7975,
author = {Keren CensorHillel and Merav Parter and Gregory Schwartzman},
title = {{Derandomizing Local Distributed Algorithms under Bandwidth Restrictions}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {11:111:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770538},
ISSN = {18688969},
year = {2017},
volume = {91},
editor = {Andr{\'e}a W. Richa},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7975},
URN = {urn:nbn:de:0030drops79759},
doi = {10.4230/LIPIcs.DISC.2017.11},
annote = {Keywords: Local problems, congested clique, derandomization}
}
2017
Keywords: 

Local problems, congested clique, derandomization 
Seminar: 

31st International Symposium on Distributed Computing (DISC 2017)

Issue date: 

2017 
Date of publication: 

2017 