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

DOI10.1109/TIT.2012.2204032zbMATH Open1364.90170arXiv1008.0227OpenAlexW2052547976MaRDI QIDQ2989744FDOQ2989744

Authors:

Publication date: 8 June 2017

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

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.

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)

Cited In (11)

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

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)