Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Thursday, May 24, 2018, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Manuela Fischer

Breaking the Linear-Memory Barrier in MPC: Fast MIS on Trees with Sublinear Memory per Machine

Recently, studying fundamental graph problems in the Massively Parallel Computation (MPC) framework, inspired by the MapReduce paradigm, has gained a lot of attention. A standard assumption, common to most traditional approaches, is to allow memory which is linear in the number n of nodes in the graph. However, as pointed out by Karloff et al. [SODA'10] and Czumaj et al. [arXiv:1707.03478], this might be unrealistic for real-world graphs.

We propose the study of a more practical variant of the MPC model which only requires substantially sublinear or even subpolynomial memory per machine. In contrast to the standard MPC model and also to the streaming model, in this low-memory MPC setting a single machine will never see all the nodes in the graph. We introduce a new technique to cope with this imposed locality.

In particular, we show that the Maximal Independent Set (MIS) problem can be solved efficiently, that is, in O(log³ log n) rounds, when the input graph is a tree. This substantially reduces the local memory from almost linear required by the recent O(log log n)-round MIS algorithm of Ghaffari et al. [PODC'18] to n^ε, and exponentially improves on the O(sqrt(log n) log log n)-algorithm by Lenzen and Wattenhofer [PODC'11] which can cope with sublinear memory.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login