Wireless random‐access networks with bipartite interference graphs

Random Structures and Algorithms, vol. 64, pp. 814–855

Abstract

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 Eindhoven The Netherlands

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

2. Frank den Hollander Aachen Mathematical Institute

   Leiden University

   Affiliation as printed

   Mathematical Institute Leiden University Leiden The Netherlands

   Mathematical Institute, Leiden University, Leiden, The Netherlands

3. Francesca Romana Nardi

   University of Florence · Eindhoven University of Technology

   Affiliation as printed

   Department of Mathematics University of Florence Florence Italy

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

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

   Department of Mathematics, University of Florence, Florence, Italy

4. Matteo Sfragara corresponding Aachen Mathematical Institute

   Leiden University · Stockholm University

   Affiliation as printed

   Department of Mathematics Stockholm University Stockholm Sweden

   Mathematical Institute Leiden University Leiden The Netherlands

   Department of Mathematics, Stockholm University, Stockholm, Sweden

   Mathematical Institute, Leiden University, Leiden, The Netherlands