Wireless random-access networks with bipartite interference graphs

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.     

Redundancy scheduling with scaled Bernoulli service requirements

Queueing Systems - Redundancy scheduling has emerged as a powerful strategy for improving response times in parallel-server systems. The key feature in redundancy scheduling is replication of a job...     

The Asymptotic Workload Behavior of Two Coupled Queues

We consider a system of two coupled queues Q ₁ and Q ₂. When both queues are backlogged, they are each served at unit rate. However, when one queue empties, the service rate at the other queue increases. Thus, the two queues are coupled through the mechanism for dynamically sharing surplus service capacity. We derive the asymptotic workload behavior at Q ₁ for various scenarios where at least one of the two queues has a heavy-tailed service time distribution. First of all, we consider a situation where the traffic load at Q ₁ is below the nominal unit service rate. We show that if the service time distribution at Q ₁ is heavy-tailed, then the workload behaves exactly as if Q ₁ is served in isolation at a constant rate, which only depends on the service time distribution at Q ₂ through its mean. In addition, we establish that if the service time distribution at Q ₁ is exponential, then the workload distribution is either exponential or semi-exponential, depending on whether the traffic load at Q ₂ exceeds the nominal service rate or not. Next, we focus on a regime where the traffic load at Q ₁ exceeds the nominal service rate, so that Q ₁ relies on the surplus capacity from Q ₂ to maintain stability. In that case, the workload distribution at Q ₁ is determined by the heaviest of the two service time distributions, so that Q ₁ may inherit potentially heavier-tailed characteristics from Q ₂.