Fast mixing of parallel Glauber dynamics and low-delay CSMA scheduling

Libin Jiang, Mathieu Leconte, Jian Ni, R. Srikant, Jean Walrand

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publication2011 Proceedings IEEE INFOCOM
Pages371-375
Number of pages5
DOIs
StatePublished - Aug 2 2011
EventIEEE INFOCOM 2011 - Shanghai, China
Duration: Apr 10 2011Apr 15 2011

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X

Other

OtherIEEE INFOCOM 2011
CountryChina
CityShanghai
Period4/10/114/15/11

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Fast mixing of parallel Glauber dynamics and low-delay CSMA scheduling'. Together they form a unique fingerprint.

  • Cite this

    Jiang, L., Leconte, M., Ni, J., Srikant, R., & Walrand, J. (2011). Fast mixing of parallel Glauber dynamics and low-delay CSMA scheduling. In 2011 Proceedings IEEE INFOCOM (pp. 371-375). [5935185] (Proceedings - IEEE INFOCOM). https://doi.org/10.1109/INFCOM.2011.5935185