Wireless random-access networks with bipartite interference graphs

arXiv (Cornell University)

Abstract

We consider random-access networks where nodes represent servers with a queue and can be either active or inactive. A node deactivates at unit rate, while it activates at a rate that depends on its queue length, provided none of its neighbors is active. We consider arbitrary bipartite graphs in the limit as the initial queue lengths become large and identify the transition time between the two states where one half of the network is active and the other half is inactive. The transition path is decomposed into a succession of transitions on complete bipartite subgraphs. We formulate a randomized greedy algorithm that takes the graph as input and gives as output the set of transition paths the network is most likely to follow. Along each path we determine the mean transition time and its law on the scale of its mean. Depending on the activation rates, we identify three regimes of behavior.

Authors 4

1. Sem C. Borst

   Eindhoven University of Technology

   Affiliation as printed

   Department of Mathematics and Computer Science , Eindhoven University of Technology , The Netherlands

2. Frank den Hollander
3. Francesca Romana Nardi

   University of Florence · Eindhoven University of Technology

   Affiliation as printed

   Department of Mathematics , University of Florence , Italy

   Department of Mathematics and Computer Science , Eindhoven University of Technology , The Netherlands

4. Matteo Sfragara Aachen Mathematical Institute

   Leiden University · Stockholm University

   Affiliation as printed

   Department of Mathematics , Stockholm University , Sweden

   Mathematical Institute , Leiden University , The Netherlands