Fast Mixing of Parallel Glauber Dynamics and Low-Delay CSMA Scheduling
Abstract
Glauber dynamics is a powerful tool to generate randomized, approximate solutions to combinatorially difficult problems. It has been recently used to design distributed CSMA 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 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.
Additional Information
© 2011 IEEE. Date of Current Version: 30 June 2011. Author names appear in the alphabetical order of the last names. Research is supported by MURI grant BAA 07-036.18, NSF Grants 1024318, 07-21286, 05-19691, 03-25673, AFOSR Grant FA-9550-08-1-0432 and DTRA Grant HDTRA1-08-1-0016.Additional details
- Eprint ID
- 29985
- DOI
- 10.1109/INFCOM.2011.5935185
- Resolver ID
- CaltechAUTHORS:20120405-074732533
- BBA 07-036.18
- Air Force Office of Scientific Research (AFOSR)
- 1024318
- NSF
- 07-21286
- NSF
- 05-19691
- NSF
- 03-25673
- NSF
- FA-9550-08-1-0432
- Air Force Office of Scientific Research (AFOSR)
- HDTRA1-08-1-0016
- Defense Threat Reduction Agency (DTRA)
- Created
-
2012-04-05Created from EPrint's datestamp field
- Updated
-
2021-11-09Created from EPrint's last_modified field
- Series Name
- IEEE Infocom