Jukka Suomela (https://users.ics.aalto.fi/suomela/) is an Assistant Professor in the Department of Computer Science at Aalto University. His work focuses on the theoretical foundations of distributed computing, with particular emphasis on the concept of locality. He is a member of the EATCS council, he was recently a local co-chair of ALGO 2018, and he is the PC chair of DISC 2019.

AG 1, AG 3, AG 4, RG1, MMCI, AG 2, AG 5, SWS   Info

AG Audience

English

30 Minutes

Saarbrücken

How fast can one find a maximal matching or a maximal independent set in a distributed system? Here each node of the input graph is a computer, and each node needs to output its own part of the solution. How many communication rounds are needed in a graph with n nodes and maximum degree Δ? These are classical questions with a long history of upper and lower bounds, the first of which date back to the 1980s.

For example, for maximal matchings the current upper bounds are:

(1) O(Δ + log* n), by Panconesi & Rizzi (2001)
(2) O(log Δ + log^3 log n), by Fischer (2017) and Barenboim et al. (2012, 2016).

The running time of algorithm (1) is optimal as a function of n; there is a matching lower bound by Linial (1987, 1992). The running time of algorithm (2) is near-optimal as a function of Δ; there is an almost-matching lower bound by Kuhn et al. (2004, 2016).

However, it has been a long-standing open question whether we can achieve the best of both worlds, and find maximal matchings and maximal independents sets e.g. in time O(log Δ + log* n).

We show that the answer is no. There is no distributed algorithm that finds a maximal matching or maximal independent set in time o(Δ + log log n/log log log n). Algorithm (1) is optimal for Δ << n, and algorithm (2) is near-optimal for larger values of Δ.

(This is joint work with Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, and Mikaël Rabie. Please see https://arxiv.org/abs/1901.02441 for more details.)

Christoph Lenzen

--email hidden

passcode not visible

logged in users only