Distributed Maximal Matching: Greedy is Optimal

摘要

We study distributed algorithms that find a maximal matching in an anonymous, edge-coloured graph. If the edges are properly coloured with κ colours, there is a trivial greedy algorithm that finds a maximal matching in κ-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, κ-edge-coloured graphs, then there is a worst-case input in which the running time of A is at least κ-1 rounds. If we focus on graphs of maximum degree A, it is known that a maxima] matching can be found in Ο(Δ + log~* κ) rounds, and prior work implies a lower bound of Ω(polylog(Δ) + log~* κ) rounds. Our work closes the gap between upper and lower bounds: the complexity is Θ(Δ + log~* κ) rounds. To our knowledge, this is the first linear-in-Δ lower bound for the distributed complexity of a classical graph problem.