License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2019.52
URN: urn:nbn:de:0030-drops-115487
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11548/
Frei, Fabian ;
Wada, Koichi
Efficient Circuit Simulation in MapReduce
Abstract
The MapReduce framework has firmly established itself as one of the most widely used parallel computing platforms for processing big data on tera- and peta-byte scale. Approaching it from a theoretical standpoint has proved to be notoriously difficult, however. In continuation of Goodrich et al.'s early efforts, explicitly espousing the goal of putting the MapReduce framework on footing equal to that of long-established models such as the PRAM, we investigate the obvious complexity question of how the computational power of MapReduce algorithms compares to that of combinational Boolean circuits commonly used for parallel computations. Relying on the standard MapReduce model introduced by Karloff et al. a decade ago, we develop an intricate simulation technique to show that any problem in NC (i.e., a problem solved by a logspace-uniform family of Boolean circuits of polynomial size and a depth polylogarithmic in the input size) can be solved by a MapReduce computation in O(T(n)/log n) rounds, where n is the input size and T(n) is the depth of the witnessing circuit family. Thus, we are able to closely relate the standard, uniform NC hierarchy modeling parallel computations to the deterministic MapReduce hierarchy DMRC by proving that NC^{i+1} subseteq DMRC^i for all i in N. Besides the theoretical significance, this result has important applied aspects as well. In particular, we show for all problems in NC^1 - many practically relevant ones, such as integer multiplication and division and the parity function, being among these - how to solve them in a constant number of deterministic MapReduce rounds.
BibTeX - Entry
@InProceedings{frei_et_al:LIPIcs:2019:11548,
author = {Fabian Frei and Koichi Wada},
title = {{Efficient Circuit Simulation in MapReduce}},
booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)},
pages = {52:1--52:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-130-6},
ISSN = {1868-8969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11548},
URN = {urn:nbn:de:0030-drops-115487},
doi = {10.4230/LIPIcs.ISAAC.2019.52},
annote = {Keywords: MapReduce, Circuit Complexity, Parallel Algorithms, Nick's Class NC}
}
|
Keywords: |
|
MapReduce, Circuit Complexity, Parallel Algorithms, Nick's Class NC |
|
Collection: |
|
30th International Symposium on Algorithms and Computation (ISAAC 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
28.11.2019 |
