  Consider a wireless network where each communication link has a minimum
bandwidth quality-of-service requirement. Certain pairs of wireless links
interfere with each other due to being in the same vicinity, and this
interference is modeled by a conflict graph. Given the conflict graph and link
bandwidth requirements, the objective is to determine, using only localized
information, whether the demands of all the links can be satisfied. At one
extreme, each node knows the demands of only its neighbors; at the other
extreme, there exists an optimal, centralized scheduler that has global
information. The present work interpolates between these two extremes by
quantifying the tradeoff between the degree of decentralization and the
performance of the distributed algorithm. This open problem is resolved for the
primary interference model, and the following general result is obtained: if
each node knows the demands of all links in a ball of radius $d$ centered at
the node, then there is a distributed algorithm whose performance is away from
that of an optimal, centralized algorithm by a factor of at most
$(2d+3)/(2d+2)$. The tradeoff between performance and complexity of the
distributed algorithm is also analyzed. It is shown that for line networks
under the protocol interference model, the row constraints are a factor of at
most $3$ away from optimal. Both bounds are best possible.
