The Library
Round compression for parallel matching algorithms
Tools
Tools
Tools
Czumaj, Artur, Łącki, Jakub, Mądry, Aleksander, Mitrović, Slobodan, Onak, Krzysztof and Sankowski, Piotr (2019) Round compression for parallel matching algorithms. SIAM Journal of Computing . (In Press)
|
PDF
WRAP-round-compression-parallel-matching-algorithms-Czumal-2019.pdf - Accepted Version - Requires a PDF viewer. Download (1199Kb) | Preview |
Abstract
1. Introduction. Over the last decade, massive parallelism became a major paradigm in computing, and we have witnessed the deployment of a number of very successful massively parallel computation frameworks, such as MapReduce [18, 19], Hadoop [44], Dryad [29], or Spark [45]. This paradigm and the corresponding models of computation are rather different from classical parallel algorithms models considered widely in literature, such as the PRAM model. In particular, in this paper, we study the Massive Parallel Computation (MPC)model (also known as the Massively Parallel Communication model) that was abstracted out of capabilities of existing systems, starting with the work of Karloff, Suri, and Vassilvitskii [33, 25, 8, 3, 9]. The main difference between this model and the PRAM model is that the MPC model allows for much more (in principle, unbounded) local computation. This enables it to capture a more “coarse–grained,” and thus, potentially, more meaningful aspect of parallelism. It is often possible to simulate one clock step of PRAM in a constant number of rounds on MPC [33, 25]. This implies that algorithms for the PRAM model.
| Item Type: | Journal Article | ||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||||||||||||||||||||||||||
| Divisions: | Faculty of Science > Computer Science | ||||||||||||||||||||||||||||||
| Library of Congress Subject Headings (LCSH): | Parallel algorithms, Distributed algorithms | ||||||||||||||||||||||||||||||
| Journal or Publication Title: | SIAM Journal of Computing | ||||||||||||||||||||||||||||||
| Publisher: | SIAM | ||||||||||||||||||||||||||||||
| ISSN: | 0097-5397 | ||||||||||||||||||||||||||||||
| Official Date: | 11 February 2019 | ||||||||||||||||||||||||||||||
| Dates: |
|
||||||||||||||||||||||||||||||
| Date of first compliant deposit: | 3 May 2018 | ||||||||||||||||||||||||||||||
| Status: | Peer Reviewed | ||||||||||||||||||||||||||||||
| Publication Status: | In Press | ||||||||||||||||||||||||||||||
| Publisher Statement: | “First Published in SIAM Journal of Computing in [volume and number, or year], published by the Society for Industrial and Applied Mathematics (SIAM)” and the copyright notice as stated in the article itself (e.g., “Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.”) | ||||||||||||||||||||||||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||||||||||||||||||||||||
| Copyright Holders: | © by SIAM | ||||||||||||||||||||||||||||||
| RIOXX Funder/Project Grant: |
|
||||||||||||||||||||||||||||||
| Conference Paper Type: | Paper | ||||||||||||||||||||||||||||||
| Title of Event: | The 50th Annual ACM Symposium on Theory of Computing (STOC 2018) | ||||||||||||||||||||||||||||||
| Type of Event: | Conference | ||||||||||||||||||||||||||||||
| Location of Event: | Los Angeles | ||||||||||||||||||||||||||||||
| Date(s) of Event: | 25-29 Jun 2018 | ||||||||||||||||||||||||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
