Abstract:
We study queue-based activation protocols in random-access networks. The network is modeled as an interference graph. Each node of the graph represents a server with a queue. Packets arrive at the nodes as independent Poisson processes and have independent exponentially distributed sizes. Each node can be either active or inactive. When a node is active, it deactivates at unit rate. When a node is inactive, it activates at a rate that depends on its current queue length, provided none of its neighboring nodes is active. Thus, two nodes that are connected by a bond cannot be active simultaneously. This situation arises in random-access wireless networks where, due to interference, servers that are close to each other cannot use the same frequency band. In the limit as the queue lengths at the nodes become very large, we compute the transition time between the two states where one half of the network is active and the other half is inactive.

In the first part of the talk we focus of networks with a complete bipartite graph as interference graph. We compare the transition time with that of a network in which the activation rates are not controlled by the queue length but are externally driven, a situation that was dealt with in earlier studies. Namely, we first sandwich the transition time between that of two networks in which the activation rates are small perturbations of a certain prescribed function of the mean queue length. After that we show that, as the perturbation tends to zero, the two transition times become asymptotically similar. We identify the scale of the transition time in terms of the model parameters and we show that its law on the scale of its mean has a trichotomy depending on the aggressiveness of the activation rates.

In the second part of the talk we consider networks with a general bipartite graph as interference graph. We decompose the transition into a succession of nucleations on complete bipartite subgraphs. The total transition time depends in a delicate way on the architecture of the graph and is achieved in a greedy way. We formulate a greedy algorithm that takes the graph as input and gives as output the set of transition paths the system is most likely to follow. Each of these paths is described by a sequence of subsets of activating nodes forming complete bipartite subgraphs. Along these paths we compute both the mean transition time of the graph and the law of the transition time on the scale of its mean. Again, we notice the three regimes of behaviour depending on how the activation rate depends on the current queue length: subcritical, critical and supercritical.

About the LCN2 seminar

This talk is part of a series of seminars organized within an ongoing scientific initiative called the "Leiden Complex Networks Network" (LCN2), which aims at bringing together scientists with a common interest in both theoretical models and empirical analyses of complex networks and random graphs. The LCN2 community that is being established shares the approach of using networks for describing real-world complex systems and aims at developing related analytical and numerical methods, while also being open to other research approaches for studying complex systems. The talks are designed for a broad audience, allowing for constructive exchanges of ideas between scientists from different disciplines. During and after the talk, some drinks and simple snacks are provided.