Efficient Circuit Simulation in MapReduce

Authors Fabian Frei, Koichi Wada



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2019.52.pdf
  • Filesize: 0.56 MB
  • 21 pages

Document Identifiers

Author Details

Fabian Frei
  • Department of Computer Science, ETH Zürich, Universitätstrasse 6, CH-8006 Zürich, Switzerland
Koichi Wada
  • Department of Applied Informatics, Hosei University, 3-7-2 Kajino, 184-8584 Tokyo, Japan

Acknowledgements

We thank the anonymous reviewers for their helpful comments.

Cite AsGet BibTex

Fabian Frei and Koichi Wada. Efficient Circuit Simulation in MapReduce. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 52:1-52:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ISAAC.2019.52

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity classes
  • Computing methodologies → MapReduce algorithms
  • Theory of computation → Circuit complexity
  • Theory of computation → MapReduce algorithms
  • Software and its engineering → Ultra-large-scale systems
Keywords
  • MapReduce
  • Circuit Complexity
  • Parallel Algorithms
  • Nick’s Class NC

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. Google Scholar
  2. D.A. Barrington. Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹. J. of Computer and System Sciences, 38:150-164, 1989. Google Scholar
  3. C.-T. Chu, S. K. Kim, Y.-A. Lin, Y. Yu, G. R. Bradski, A. Y. Ng, and K. Olukotum. Map-Reduce for machine learning on multicore. In Advances in neural information processing systems (NIPS), pages 281-288, 2006. Google Scholar
  4. T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press, 1990. Google Scholar
  5. J. Dean and S. Ghemawat. MapReduce: Simplified data processing on large clusters. Commun. ACM, 51(1):107-113, 2008. Google Scholar
  6. A. K. Farahat, A. Elgohary, A. Ghodsi, and M. S. Kamel. Distributed Column Subset Selection on MapReduce. In International Conference on Data Mining (ICDM), pages 171-180, 2013. Google Scholar
  7. J. Feldman, S. Muthukrishnan, A. Sidiropoulos, C. Stein, and Z. Svitkina. On Distributing Symmetric Streaming Computations. ACM Trans. on Algorithms, 6(4):66:1-66:15, 2010. Google Scholar
  8. B. Fish, J. Kun, Á. D. Lelker, L. Reyzin, and G. Turán. On the Computational Complexity of MapReduce. In International Symposium on Distributed Computing (DISC), pages 1-15, 2015. Google Scholar
  9. F. Frei and K. Wada. Efficient Circuit Simulation in MapReduce. Technical Report arXiv.org, cs(arXiv:1907.01624):1-20, 2019. URL: http://arxiv.org/abs/1907.01624.
  10. M. Goodrich, N. Sichinava, and Q. Zhang. Sorting, Searching, and Simulation in the MapReduce Framework. In 22nd Int. Symp. on Algorithms and Computation (ISAAC), pages 374-383, 2011. Google Scholar
  11. S. Kamara and M. Raykova. Parallel Homomorphic Encryption. In Financial Cryptography Workshops, pages 213-225, 2013. Google Scholar
  12. H. Karloff, S. Suri, and S. Vassilvitskii. A Model of Computation for MapReduce. In 21st ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 938-948, 2010. Google Scholar
  13. R. Kumar, B. Moseley, and S. Vassilvitskii. Fast Greedy Algorithms in MapReduce and Streaming. In ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pages 1-10, 2013. Google Scholar
  14. M. F. Pace. BSP vs MapReduce. In 12th Int. Conf. on Computational Science (ICCS), pages 246-255, 2012. Google Scholar
  15. A. Pietracaprina, G. Pucci, M. Riondato, F. Silvestri, and E. Upfal. Space-Round Tradeoffs for MapReduce Computations. In 26th ACM Int. Conf. on Supercomputing (ICS), pages 235-244, 2012. Google Scholar
  16. T. Roughgarden, S. Vassilvitskii, and J. R. Wang. Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation). Journal of the ACM (JACM), 65(6):41:1-66:24, 2018. Google Scholar
  17. A. D. Sarma, F. N. Afrati, S. Salihoglu, and J. D. Ullman. Upper and Lower Bounds on the Cost of a Map-Reduce Computation. In Proceedings of the VLDB Endowment (PVLDB), pages 277-288, 2013. Google Scholar
  18. A. Tada, M. Migita, and R. Nakamura. Parallel Topological Sorting Algorithm. J. of the Information Processing Society of Japan (IPSJ), 45(4):1102-1111, 2004. Google Scholar
  19. T. White. Hadoop: The Definitive Guide, 4th edition. O'Reilly, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail