CaltechAUTHORS
  A Caltech Library Service

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

Jiang, Libin and Leconte, Mathieu and Ni, Jian and Srikant, R. and Walrand, Jean (2011) Fast Mixing of Parallel Glauber Dynamics and Low-Delay CSMA Scheduling. In: 2011 IEEE Infocom Proceedings. IEEE Infocom. IEEE , Piscataway, NJ, pp. 371-375. ISBN 978-1-4244-9919-9. https://resolver.caltech.edu/CaltechAUTHORS:20120405-074732533

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20120405-074732533

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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/ 10.1109/INFCOM.2011.5935185DOIArticle
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.
Funders:
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)BBA 07-036.18
NSF1024318
NSF07-21286
NSF05-19691
NSF03-25673
Air Force Office of Scientific Research (AFOSR)FA-9550-08-1-0432
Defense Threat Reduction Agency (DTRA)HDTRA1-08-1-0016
Series Name:IEEE Infocom
Record Number:CaltechAUTHORS:20120405-074732533
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20120405-074732533
Official Citation:Libin Jiang; Leconte, M.; Jian Ni; Srikant, R.; Walrand, J.; , "Fast mixing of parallel Glauber dynamics and low-delay CSMA scheduling," INFOCOM, 2011 Proceedings IEEE , vol., no., pp.371-375, 10-15 April 2011 doi: 10.1109/INFCOM.2011.5935185 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5935185&isnumber=5934870
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:29985
Collection:CaltechAUTHORS
Deposited By: Ruth Sustaita
Deposited On:05 Apr 2012 15:58
Last Modified:04 Nov 2019 23:04

Repository Staff Only: item control page