CISPA
Browse
1-s2.0-S074373152300031X-main.pdf (609.83 kB)

Efficient deterministic MapReduce algorithms for parallelizable problems.

Download (609.83 kB)
journal contribution
posted on 2024-03-18, 09:44 authored by Fabian FreiFabian Frei, Koichi Wada
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 (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 rounds, where n is the input size and is the depth of the witnessing circuit family. Thus, we are able to closely relate the standard, uniform hierarchy modeling parallel computations to the deterministic MapReduce hierarchy by proving that for all . Besides the theoretical significance, this result has important applied aspects as well. In particular, we show for all problems in —many practically relevant ones, such as integer multiplication and division, the parity function, and recognizing balanced strings of parentheses being among these—how to solve them in a constant number of deterministic MapReduce rounds.

History

Primary Research Area

  • Algorithmic Foundations and Cryptography

Journal

Journal of Parallel and Distributed Computing

Volume

177

Page Range

28-38

Publisher

Elsevier

Sub Type

  • Article

BibTeX

@article{Frei:Wada:2023, title = "Efficient deterministic MapReduce algorithms for parallelizable problems.", author = "Frei, Fabian" AND "Wada, Koichi", year = 2023, month = 7, journal = "Journal of Parallel and Distributed Computing", pages = "28--38", publisher = "Elsevier", issn = "0743-7315" }

Usage metrics

    Categories

    No categories selected

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC