# Linear-in-Δ lower bounds in the LOCAL model

Distributed Computing · volume 30, issue 5, pages 325–338, 2017 ·

# Abstract

By prior work, there is a distributed graph algorithm that finds a maximal fractional matching (maximal edge packing) in $O(\Delta)$ rounds, independently of $n$; here $\Delta$ is the maximum degree of the graph and $n$ is the number of nodes in the graph. We show that this is optimal: there is no distributed algorithm that finds a maximal fractional matching in $o(\Delta)$ rounds, independently of $n$. Our work gives the first linear-in-$\Delta$ lower bound for a natural graph problem in the standard LOCAL model of distributed computing—prior lower bounds for a wide range of graph problems have been at best logarithmic in $\Delta$.