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

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

2010-08-02

arxiv.org/abs/1008.0227v1

Computer Science

Networking and Internet Architecture

12 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Fast Mixing of Parallel Glauber Dynamics and Low-Delay CSMA Scheduling does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fast Mixing of Parallel Glauber Dynamics and Low-Delay CSMA Scheduling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast Mixing of Parallel Glauber Dynamics and Low-Delay CSMA Scheduling will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-52431