We study distributed algorithms that find a maximal matching in an anonymous, edge-coloured graph. If the edges are properly coloured with k colours, there is a trivial greedy algorithm 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.
It turns out there is a matching lower bound: no algorithm solves this problem in o(Δ) rounds in the same model REF .
Distributed maximal matching: greedy is optimal
PODC '12
Computer Science