Distributed maximal matching: greedy is optimal

We study distributed algorithms that find a maximal match-ing in an anonymous, edge-coloured graph. If the edges are properly coloured with k colours, there is a trivial greedy al-gorithm that finds a maximal matching in k − 1 synchronous communication rounds. The present work shows that the greedy algorithm is optimal in the general case: if A is a deterministic distributed algorithm that finds a maximal matching in anonymous, k-edge-coloured graphs, then there is a worst-case input in which the running time of A is at least k − 1 rounds. If we focus on graphs of maximum degree ∆, it is known that a maximal matching can be found in O( ∆ + log ∗ k) rounds, and prior work implies a lower bound of Ω(polylog(∆) + log ∗ k) rounds. Our work closes the gap between upper and lower bounds: the complexity is Θ( ∆ + log ∗ k) rounds. To our knowledge, this is the first linear-in- ∆ lower bound for the distributed complexity of a classical graph problem