Performance Bounds of Distributed CSMA Scheduling

CSMA-based scheduling is a recently proposed distributed scheduling algorithm that is shown to achieve the maximal throughput. Central to this algorithm is a Markov chain that produces samples from a desired distribution. In this paper, the authors discuss the relationships of the achievable throughput, queueing delay and the mixing time of the Markov chain in a variant of the algorithm. This result suggests that a small mixing time is desirable for low delay. They then discuss how a generic bound on the mixing time can be tightened in specific topologies.