Fast Mixing of Parallel Glauber Dynamics and Low-Delay CSMA Scheduling

DOI10.1109/TIT.2012.2204032MaRDI QIDQ2989744zbMATH OpenOpenAlexFDO

Authors

Publication date 8 June 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1008.0227

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Stochastic scheduling theory in operations research (90B36)

Abstract: Glauber dynamics is a powerful tool to generate randomized, approximate solutions to combinatorially difficult problems. It has been used to analyze and design distributed CSMA (Carrier Sense Multiple Access) scheduling algorithms for multi-hop wireless networks. In this paper we derive bounds on the mixing time of a generalization of Glauber dynamics where multiple links are allowed to update their states in parallel and the fugacity of each link can be different. The results can be used to prove that the average queue length (and hence, the delay) under the parallel Glauber dynamics based CSMA grows polynomially in the number of links for wireless networks with bounded-degree interference graphs when the arrival rate lies in a fraction of the capacity region. We also show that in specific network topologies, the low-delay capacity region can be further improved.

Cited in

(11)

• Queues with random back-offs
• Independent-set reconfiguration thresholds of hereditary graph classes
• Mixing time for the repeated balls into bins dynamics
• Crossover times in bipartite networks with activity constraints and time-varying switching rates
• Temporal starvation in multi-channel CSMA networks: an analytical framework
• Stability and delay of distributed scheduling algorithms for networks of conflicting queues
• Effective Wireless Scheduling via Hypergraph Sketches
• A new distributed approximation algorithm for the maximum weight independent set problem
• Delay performance in random-access networks
• Lingering issues in distributed scheduling
• Queue-based random-access algorithms: fluid limits and stability issues

This page was built for publication: Fast Mixing of Parallel Glauber Dynamics and Low-Delay CSMA Scheduling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2989744)