Round compression for parallel matching algorithms

For over a decade now we have been witnessing the success of massive parallel computation (MPC) frameworks, such as MapReduce, Hadoop, Dryad, or Spark. One of the reasons for their success is the fact that these frameworks are able to accurately capture the nature of large-scale computation. In particular, compared to the classic distributed algorithms or PRAM models, these frameworks allow for much more local computation. The fundamental question that arises in this context is though: can we leverage this additional power to obtain even faster parallel algorithms?

Authors

• Artur Czumaj
• Jakub Lacki
• Aleksander Madry
• Slobodan Mitrovic
• Krzysztof Onak
• Piotr Sankowski

Keywords

• maximum matching
• round compression
• vertex partitioning