Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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, 49 (5). p. 1. STOC18-1–STOC18-44. doi:10.1137/18M1197655

[img]
Preview
PDF
WRAP-round-compression-parallel-matching-algorithms-Czumal-2019.pdf - Accepted Version - Requires a PDF viewer.

Download (1199Kb) | Preview
Official URL: https://doi.org/10.1137/18M1197655

Request Changes to record.

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: 5 November 2019
Dates:
DateEvent
5 November 2019Available
11 February 2019Accepted
Volume: 49
Number: 5
Page Range: p. 1
Article Number: STOC18-1–STOC18-44
DOI: 10.1137/18M1197655
Status: Peer Reviewed
Publication Status: Published
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: SIAM
RIOXX Funder/Project Grant:
Project/Grant IDRIOXX Funder NameFunder ID
International Exchanges Scheme 2013/R1[RS] Royal Societyhttp://dx.doi.org/10.13039/501100000288
Faculty AwardInternational Business Machines Corporationhttp://dx.doi.org/10.13039/100004316
EP/N011163/1[EPSRC] Engineering and Physical Sciences Research Councilhttp://dx.doi.org/10.13039/501100000266
UNSPECIFIEDAlfred P. Sloan Foundationhttp://dx.doi.org/10.13039/100000879
UNSPECIFIEDGooglehttp://dx.doi.org/10.13039/100006785
CCF-1553428National Science Foundationhttp://dx.doi.org/10.13039/100000001
P1ELP2_161820[SNSF] Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschunghttp://dx.doi.org/10.13039/501100001711
NCN2014/13/B/ST6/00770 Narodowe Centrum Naukihttp://dx.doi.org/10.13039/501100004281
677651European Research Councilhttp://viaf.org/viaf/130022607
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:
  • Publisher

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us