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

Glauber dynamics is a powerful tool to generate randomized, approximate solutions to combinatorially difficult problems. It has been recently used to design distributed carrier-sense multiple-access (CSMA) scheduling algorithms for multihop wireless networks. In this paper, we derive bounds on the mixing time of a generalization of Glauber dynamics where multiple links update their states in parallel and the fugacity of each link can be different. The results are 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. Other versions of adaptive CSMA can be analyzed similarly. We also show that in specific network topologies, the low-delay capacity region can be further improved.

• Publication year

  2010

• Venue

  IEEE Transactions on Information Theory

• Publication date

  2010-08-02

• Fields of study

  Computer Science, Engineering

• Identifiers
  DOI 10.1109/TIT.2012.2204032arXiv 1008.0227
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Hardness of Low Delay Network Scheduling

  2011cited by this paper
• Improved bounds on the throughput efficiency of greedy maximal scheduling in wireless networks

  2011cited by this paper
• Delay performance of CSMA in networks with bounded degree conflict graphs

  2011cited by this paper
• Fast mixing of parallel Glauber dynamics and low-delay CSMA scheduling

  2011cited by this paper
• Delay performance of CSMA policies in multihop wireless networks: A new perspective

  2010cited by this paper
• On the design of efficient CSMA algorithms for wireless networks

  2010cited by this paper
• Delay optimal queue-based CSMA

  2010cited by this paper
• The Optimality of Two Prices: Maximizing Revenue in a Stochastic Communication System

  2010cited by this paper
• Computational Transition at the Uniqueness Threshold

  2010cited by this paper
• Convergence and stability of a distributed CSMA algorithm for maximal network throughput

  2009cited by this paper
• Distributed Random Access Algorithm: Scheduling and Congestion Control

  2009cited by this paper
• Network adiabatic theorem: an efficient randomized protocol for contention resolution

  2009influential reference
• Q-CSMA: Queue-Length-Based CSMA/CA Algorithms for Achieving Maximum Throughput and Low Delay in Wireless Networks

  2009influential reference
• Distributed CSMA/CA algorithms for achieving maximum throughput in wireless networks

  2009influential reference
• A distributed CSMA algorithm for throughput and utility maximization in wireless networks

  2008influential reference
• Maximizing Utility via Random Access without Message Passing

  2008cited by this paper
• Sufficient rate constraints for QoS flows in ad-hoc networks

  2007cited by this paper
• Back-of-the-Envelope Computation of Throughput Distributions in CSMA Wireless Networks

  2007cited by this paper
• Rapid mixing of Gibbs sampling on graphs that are sparse on average

  2007cited by this paper
• Counting independent sets up to the tree threshold

  2006cited by this paper
• Throughput modelling and fairness issues in CSMA/CA based ad-hoc networks

  2005cited by this paper
• A general lower bound for mixing of single-site dynamics on graphs

  2005cited by this paper
• A Note on the Glauber Dynamics for Sampling Independent Sets

  2001cited by this paper
• On Markov Chains for Independent Sets

  2000cited by this paper
• Lectures on Glauber dynamics for discrete spin models

  1999cited by this paper
• Path coupling: A technique for proving rapid mixing in Markov chains

  1997cited by this paper
• Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks

  1990cited by this paper
• Throughput Analysis in Multihop CSMA Packet Radio Networks

  1987cited by this paper
• Data Networks

  1986cited by this paper

• Consensus-based Decentralized Multi-agent Reinforcement Learning for Random Access Network Optimization

  2025cites this paper
• Stirring the Data Pot: Shuffling Data in Networks for Fast Decentralized Learning

  2025cites this paper
• Sensing-Assisted Adaptive Channel Contention for Mobile Delay-Sensitive Communications

  2024cites this paper
• Multicoloured Hardcore Model: Fast Mixing and Its Applications as a Scheduling Algorithm

  2024cites this paper
• The power of an adversary in Glauber dynamics

  2023cites this paper
• Low-complexity scheduling algorithms with constant queue length and throughput guarantees

  2022cites this paper
• Fresh-CSMA: A Distributed Protocol for Minimizing Age of Information

  2022cites this paper
• Adaptive CSMA scheduling algorithm for queuing delay enhancement and energy optimization

  2022cites this paper
• Adaptive CSMA for Decentralized Scheduling of Multi-Hop Networks With End-to-End Deadline Constraints

  2021cites this paper
• A Queue-Length Based Approach to Metropolized Hamiltonians for Distributed Scheduling in Wireless Networks

  2020cites this paper
• A Novel Medium Access Control Algorithm for Ad Hoc Networks Based on Ising Model

  2020cites this paper
• Mixing time for the Repeated Balls into Bins dynamics

  2020cites this paper
• Age of Information in Random Access Channels

  2020cites this paper
• Crossover times in bipartite networks with activity constraints and time-varying switching rates

  2019cites this paper
• Age of Information in Random Access Channels

  2019cites this paper
• Aggregated Throughput Prediction for Collated Massive Machine-Type Communications in 5G Wireless Networks

  2019cites this paper
• EMIT: An Efficient MAC Paradigm for the Internet of Things

  2019cites this paper
• A Decentralized Medium Access Protocol for Real-Time Wireless Ad Hoc Networks With Unreliable Transmissions

  2018cites this paper
• Effective Wireless Scheduling via Hypergraph Sketches

  2018cites this paper
• Node-Based Distributed Channel Access With Enhanced Delay Characteristics

  2018influential citation
• Optimal CSMA scheduling with dual access probability for wireless networks

  2018cites this paper
• Hierarchical scheduling algorithms with throughput guarantees and low delay

  2018influential citation
• I-CSMA: A Link-Scheduling Algorithm for Wireless Networks Based on Ising Model

  2018cites this paper
• Dynamic network formation

  2018cites this paper
• Completely Uncoupled Algorithms for Network Utility Maximization

  2018cites this paper
• A novel queue-length-based CSMA algorithm with improved delay characteristics

  2017influential citation
• Universal Framework for Wireless Scheduling Problems

  2017cites this paper
• Efficient CSMA Using Regional Free Energy Approximations

  2017influential citation
• Throughput Optimal Decentralized Scheduling of Multi-Hop Networks with End-to-End Deadline Constraints: II Wireless Networks with Interference

  2017cites this paper
• Improving the queue size and delay performance with the I-CSMA link scheduling algorithm

  2017cites this paper
• Advances in Multi-Channel Resource Allocation: Throughput, Delay, and Complexity

  2016cites this paper
• Efficient CSMA based on Kikuchi approximation

  2016cites this paper
• Adaptive CSMA Under the SINR Model: Efficient Approximation Algorithms for Throughput and Utility Maximization

  2016influential citation
• A High-Order Markov-Chain-Based Scheduling Algorithm for Low Delay in CSMA Networks

  2016cites this paper
• EMIT: An efficient MAC paradigm for the Internet of Things

  2016cites this paper
• Reciprocity and Efficiency in Peer Exchange of Wireless Nodes Through Convex Optimization

  2016cites this paper
• Distributed Medium Access for Camera Sensor Networks: Theory and Practice

  2016cites this paper
• A node-based CSMA algorithm for improved delay performance in wireless networks

  2016influential citation
• Throughput Optimal Decentralized Scheduling of Multihop Networks With End-to-End Deadline Constraints: Unreliable Links

  2016cites this paper
• An antithetic coupling approach to multi-chain based CSMA scheduling algorithms

  2016cites this paper
• Independent Set Reconfiguration Thresholds of Hereditary Graph Classes

  2016cites this paper
• Multiple access control in wireless networks

  2016cites this paper
• On the Interaction of Information and Decisions in Dynamic Networked Systems.

  2016influential citation
• A New Distributed Approximation Algorithm for the Maximum Weight Independent Set Problem

  2016cites this paper
• Distributed Medium Access Over Time-Varying Channels

  2016cites this paper
• Delay Optimal CSMA With Linear Virtual Channels Under a General Topology

  2016cites this paper
• Speeding up Glauber Dynamics for Random Generation of Independent Sets

  2015influential citation
• Achieving Optimal Throughput Utility and Low Delay With CSMA-Like Algorithms: A Virtual Multichannel Approach

  2015cites this paper
• Decentralized throughput maximizing policies for deadline-constrained wireless networks

  2015cites this paper
• Capacity Achieving Distributed Scheduling With Finite Buffers

  2015cites this paper
• A common information-based multiple access protocol achieving full throughput

  2015influential citation
• Complexity Analysis of CSMA Scheduling via Dependencies Matrix

  2015cites this paper
• Spatio-temporal dynamics of random-access networks : an interacting particle approach

  2015cites this paper
• Temporal Starvation in CSMA Wireless Networks

  2015cites this paper
• Scheduling using interactive oracles: connection between iterative optimization and low-complexity scheduling

  2014cites this paper
• Provable per-link delay-optimal CSMA for general wireless network topology

  2014cites this paper
• Delay performance in random-access networks

  2014cites this paper
• Scheduling Using Interactive Optimization Oracles for Constrained Queueing Networks

  2014cites this paper
• Distributed Scheduling Algorithms for Crosspoint-Buffered Switches

  2014cites this paper
• Scheduling using Interactive Optimization Oracles for Constrained Queueing Networks

  2014cites this paper
• Physics-inspired methods for networking and communications

  2014cites this paper
• Optimal CSMA-based wireless communication with worst-case delay and non-uniform sizes

  2014cites this paper
• A high-order Markov chain based scheduling algorithm for low delay in CSMA networks

  2014cites this paper
• Optimal parameter selection for discrete-time throughput-optimal MAC protocols

  2014cites this paper
• Throughput analysis of CSMA wireless networks with finite offered-load

  2013cites this paper
• Delays and mixing times in random-access networks

  2013cites this paper
• Low Delay MAC Scheduling for Frequency-Agile Multi-Radio Wireless Networks

  2013cites this paper
• Scheduling strategies to mitigate the impact of bursty traffic in wireless networks

  2013influential citation
• Loss-based proportional fairness in multihop wireless networks

  2013cites this paper
• CSMA Using the Bethe Approximation: Scheduling and Utility Maximization

  2013cites this paper
• Delay Performance and Mixing Times in Random-Access Networks

  2013cites this paper
• Improving the delay performance of CSMA algorithms: A Virtual Multi-Channel approach

  2013cites this paper
• PERFORMANCE ANALYSIS OF THE CARRIER-SENSE MULTIPLE ACCESS PROTOCOL FOR FUTURE GENERATION WIRELESS NETWORKS

  2013cites this paper
• Fundamental limits of random access in wireless networks

  2013cites this paper
• Delay-oriented analysis and design of optimal scheduling algorithms

  2013influential citation
• Queue-based random access in wireless networks

  2013cites this paper
• CSMA using the Bethe approximation for utility maximization

  2013cites this paper
• The Impact of Access Probabilities on the Delay Performance of Q-CSMA Algorithms in Wireless Networks

  2013cites this paper
• Queues with random back-offs

  2013cites this paper
• Lingering issues in distributed scheduling

  2013cites this paper
• Queue-Based Random-Access Algorithms: Fluid Limits and Stability Issues

  2013cites this paper
• Delay performance in random-access grid networks

  2013cites this paper
• Exploiting the past to reduce delay in CSMA scheduling: a high-order markov chain approach

  2013influential citation
• CSMA over time-varying channels: optimality, uniqueness and limited backoff rate

  2013cites this paper
• Queuing behavior of queue-backlog-based random access scheduling in the many-channel regime

  2013influential citation
• A distributed CSMA algorithm for wireless networks based on Ising model

  2013cites this paper
• Distributed utility-optimal scheduling with finite buffers

  2012influential citation
• Stability and delay of distributed scheduling algorithms for networks of conflicting queues

  2012influential citation
• On scheduling algorithms robust to heavy-tailed traffic

  2012cites this paper
• Adaptive access and rate control of CSMA for energy, rate, and delay optimization

  2012cites this paper
• From Glauber dynamics to Metropolis algorithm: Smaller delay in optimal CSMA

  2012influential citation
• Optimal CSMA: A survey

  2012influential citation
• Effect of access probabilities on the delay performance of Q-CSMA algorithms

  2012cites this paper
• Mixing time and temporal starvation of general CSMA networks with multiple frequency agility

  2012cites this paper
• Effect of network density and size on the short-term fairness performance of CSMA systems

  2012cites this paper
• Medium Access over Time-varying Channels with Limited Sensing Cost

  2012cites this paper
• Backlog-based random access in wireless networks: Fluid limits and instability issues

  2012cites this paper
• Backlog-based random access in wireless networks: Fluid limits and instability issues

  2012cites this paper
• On reducing delay and temporal starvation of queue-length-based CSMA algorithms

  2012cites this paper
• Fast mixing of parallel Glauber dynamics and low-delay CSMA scheduling

  2011cites this paper