Survey on large deviation bounds of queuing delay in CSMA scheduling

Question

I am trying to do some literature survey on the theoretical guarantees in uplink scheduling algorithms. I found there exist a series of papers from UIUC and UC Berkeley by L.Jiang, J. Walrand, R. Srikant and others. These works mostly analyse the stability and sometimes delay of CSMA\adaptive CSMA in large scale networks using Markov chain and Mixing time techniques. The most exciting work seems to be $[1]$, where the authors derive polynomial upper bound on the average queue length in large scale networks. But the large deviation bounds are not present in their work. Any direction to the latest literature in this specific area will help me proceed quickly with my research. Thanks in advance.

$[1]$ Jiang, Libin, et al. "Fast mixing of parallel Glauber dynamics and low-delay CSMA scheduling." Information Theory, IEEE Transactions on 58.10 (2012): 6541-6555.

Answer 1

I am not aware of any result on the large deviation bounds you mention, but you may want to start digging in the following article (and references therein), which offers a survey of the various model that have been introduced in literature to study the performance of CSMA-like algorithms:

S.-Y. Yun, Y. Yi, J. Shin, and D.Y. Eun. Optimal CSMA: A survey. In 2012
IEEE International Conference on Communication Systems (ICCS), pages
199–204. IEEE, 2012.

Another starting point for your research could be the PhD thesis of Niek Bouman "Queue-based random access in wireless networks" and/or his publications (and references therein) co-authored with S.C. Borst and J.S.H. van Leeuwaarden.