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.)