Florian Simatos
email: f.simatos@tue.nl

Niek Bouman
email: n.bouman@tue.nl

Sem Borst

Lingering issues in distributed scheduling

Keywords: Delay performance, Distributed scheduling algorithms, Heavy traffic scaling, Wireless networks Mathematics Subject Classification 68M20, 90B18, 90B22

Recent advances have resulted in queue-based algorithms for medium access control which operate in a distributed fashion, and yet achieve the optimal throughput performance of centralized scheduling algorithms. However, fundamental performance bounds reveal that the "cautious" activation rules involved in establishing throughput optimality tend to produce extremely large delays, typically growing exponentially in 1/(1-ρ), with ρ the load of the system, in contrast to the usual linear growth. Motivated by that issue, we explore to what extent more "aggressive" schemes can improve the delay performance. Our main finding is that aggressive activation rules induce a lingering effect, where individual nodes retain possession of a shared resource for excessive lengths of time even while a majority of other nodes idle. Using central limit theorem type arguments, we prove that the idleness induced by the lingering effect may cause the delays to grow with 1/(1-ρ) at a quadratic rate. To the best of our knowledge, these are the first mathematical results illuminating the lingering effect and quantifying the performance impact. In addition extensive simulation experiments are conducted to illustrate and validate the various analytical results.

schemes cannot be expected to achieve low delay in arbitrary topologies (unless P equals NP), roughly meaning that the required number of calculations prior to any transmission is super-polynomial in the number of nodes. However, this notion of delay is a transient one, and it is not exactly clear what the implications are for expected queue lengths or delays in specific networks, if any.

Performance upper bounds in [START_REF] Jiang | Fast mixing of parallel glauber dynamics and low-delay CSMA scheduling[END_REF][START_REF] Jiang | Stability and delay of distributed scheduling algorithms for networks of conflicting queues[END_REF] show that for sufficiently low load the delay only grows polynomially with the number of nodes in bounded-degree interference graphs. Similar upper bounds are presented in [START_REF] Subramanian | Delay performance of CSMA in networks with bounded degree conflict graphs[END_REF] for bounded-degree conflict graphs with low load.

Performance lower bounds in [START_REF] Bouman | Achievable delay performance in CSMA networks[END_REF] indicate that the "cautious" back-off functions involved in establishing maximum stability tend to produce extremely large delays, typically growing exponentially in 1/(1-ρ), with ρ the load of the system, in contrast to the usual linear growth. More specifically, the bounds show that the expected queue lengths grow as ψ -1 (1-ρ) as ρ ↑ 1. Here ψ -1 represents the inverse of the (decreasing) function ψ, specifying the probability of a node entering a back-off as a function of its current queue length. The bounds may be explained by noting that the queue lengths govern the fraction of back-off time through the function ψ. Since the fraction of back-off time cannot exceed the surplus capacity in order for the system to be stable, however, it is ultimately the amount of surplus 1-ρ that dictates the queue lengths through the function ψ -1 . We note that maximum stability has been established under the condition that the function ψ(a) decays (no faster than) inverselogarithmically as a → ∞, i.e., ψ(a) ∼ 1/ log a. This entails that ψ -1 (s) grows (no slower than) exponentially in 1/s as s ↓ 0, yielding the stated exponential growth of ψ -1 (1-ρ) in 1/(1-ρ) as ρ ↑ 1.

The above lower bounds suggest that the delay performance may be improved when the function ψ decays faster, e.g., inverse-polynomially: ψ(a) ∼ a -β , with β > 0, so that ψ -1 (s) ∼ s -1/β as s ↓ 0. The larger the value of the exponent β, the slower the growth of ψ -1 (1-ρ) ∼ (1-ρ) -1/β as ρ ↑ 1. In particular, it might seem plausible that for β ≥ 1, the expected queue lengths will only exhibit the usual linear growth in 1/(1-ρ) as ρ ↑ 1. Note that a larger value of β means that a node is more "aggressive", in the sense that it is less likely to enter a back-off and more inclined to hold on to the medium, and hence the coefficient β will be referred to as the aggressiveness parameter. It is worth mentioning that maximum stability for the above back-off functions is not guaranteed by existing results, which do not apply for any β > 0. In fact, for β > 1, maximum stability has been shown not to hold in certain topologies [START_REF] Ghaderi | Backlog-based random-access in wireless networks: fluid limits and instability issues[END_REF].

In the present paper we aim to gain fundamental insight into the extent that a larger aggressiveness parameter can improve the delay performance. Our main finding is that, for large values of β, a lingering effect can cause the mean stationary delay to increase in heavy traffic as 1/(1-ρ) 2 . In the infinitely persistent case, β = +∞, we present a complete analysis and prove that the heavy-traffic stationary delay scales as 1/(1-ρ) 2 . In the strongly persistent case, β ∈ (1, ∞), we show that the system's behavior is roughly similar to the behavior in the infinitely persistent case, supporting our claim that the delay scales as 1/(1-ρ) 2 in this case as well. In the weakly persistent case, β < 1, fundamentally different behavior may emerge, requiring significant additional developments which go beyond the scope of the present paper.

For transparency, we focus on the simplest topology where the lingering effect occurs. This topology, described in later sections, may at first sight seem restrictive in view of recent results [START_REF] Jiang | Distributed random access algorithm: scheduling and congestion control[END_REF][START_REF] Rajagopalan | Network adiabatic theorem: an efficient randomized protocol for content resolution[END_REF][START_REF] Shah | Randomized scheduling algorithm for queueing networks[END_REF] which apply to general topologies. We believe, however, that our results give insight into more general situations as will be discussed in Sect. 6.

Illustrative example

Consider a network consisting of four queues which are split into two groups, in such a way that if any queue of one group is transmitting a packet, no queue of the other group may transmit, and vice versa. A group is said to be active if one of its queues is transmitting a packet, and a queue is said to be active if it belongs to the active group. The other group and queues are said to be inactive.

In our model, time is slotted and active queues adhere to the following algorithm: after each transmission, each active queue flips a coin and advertizes a release with probability (1 + a) -β , with a the number of packets that this queue has to transmit and β > 0. If the two active queues advertize a release simultaneously, then active queues become inactive and vice versa: such a time is called a switching time. This simple distributed algorithm gives rise to dynamics as illustrated in Fig. 1, where the system is considered over three consecutive switching times t 1 , t 2 , and t 3 . Between switching times, the packet buffers at the active queues are drained, while packets accumulate at the inactive queues. The dynamics shown in Fig. 1 are representative of the case β > 1 where a switch does not occur until both active queues are close to being empty, see Theorem 4.1 and Corollary 5.5.

Let us now give a flavor of the lingering effect. Imagine that the two active queues start with initial queue lengths of the same order, say Q. As just mentioned, queues retain the shared resource until the time T * at which both queues are close to being empty, thus preventing other queues from activating until this time. The law of large numbers suggests that T * is of order Q (i.e., active queues are drained linearly as in Fig. 1 A sample path on the normal time scale with β = 2, representative of the case β > 1. The three boxes zoom in to show the lingering effect. One queue hovers around zero while the other queue is yet to empty, resulting in an inefficient use of the resource Fig. 1), but the central limit theorem suggests that up to time T * , the first active queue to have been completely drained will be empty of the order of √ Q units of time, while waiting for the other queue to empty. This lingering effect is illustrated in Fig. 1, which will be explained in greater detail in Sect. 3. This leads to a fraction of the slots of the order of (1/ √ Q) where the shared resource is used inefficiently. This may at first sight seem negligible when Q is large, and indeed queues seem to empty at the same time on the coarse time scale of Fig. 1. However, we will actually establish in Sects. 4 and 5 that it has a significant impact in heavy traffic, causing queue lengths to grow at a rate 1/(1 -ρ) 2 as ρ ↑ 1, instead of the optimal 1/(1 -ρ).

Organization

The remainder of the paper is organized as follows. In Sect. 2 we present a detailed model description. In Sect. 3 we provide an informal discussion of the lingering effect and explain how it leads to a growth rate 1/(1-ρ) 2 as ρ ↑ 1 of the mean stationary delay. Sect. 4 is devoted to the proof of Theorem 4.1, which is the main theoretical result of the paper, and proves this quadratic growth rate in the infinitely persistent case β = +∞. In Sect. 5 we present arguments supporting the conjecture that this quadratic growth occurs for every β ∈ (1, ∞), and not just for β = +∞. Finally, we conclude in Sect. 6 with some remarks and suggestions for further research.

Model description

Informal description

Let us now give a more precise definition of our model. As mentioned in the introduction, in order to analyze the lingering effect in the simplest possible setting, we focus on a symmetric system consisting of two groups of R ≥ 2 queues. At any given point in time, one of the groups is active while the other is inactive.

Time is slotted, and inactive queues have simple dynamics, driven by independent and identically distributed numbers of packet arrivals in each slot, so that they each simply grow according to random walks with step size distribution denoted by ξ . During each time slot, active queues increase by independent amounts distributed as ξ as well, but, if at least one packet is present at the start of the slot, then an active queue also flushes exactly one packet.

Moreover, at the end of each time slot, each active queue tosses a coin and advertizes a momentary release with probability ψ(a), with a the number of packets in the queue at the end of the time slot. This (momentary) release gives inactive queues an opportunity to become active: if all the active queues simultaneously advertize a release, then inactive queues become active, and active queues become inactive. Such a time is called a switching time. We will assume in the sequel that ψ(a) = (1+a) -β for some parameter β > 0, called the aggressiveness parameter. In particular, ψ(a) → 0 as a → +∞, and so active queues are less likely to advertize a release when they are highly loaded; this mechanism thus gives priority to highly loaded queues in a distributed fashion. Finally, there is a cost associated with advertizing a release: each time an active queue advertizes a release and is not empty, it incurs an additional increase distributed according to some random variable ζ .

This model qualitatively resembles the canonical models for queue-based medium access control mechanisms [START_REF] Bouman | Achievable delay performance in CSMA networks[END_REF][START_REF] Ni | Q-CSMA: queue length based CSMA/CA algorithms for achieving maximum throughput and low delay in wireless networks[END_REF][START_REF] Rajagopalan | Network adiabatic theorem: an efficient randomized protocol for content resolution[END_REF][START_REF] Shah | Medium access using queues[END_REF][START_REF] Shah | Randomized scheduling algorithm for queueing networks[END_REF]. The main difference with these models is that in our model, back-off periods are infinitesimally short (hence, the releases are qualified as momentary), and the jump size ζ represents the number of packets that would have arrived during a non-zero back-off period. In contrast to the discretetime model in [START_REF] Ni | Q-CSMA: queue length based CSMA/CA algorithms for achieving maximum throughput and low delay in wireless networks[END_REF][START_REF] Shah | Medium access using queues[END_REF], our back-off model shares the common feature of continuoustime models that there are no collisions. This back-off model simplifies the analysis and is possible because of the simple topology considered in our paper. The key advantage of using a discrete-time model with synchronized queues is that it avoids the complication of requiring back-off periods to overlap in order to define a switching time. Moreover, simulation experiments show that our main results extend to models with non-infinitesimal back-off periods and also behave qualitatively similarly as a continuous-time model.

Parameters and heavy-traffic regime

The model described in the previous subsection is defined through four parameters: the number R ≥ 2 of queues in each group, two integer-valued random variables ξ, ζ ∈ N = {0, 1, . . .} and a real number β ∈ (0, ∞], which defines the [0, 1]valued sequence (ψ(a), a ≥ 0) via ψ(a) = (1 + a) -β for a ≥ 0, to be understood for β = +∞ as ψ(0) = 1 and ψ(a) = 0 for a > 0. Note that only the asymptotic behavior of ψ matters, and our results could easily be extended to any ψ with a β ψ(a) → ∈ (0, ∞) as a → +∞ (when β is finite).

We assume that ξ and ζ have finite means, respectively Eξ = ρ/2 and Eζ = z, and that ξ has finite variance denoted by v = E[(ξ -ρ/2) 2 ]. It will be argued that the system is stable if and only if ρ < 1, and so we will refer to ρ as the load of the system. Note that by symmetry, each queue is active half the time, which explains the factor 2 in the definition ρ = 2Eξ of ρ.

In the sequel we will be interested in a heavy-traffic regime where the load ρ of the system increases to the critical value 1. Although we will not make this dependency explicit, we think of the random variable ξ as depending on ρ, i.e., we have a family of random variables {ξ ρ , ρ > 0} with Eξ ρ = ρ/2. With this in mind, we make a final assumption on the ξ 's: we assume that their second moment is uniformly bounded in ρ, i.e., sup ρ Eξ 2 ρ < +∞.

Formal description

Because of the symmetry of the system, we do not need to label the queues individually, but only need to keep track of the state of active and inactive queues. We will consider the system embedded at switching times, and define Q a r (k) and Q i r (k) as the numbers of packets in the r th active and inactive queue, respectively, just after the kth switch occurred. We will be interested in the Markov chain (Q(k), k ≥ 0) which we also write

as Q = (Q a , Q i ) with Q a = (Q a r , r ∈ R), Q i = (Q i r , r ∈ R), R = {1, .
. . , R}, and we reserve in the sequel bold notation for vectors (of functions or numbers).

As informally described in Sect. 2.1, the dynamics of Q in between two switching times are governed by two R-dimensional processes S = (S r , r ∈ R) and A = (A r , r ∈ R): S gives the increments of the inactive queues, while A gives the state of the active queues. The dynamics are as follows:

• The 2R processes A r , S r are independent;

• For each r ∈ R, (S r (k), k ≥ 0) is a random walk with step size distribution ξ started at 0; • For each r ∈ R, (A r (k), k ≥ 0) is a space-inhomogeneous random walk with the following dynamics: for any a ∈ N and any function f : N → [0, ∞), we have

E [ f (A r (1)) | A r (0) = a] = E f Y (a) + ζ 1 {Y (a)>0,U <ψ(Y (a))} , (1)
where Y (a) = a + ξ -1 {a>0} is the number of packets at the end of the time slot, U is uniformly distributed in [0, 1], and U , ξ , and ζ are independent.

Equation (1) describes the dynamics of an active queue and can be interpreted as follows. At each time slot, an active queue increases by ξ , and if not empty at the beginning of the time slot, flushes a packet, which brings the queue from state a to state Y (a). If U < ψ(Y (a)), then we say that the active queue advertizes a release, which thus happens with the (conditional) probability ψ(Y (a)) as described in Sect. 2.1. If at the end of the time slot the queue is not empty and it advertizes a release, i.e., Y (a) > 0 and U < ψ(Y (a)), then the active queue also incurs an additional increase by ζ .

To define the 2R-dimensional process Q = (Q a , Q i ) from S and A, it remains to adopt notation for the switching time, which we denote by T * . Thus T * is the first time at which all active queues advertize a release at the same time. Note that T * and S are independent. With these definitions, the dynamics of Q as informally described in Sect. 2.1 obey the following equation: for any q = (q a , q i ) ∈ N R × N R and any function f :

N 2R → [0, ∞), E f (Q(1)) | Q(0) = q = E f (q i + S(T * ), A(T * )) | A(0) = q a .
(

The special case β = +∞ will be of particular importance. Indeed, it can be analyzed exhaustively and we will show in Sect. 5 that it is representative of the system's behavior in the range β > 1. The fluid limits of the system for a fixed value of ρ and β = +∞ have been studied in [START_REF] Feuillet | Random capture algorithms: fluid limits and stability[END_REF], where the algorithm is referred to as the random capture algorithm. Also, when β = +∞, active queues only advertize a release when they are empty (in which case there is no additional term ζ ), and so in this case we have A(T * ) = 0 and T * = inf {k ≥ 0 : A(k) = 0}.

Notation for probabilities and expectations

Similarly as we have just done in (2), we will use in the remainder of the paper the common symbol E to denote expectation with respect to the laws of Q and (A, S). Initial conditions will be denoted by a subscript, and it should always be clear from the context whether we consider initial conditions of Q, A, or some A r (remember that S(0) is always equal to 0). For instance, (1) and ( 2) can be rewritten as follows:

E a [ f (A r (1))] = E f Y (a) + ζ 1 {Y (a)>0,U <ψ(Y (a))} and E q [ f (Q(1))] = E q a f (q i + S(T * ), A(T * )) .
The probability distributions corresponding to these various expectations are written as P a , P, P q , and P q a . We also define P ∞ with corresponding expectation E ∞ as the laws of Q and (A, S) started in the stationary distribution of Q, provided Q is positive recurrent.

When β = +∞, we see based on (2) and the fact that

A(T * ) = 0 that Q i (k) = 0 for k ≥ 1. In particular, when Q is positive recurrent, Q i (0) is P ∞ -almost surely equal to 0 and (2) therefore becomes E ∞ f (Q a (0)) = E ∞ f (S(T * )) (β = +∞). (3)
2.5 Additional notation τ r , τ max , τ (r ) , |•|, and •

In the remainder of the paper we define τ r = inf{k ≥ 0 : A r (k) = 0} as the time at which the r th active queue hits 0, τ max = max r ∈R τ r as the largest time at which an active queue hits 0 for the first time, and we let the τ (r ) 's be the order statistics of the τ r 's, i.e., τ (1) ≤ • • • ≤ τ (R) and {τ (r ) } = {τ r } (in particular τ max = τ (R) ).

Let |•| be the L ∞ norm and • be the L 1 norm, i.e., if J ≥ 1 and x ∈ R J then |x| = max j |x j | (which is just the absolute value for J = 1) and

x = |x 1 | + • • • + |x J |.

Connection with polling systems

It is worth emphasizing that we restrict the investigation in the next sections to the case of R ≥ 2 queues in each group, and exclude the case R = 1 from the analysis. Indeed, the lingering effect that we intend to investigate only occurs when there are R ≥ 2 queues in the same group.

The case R = 1 may be interpreted as a single-server two-class queueing system, where the server may switch from one class to the other after each service completion with a probability that depends on the queue length of the class that is currently being served. As a somewhat unusual feature, the queue length of the latter class increases by the random variable ζ when a switch occurs. This bears some resemblance with a polling system, when ζ is viewed as the number of arrivals during a switch-over time. It is worth observing that this switching rule does not belong to the class of branchingtype service disciplines which yield tractable joint queue length distributions in polling models. The only exception is the special case β = +∞, which corresponds to the exhaustive service discipline in polling models (with a process-level heavy-traffic analysis in [START_REF] Coffman | Polling systems with zero switchover times: a heavytraffic averaging principle[END_REF]) and the so-called random capture algorithm in [START_REF] Feuillet | Random capture algorithms: fluid limits and stability[END_REF]. In general, however, the analysis of the joint queue length process appears far from trivial, even when ζ = 0, although the aggregate queue length distribution is then fairly easy to obtain. This connection with polling systems is actually at the heart of the proof of forthcoming Lemma 4.5.

In case R ≥ 2, the system may in the same vein be interpreted as a set of R singleserver two-queue polling systems, where servers are only allowed to switch between queues in a synchronized fashion. Such models with simultaneous service of several queues and synchronized switches are natural in applications, and indeed our model has already been studied in Boon et al. [START_REF] Boon | Delays at signalized intersections with exhaustive traffic control[END_REF] to model traffic lights at intersections. The results in [START_REF] Boon | Delays at signalized intersections with exhaustive traffic control[END_REF] are in some sense complementary to ours, since the authors perform a heavy-traffic analysis when the system's parameters are such that the lingering effect does not play a role. In particular, they study cases where the delay scales as 1/(1-ρ).

These models show similarity with multiple-server polling systems, which did receive some attention, but have largely defied analysis. This offers testimony of the mathematical complexity of an exact queueing analysis of the model under consideration, and provides justification for an asymptotic investigation.

Informal discussion of the lingering effect

In Sect. 5.1 we will prove that, when β > 1, an active queue only advertizes releases when it is close to being empty. In particular, once a queue gains possession of the resource, it holds onto it, even when some or all of the other queues in the same group are empty, and it would be more efficient for the queues in the other group to receive the resource. This causes a lingering effect as discussed in Sect. 1.2 and illustrated in Fig. 1 for a scenario with R = 2, β = 2.

It may appear that the two queues in the same group drain around the same time (as can indeed be shown to be the case on a "fluid scale"). When we zoom in, however, we see that there is actually a time period where one of the queues is already empty, while the other one clings to the resource and prevents the two queues in the other group from activating. In this section we give a heuristic explanation of how this inefficient use of the resource leads to a quadratic growth of the mean stationary delay in heavy traffic. This explanation is also aimed at developing intuition and introducing the structure of the proofs in the next section. Now consider a regime in which active queues only advertize a release when they are close to empty, i.e., A(T * ) ≈ 0. Applying (2) with f (q) = q a , we obtain

E q ( Q a (1) ) = q i + E q ( S(T * ) ).
Thus in stationarity, we have

E ∞ ( Q a (0) ) = E ∞ ( Q a (1) ) = E ∞ ( Q i (0) ) + E ∞ ( S(T * ) ) = E ∞ ( A(T * ) ) + E ∞ ( S(T * ) )
the last equality following by applying (2) in stationarity and with f (q) = q i . In particular, since

A(T * ) ≈ 0, it follows that E ∞ ( Q a (0) ) ≈ E ∞ ( S(T * ) ).
Since by definition Q a (0) = A(0) and S(•) is a random walk with drift REξ independent of T * , we obtain E ∞ ( A(0) ) ≈ RE(ξ )E ∞ (T * ) and so by symmetry,

E ∞ (A 1 (0)) ≈ E(ξ )E ∞ T * . ( 4
)
The goal is now to relate T * to A 1 (0). Remember that active queues only advertize a release when they are close to empty; moreover, active queues are stable and so once all active queues are close to 0, it is only a matter of constant time for them to simultaneously advertize a release. This suggests that the switching time should occur around the largest time at which an active queue empties, i.e., this suggests the approximation T * ≈ τ max (recall that τ max and the τ r 's have been defined in Sect. 2.5). The law of large numbers combined with the central limit theorem show that τ r ≈ A r (0)/(1 -Eξ) + A r (0) 1/2 (where we neglect multiplicative constants, possibly random, appearing in front of first-or second-order terms and that do not influence the order of magnitude of the final result), which leads to the approximation

τ max ≈ |A(0)|/(1 -Eξ) + |A(0)| 1/2 . Since under P ∞ queues are symmetric, we have |A(0)| ≈ A 1 (0) + A 1 (0) 1/2 which finally leads to T * ≈ A 1 (0)/(1 -Eξ) + A 1 (0) 1/2 ,
i.e., going back to (4),

E ∞ (A 1 (0)) ≈ Eξ 1 -Eξ E ∞ (A 1 (0)) + E ∞ A 1 (0) 1/2 .
Thus upon a concentration-like result of the kind

E ∞ [ A 1 (0) 1/2 ] ≈ [E ∞ (A 1 (0))] 1/2 it is reasonable to expect 1 - Eξ 1 -Eξ E ∞ (A 1 (0)) ≈ [E ∞ (A 1 (0))] 1/2 . Since 1 -E(ξ )/(1 -Eξ) ≈ 1 -ρ this shows that E ∞ (A 1 (0)),
and hence E ∞ ( Q(0) ), should grow as 1/(1 -ρ) 2 . While admittedly crude, the above heuristic arguments provide the correct estimates, and serve as a useful guide for a rigorous proof in Sect. 4.

As reflected in the above computations, the square factor really stems from the relation T * ≈ τ (1) + |A(0)| 1/2 , i.e., T * occurs somehow long after τ [START_REF] Boon | Delays at signalized intersections with exhaustive traffic control[END_REF] , the time at which it would be optimal to switch in order to avoid inefficient use of the resource. But it is difficult to make the system switch exactly at τ [START_REF] Boon | Delays at signalized intersections with exhaustive traffic control[END_REF] in a distributed fashion, and here the penalty incurred is a square root. Interestingly, the penalty may seem negligible but this small inefficiency has a significant impact in heavy traffic.

When β = +∞ the above heuristic arguments can be made rigorous, and a complete proof is provided in the next section. When β ∈ (1, ∞), we will prove in Sect. 5.1 that active queues indeed advertize a release only when they are close to being empty, thus justifying the above intuition. More formally, we will show in Proposition 5.1 and its Corollary 5.5 that the random variable A(T * ) converges weakly to a finite random variable as the initial state blows up. We therefore conjecture that the lingering effect will make the mean stationary delay scale like 1/(1-ρ) 2 when β > 1, but a proof of that result may involve significantly more work than in the case β = +∞. We leave this issue open for future research, and present in Sect. 5.2 extensive simulation results which support this conjecture.

Full investigation of the infinitely persistent case

In the infinitely persistent case β = +∞, the system's performance and in particular the impact of the lingering effect can be analyzed rigorously. The main result of this section is given by the following theorem, which shows that the mean stationary delay grows quadratically in 1/(1-ρ) as ρ ↑ 1.

Theorem 4.1 If β = +∞, then Q is positive recurrent for ρ < 1 and 0 < lim inf ρ↑1 (1 -ρ) 2 E ∞ ( Q(0) ) ≤ lim sup ρ↑1 (1 -ρ) 2 E ∞ ( Q(0) ) < +∞. (5)
The rest of this section is devoted to the proof of Theorem 4.1, and so from now on we assume that β = +∞. Remember that in this case we have T * = inf{k ≥ 0 : A(k) = 0} and A(T * ) = 0. Moreover, in this case active queues only advertize a release when they are empty, in which case they do not incur the additional arrivals given by ζ . In particular, active queues are independent random walks with step size distribution ξ -1 and reflected at the origin. Since ξ ≥ 0, these random walks belong to the class of skip-free random walks, i.e., random walks that only decrease by -1.

In particular, it is well-known and not difficult to show that E a (τ 1 ) = a/(1 -Eξ) for any a ∈ N, a fact that will be used several times in this section.

We prove Theorem 4.1 via a series of intermediate results that justify the various approximations of the previous section. We first prove that T * ≈ τ max , i.e., the time at which the R independent random walks A r simultaneously hit 0 is close to the first time at which each process has visited 0 at least once. Lemma 4.2 Let ρ 0 < 2: then sup a,ρ E a (T * -τ max ) is finite, where the supremum is taken over a ∈ N R and ρ ≤ ρ 0 .

Proof Fix any ρ < 2, so that the active queues are stable, and T * is almost surely finite. Define the sequences (τ r,k , k ≥ 0) and (σ max,k , k ≥ 0) by induction on k as follows: for k = 0 set τ r,0 = σ max,0 = 0 and for k ≥ 0,

τ r,k+1 = min{i ≥ σ max,k : A r (i) = 0} and σ max,k+1 = max r ∈R τ r,k+1 .
Remember that (since β = +∞) T * is the first time at which all the queues are simultaneously empty, thus T * ≥ τ max = σ max,1 . If T * > σ max,1 , this means that at time σ max,1 at least one queue was not empty, and so T * will be at least as large as the first time after time σ max,1 at which every queue will have visited 0 at least once, which is by definition σ max,2 . Iterating this argument, we see that the sequence (σ max,k , k ≥ 1) is stationary (in the sense that σ max,k = σ max,k * for some finite k * and all k ≥ k * ), and that T * = σ max,k * . This can be rewritten as T * = k≥1 τ max,k with τ max,k = σ max,k -σ max,k-1 for k ≥ 1 or, since τ max,1 = τ max , as T * -τ max = k≥2 τ max,k . We now proceed to derive a stochastic upper bound on k≥2 τ max,k by using a coupling argument.

Let (X r,k , k ≥ 1, r ∈ R) and (Y r,k , k ≥ 1, r ∈ R) be two sequences of i.i.d.
random variables with common distribution the stationary distribution, say X , of the A r 's; we assume moreover that these two sequences are independent from one another and also independent from the active queues A.

For each k ≥ 1 let A r,k be a stationary version of A r such that A r,k (0) = X r,k and A r,k (i) ≥ A r (i + τ r,k ) for every i ≥ 0.
This can be done with, e.g., the usual coupling between two processes with different initial states and the same stochastic primitives; in this case, the ordering between the two processes comes from the fact that A r (τ r,k ) = 0 by definition of τ r,k .

Consider now, for r ∈ R and k ≥ 1, the random variables X r,k defined by:

X r,k = A r,k (σ max,k -τ r,k ) if σ max,k > τ r,k , Y r,k otherwise.
A moment's thought reveals that for each k ≥ 1 the random variables (X r,k , r ∈ R) are i.i.d. with common distribution X . Indeed, consider the process A r,k at the random time σ max,k -τ r,k .

If σ max,k > τ r,k , the r th active queue A r has hit 0 somewhere in the past at time τ r,k : at this time we forgot about its state by using X r,k to build A r,k , and the remaining time to go σ max,k -τ r,k depends only on the behavior of the other queues and is thus independent from A r,k . Thus in this case, considering A r,k (σ max,k -τ r,k ) amounts to consider a stationary process sampled at an independent random time, and so this random variable is indeed distributed according to X and is independent from the other queues.

If on the other hand σ max,k = τ r,k , this means that the r th active queue is one of the last queue to hit 0, and again at this time we forget about this by using Y r,k which is distributed according to X independently from everything else.

We now use again the same coupling as before, between processes sharing the same stochastic primitives, to build for each r ∈ R and k ≥ 1 a process A r,k starting at X r,k and sharing the same stochastic primitives as A r,k . This leads to a collection of processes (A r,k , r ∈ R, k ≥ 1) such that: [START_REF] Boon | Delays at signalized intersections with exhaustive traffic control[END_REF]

for each k ≥ 1, A k = (A r,k , r ∈ R)
is a stationary version of A and (2) for every k ≥ 1, i ≥ 0, and r ∈ R, it holds that A r,k (σ max,k + i) ≤ A r,k (i). In particular, τ max,k ≤ τ max,k where τ max,k = inf{i ≥ 0 : A k (i) = 0}, and so T * -τ max ≤ G-1 k=2 τ max,k , with the convention 1 2 = 0 and where G = inf{k ≥ 2 : τ max,k = 0}, which provides the desired stochastic upper bound.

To conclude the proof, it remains to show that E a ( G-1 k=2 τ max,k ) is bounded away from +∞ uniformly in ρ ≤ ρ 0 and a ∈ N R . Let X = (X 1,r , r ∈ R): then by construction of the τ max,k 's and by definition of G, G -2 is a geometric random variable with parameter P(X = 0) and conditionally on G, (τ max,k , 2 ≤ k ≤ G -1) are i.i.d. with common distribution τ max under P X ( • | X = 0). In particular,

E a G-1 k=2 τ max,k = E(G -2)E X (τ max | X = 0) = E X (τ max ) P(X = 0) . Since τ max ≤ τ 1 + • • • + τ R , E a (τ 1 ) = a/(1 -Eξ)
and X is a vector of R i.i.d. random variables with common distribution X , we finally obtain the bound

E a G-1 k=2 τ max,k ≤ R 1 -Eξ E(X ) P(X = 0) R .
This upper bound does not depend on a, and so it remains to show that its supremum over ρ ≤ ρ 0 < 2 is finite. Since X is the stationary distribution of A 1 , X is equal in distribution to X + ξ -1 {X >0} . In particular, taking the mean we obtain P(X = 0) = 1 -Eξ and so it remains to show that sup ρ≤ρ 0 EX < +∞. To compute EX , we can start from the equality E e -λX = E e -λ(X +ξ -1 {X >0} ) , which leads to

φ(λ) = ϕ(λ)(1 -e -λ )ϕ (0) ϕ(λ) -1 ,
where φ(λ) = E(e -λX ) and ϕ(λ) = E(e -λ(ξ -1) ), and we have used ϕ (0) = 1-Eξ = P(X = 0). Using EX = -φ (0), we can compute after some algebra

EX = ϕ (0) -ϕ (0) 2ϕ (0) = Eξ 2 + 2 -3Eξ 2(1 -Eξ) .
Since sup ρ≤ρ 0 Eξ 2 is finite by assumption (see the discussion at the end of Sect. 2.2), the result is finally proved.

The previous lemma justifies the approximation T * ≈ τ max , and to further control τ max , we will use that (τ r , r ∈ R) under P a is equal in distribution to (V r (a r ), r ∈ R), where (V r , r ∈ R) are i.i.d. random walks started at 0 and with step size distribution δ, equal in distribution to τ 1 under P 1 (i.e., δ is the time needed for a random walk with step size distribution ξ -1 to go from 1 to 0). Then δ has finite mean 1/(1 -Eξ) and also finite variance, which we denote by ν. To control the maximum of random walks, we will use the following result. Lemma 4.3 Let (W r , r ∈ R) be i.i.d. random walks started at 0 with step size distribution having finite mean m and finite variance w. Then for any

x = (x r , r ∈ R) ∈ N R it holds that E max r ∈R W r (x r ) ≤ m|x| + R(w|x|) 1/2 . ( 6
)
Furthermore, if the step size distribution of the W r 's is non-negative, then

E max r ∈R W r (x r ) 1/2 ≥ (m|x|) 1/2 -(w/m 3/2 )|x| -1/2 . ( 7
)
Proof Fix some x ∈ N R and for r ∈ R let Y r = (W r (x r ) -mx r )/(wx r ) 1/2 , so that EY r = 0 and E(|Y r |) ≤ (E(Y 2 r )) 1/2 = 1.
To prove the upper bound, we start from the equality max r W r (

x r ) = max r (mx r + (wx r ) 1/2 Y r ) which implies max r ∈R W r (x r ) ≤ max r ∈R mx r + (wx r ) 1/2 |Y r | ≤ m|x| + (w|x|) 1/2 Y .
Averaging on both sides yields [START_REF] Foster | A limit theorem for a branching process with state-dependent immigration[END_REF], since

E( Y ) = r E(|Y r |) ≤ R.
Let us now prove the lower bound, so assume that the step size distribution of the W r 's is non-negative. Since E(max r W r (x r ) 1/2 ) ≥ max r E(W r (x r ) 1/2 ) and max r ∈R

(mx r ) 1/2 -(w/m 3/2 )x -1/2 r ≥ (m|x|) 1/2 -(w/m 3/2 )|x| -1/2 , it is enough to show that E(W r (x r ) 1/2 ) ≥ (mx r ) 1/2 -(w/m 3/2 )x -1/2 r for each fixed r ∈ R. Let f (y) = 1 + y/2 -(1 + y) 1/2 y 2 , y ≥ -1, so that, defining y = (w/(m 2 x r )) 1/2 Y r which satisfies y ≥ -1 since W r (x r ) ≥ 0, we obtain W r (x r ) 1/2 = (wx r ) 1/2 Y r + mx r 1/2 = (mx r ) 1/2 1 + y/2 -y 2 f (y) .
Since Ey = 0, taking expectation on both sides leads to

E W r (x r ) 1/2 = (mx r ) 1/2 -(mx r ) 1/2 E(y 2 f (y)).
Since sup f = 1/2 ≤ 1 and E(y 2 ) = w/(m 2 x r ), we get the result.

We now prove that the process is Q stable for ρ < 1; moreover, we will need the fact that the mean stationary number of packets is finite.

Proposition 4.4 If ρ < 1, then Q is positive recurrent and E ∞ ( Q(0) ) < +∞.
Proof Because β = +∞, we have Q i (k) = 0 for k ≥ 1: we therefore assume without loss of generality that Q i (k) = 0 for k ≥ 0, and we only have to show that Q a is positive recurrent and has finite stationary mean. To prove Proposition 4.4, it is enough to prove that lim

K →+∞ sup q a :|q a |≥K E q |Q a (2)| -|q a | |q a | < 0, (8)
where here and in the sequel, q = (q a , 0). Indeed, this shows that |•| is a Lyapunov function, which implies positive recurrence of Q a using for instance the Foster-Lyapunov criterion. In the terminology of [START_REF] Gamarnik | Validity of heavy traffic steady-state approximation in generalized Jackson networks[END_REF], it also shows that |•| is a geometric Lyapunov function, and Theorem 5 in [START_REF] Gamarnik | Validity of heavy traffic steady-state approximation in generalized Jackson networks[END_REF] states that [START_REF] Georgiadis | Resource allocation and cross-layer control in wireless networks[END_REF] implies that

E ∞ [|Q a (0)|],
and in particular E ∞ ( Q(0) ), is finite. Thus we only have to prove [START_REF] Georgiadis | Resource allocation and cross-layer control in wireless networks[END_REF]. By (3) and the fact that A(T * ) = 0, we obtain

E q |Q a (1)| = E q a (|S(T * )|).
Since S and T * are independent, [START_REF] Foster | A limit theorem for a branching process with state-dependent immigration[END_REF] gives that

E a (|S(T * )|) ≤ E(ξ )E a (T * ) + Rv 1/2 E a ((T * ) 1/2 ),
for any a ∈ N R (recall that v is the variance of ξ , assumed to be finite). Thus after rearranging the terms and using Jensen's inequality, we end up with the bound

E q |Q a (1)| -|q a | ≤ -(1 -ρ)E q a (T * ) + (q a ) + Rv 1/2 [E a (T * )] 1/2 , ( 9
)
where (a) = E a ((1 -Eξ)T * -|A(0)|). We now argue that (a) ≤ c[E a (T * )] 1/2 for some finite constant c independent of a. By Lemma 4.2, we have E a (T * ) ≤ E a (τ max ) + c for some finite constant c independent of a. Further, since τ max is equal in distribution to max r V r (a r ), [START_REF] Foster | A limit theorem for a branching process with state-dependent immigration[END_REF] gives (recall that ν is the variance of the step size distribution of the V r 's, which has mean 1/(1-Eξ))

E a (T * ) ≤ |a| 1 -Eξ + Rν 1/2 |a| 1/2 + c , which can be rewritten as (a) ≤ R(1 -Eξ)ν 1/2 |a| 1/2 + c (1 -Eξ).
Since T * ≥ τ r and E a r τ r = a r /(1 -Eξ), we obtain |a| ≤ (1 -Eξ)E a (T * ) which, together with the previous inequality, implies the existence of the desired constant c such that (a

) ≤ c[E a (T * )] 1/2 . Defining (a) = (1 -ρ)E a T * -(c + Rv 1/2 ) E a T * 1/2 , ( 10
)
we can rewrite ( 9) as E q |Q a (1)|) -|q a | ≤ -(q a ). Using the Markov property and (2), this gives

E q |Q a (2)| -|q a | ≤ -E q a (q a ) + (S(T * )) . ( 11
)
When |q a | is large, at least one of the R coordinates of q a must be large. Since E a (T * ) ≥ a r /(1 -Eξ), it is not hard to show that lim

K →+∞ inf q a :|q a |≥K E q a ( (q a ) + (S(T * ))) |q a | > 0,
which completes the proof of the result.

We need a last technical lemma before proving Theorem 4.1.

Lemma 4.5 Let ⇒ denote weak convergence under P ∞ as ρ ↑ 1. Then for any r ∈ R, Q a r (0) ⇒ +∞. In particular, τ max ⇒ +∞ and

lim inf ρ↑1 E ∞ |Q a (0)| 1/2 -(Q a 1 (0)) 1/2 > 0.
Proof Fix some r ∈ R, and let us first prove that Q a r (0) ⇒ +∞. The proof relies on a coupling argument between the system in the normal time scale (i.e., not embedded at switching epochs) and a polling system. So let Q a (t) and Q i (t) be the number of packets in the r th active and inactive queues, respectively, at the beginning of the tth time slot. Furthermore, assume without loss of generality that Q i (0) = 0.

We build a process (Q a , Q i ) that will be closely related to a polling system and which will provide a lower bound on ( Q a , Q i ). We explain how to build (Q a , Q i ) on {0, . . . , T * }, the construction can be repeated by induction between any two switching times:

• At time 0 we have Q a (0) ≤ Q a (0) and Q i (0) = 0; • The two processes ( Q a , Q i ) and (Q a , Q i ) share the same stochastic primitives until Q a hits 0 at time τ = inf{t ≥ 0 : Q a (t) = 0}. Since Q a (0) ≤ Q a (0), we have in particular τ ≤ T * ; • On {τ , . . . , T * -1}, the two processes Q a and Q i are frozen, i.e., Q a (t) = Q a (τ ) and Q i (t) = Q i (τ ) for τ ≤ t < T * ; • At time T * the active and inactive queues are switched for both ( Q a , Q i ) (by definition of T * ) and (Q a , Q i ) (by construction).
Since Q i and Q i share the same stochastic primitives up to time τ , we have Q i (τ ) = Q i (τ ); since Q i is frozen afterward while Q i continues to increase, and the active and inactive queues are switched at time T * , we obtain Q a (T * ) ≤ Q a (T * ). Since moreover Q i (1) = 0, it follows by induction that Q a (k) ≤ Q a (k) for every k ≥ 0. Let τ (k) be the kth time at which Q a hits 0 and T * (k) be the kth switching time: then

Q a r (k) = Q a (T * (k)) ≥ Q a (T * (k)) = Q i (τ (k)) (12)
(the last equality is only valid

if τ (k) < T * (k); if τ (k) = T * (k) then Q i (τ (k))
is to be understood as the value of the inactive queue just before the switch occurs). Finally, we note that by construction, the process (Q i (τ (k)), k ≥ 0) is equal in distribution to the process (P(γ (k)), k ≥ 0) where:

• P(t) for t ≥ 0 is the total number of packets in the kth time slot of a two-queue polling system, operating under the exhaustive service discipline, with zero switchover time, where time is discrete and arrivals in each time slot in each queue are distributed according to ξ ; • γ (k) is the kth time at which a queue empties.

Next, we note that the process (P(γ (k)), k ≥ 0) is a branching process with immigration at 0, the offspring distribution η of the branching process being equal in distribution to S 1 (τ 1 ) under P 1 , i.e., η is the number of packets arriving in the inactive queue during the time needed to make the state of the active queue decrease by one. This property can be seen directly from the system's dynamics; at a higher level, it also comes from the fact that the exhaustive service discipline satisfies the well-known branching property [START_REF] Resing | Polling systems and multitype branching processes[END_REF]. In any case, we can adapt the proof of [START_REF] Foster | A limit theorem for a branching process with state-dependent immigration[END_REF] to show that the stationary distribution of (P(γ (k)), k ≥ 0) converges weakly to +∞ as ρ ↑ 1. In view of [START_REF] Jiang | Stability and delay of distributed scheduling algorithms for networks of conflicting queues[END_REF] this shows that Q a r (0) ⇒ +∞, which concludes the proof of the first claim of the lemma. The second claim is then immediate, and so it remains to prove the third and last claim. Using

a 1/2 -b 1/2 = (a -b)/(a 1/2 + b 1/2 ), we can rewrite |Q a (0)| 1/2 -(Q a 1 (0)) 1/2 = |Q a (0)| -Q a 1 (0) (Q a 1 (0) + 1) 1/2 × (Q a 1 (0) + 1) 1/2 |Q a (0)| 1/2 + (Q a 1 (0)) 1/2 ,
which by (3), is equal in distribution to

|S(T * )| -S 1 (T * ) (S 1 (T * ) + 1) 1/2 × (S 1 (T * ) + 1) 1/2 |S(T * )| 1/2 + (S 1 (T * )) 1/2 = max r ∈R S r (T * ) -S 1 (T * ) (S 1 (T * ) + 1) 1/2 × (S 1 (T * ) + 1) 1/2 |S(T * )| 1/2 + (S 1 (T * )) 1/2 .
Since S and T * are independent and T * ⇒ +∞ (as a result of the second claim and T * ≥ τ max ), the law of large numbers implies that

(S 1 (T * ) + 1) 1/2 |S(T * )| 1/2 + (S 1 (T * )) 1/2 ⇒ 1 2 ,
while the central limit theorem implies that

S r (T * ) -S 1 (T * ) (S 1 (T * ) + 1) 1/2 = S r (T * ) -T * Eξ (T * ) 1/2 - S 1 (T * ) -T * Eξ (T * ) 1/2 × S 1 (T * ) + 1 T * -1/2
converges weakly to the difference of two independent normal random variables. Gathering these results, we obtain the weak convergence of |Q a (0

)| 1/2 -(Q a 1 (0)) 1/2
toward a non-negative random variable with strictly positive mean. Invoking Fatou's lemma completes the proof.

Remark Although the stationary distribution of the process P introduced in the previous proof scales like 1/(1-ρ) as ρ ↑ 1, using similar techniques as in [START_REF] Foster | A limit theorem for a branching process with state-dependent immigration[END_REF] one can show that the stationary distribution P(γ (∞)) of the embedded process (P(γ (k)), k ≥ 0) scales like 1/(1-ρ) U with U a random variable uniformly distributed on (0, 1), in the sense that log P(γ (∞))/ log(1/(1 -ρ)) converges weakly to U as ρ ↑ 1.

Proof of Theorem 4.1 Since β = +∞, we have

E ∞ ( Q(0) ) = E ∞ ( A(0) ) = RE ∞ (A 1 (0)
) and so we only need to prove the two inequalities lim sup

ρ↑1 (1 -ρ) 2 E ∞ (A 1 (0)) < +∞ and lim inf ρ↑1 (1 -ρ)E ∞ A (0) 1/2 > 0. ( 13
)
Indeed, the first one directly implies the upper bound in ( 5) while the second one implies the corresponding lower bound by Jensen's inequality.

Proof of the first inequality in [START_REF] Jiang | Distributed random access algorithm: scheduling and congestion control[END_REF] Starting from (4), using that E a (τ 1 ) = a/(1-Eξ), subtracting on both sides E(ξ )E ∞ (τ 1 ) (for this precise operation we need the finiteness of the stationary first moment proved in Proposition 4.4, to avoid an indetermination of the kind ∞ -∞) and dividing by Eξ , we end up with

1 Eξ 1 - Eξ 1 -Eξ E ∞ (A 1 (0)) = E ∞ T * -τ 1 .
Then, adding and subtracting τ max in the right hand side, and using that Eξ = ρ/2, we obtain

g ρ (1 -ρ)E ∞ (A 1 (0)) = E ∞ (τ max -τ 1 ) + E ∞ T * -τ max , with g ρ = 4/(ρ(2 -ρ))
. Thus in view of Lemmas 4.2 and 4.5, to prove the first inequality in [START_REF] Jiang | Distributed random access algorithm: scheduling and congestion control[END_REF] we only have to show that lim sup

ρ↑1 E ∞ (τ max -τ 1 ) [E ∞ (A 1 (0))] 1/2 < +∞. ( 14
)
Applying [START_REF] Foster | A limit theorem for a branching process with state-dependent immigration[END_REF] to τ max under P a (equal in distribution to max r V r (a r )), we obtain the inequality E a (τ max -τ 1 ) ≤ (|a|a 1 )/(1 -Eξ) + Rν 1/2 |a| 1/2 . Integrating over the stationary distribution of Q and using Jensen's inequality, we obtain

E ∞ (τ max -τ 1 ) ≤ 1 1 -Eξ E ∞ (|A(0)| -A 1 (0)) + Rν 1/2 [E ∞ (A 1 (0))] 1/2 .
In particular, to prove [START_REF] Marbach | A backlog-based CSMA mechanism to achieve fairness and throughputoptimality in multihop wireless networks[END_REF] it is enough to show that lim sup

ρ↑1 E ∞ (|A(0)| -A 1 (0)) [E ∞ (A 1 (0))] 1/2 < +∞. ( 15
)
We have already shown in the proof of Proposition 4.4 that

E ∞ (|A(0)|) = E ∞ |S(T * )| ≤ E(ξ )E ∞ (T * ) + Rv 1/2 E ∞ (T * ) 1/2 ,
and since

E ∞ (A 1 (0)) = E(ξ )E ∞ (T * ) this gives E ∞ (|A(0)| -A 1 (0)) ≤ Rv 1/2 [E ∞ (A 1 (0))/Eξ ] 1/2 .
This proves [START_REF] Modiano | Maximizing throughput in wireless networks via gossiping[END_REF] which completes the proof of the first inequality in [START_REF] Jiang | Distributed random access algorithm: scheduling and congestion control[END_REF].

Proof of the second inequality in [START_REF] Jiang | Distributed random access algorithm: scheduling and congestion control[END_REF] We have

E ∞ (Q a 1 (0)) 1/2 = E ∞ (S 1 (T * )) 1/2 ≥ E ∞ (S 1 (τ max )) 1/2 .
Applying (7) (with R = 1) to S 1 (τ max ) by using the independence between S 1 and τ max , we obtain

E ∞ (Q a 1 (0)) 1/2 ≥ (Eξ) 1/2 E ∞ (τ max ) 1/2 -c E ∞ (τ max ) -1/2 ,
for some finite constant c independent of ρ. Applying again [START_REF] Gamarnik | Validity of heavy traffic steady-state approximation in generalized Jackson networks[END_REF] to τ max we obtain

E ∞ (Q a 1 (0)) 1/2 ≥ Eξ 1 -Eξ 1/2 E ∞ (|Q a (0)| 1/2 ) -c E ∞ (|Q a (0)| -1/2 ) -c E ∞ (τ max ) -1/2
for some constant c , still independent from ρ.

Subtracting (Eξ/(1 -Eξ)) 1/2 E ∞ (Q a 1 (0) 1/2
) on both sides we finally end up with

h ρ (1 -ρ)E ∞ (Q a 1 (0)) 1/2 ≥ Eξ 1 -Eξ 1/2 E ∞ |Q a (0)| 1/2 -(Q a 1 (0)) 1/2 -c E ∞ |Q a (0)| -1/2 -c E ∞ (τ max ) -1/2 , with h ρ = (1 -(ρ/(2 -ρ)) 1/2 )/(1 -ρ) → 1 as ρ → 1.
We can then invoke the results of Lemma 4.5 to conclude the proof of the second inequality in [START_REF] Jiang | Distributed random access algorithm: scheduling and congestion control[END_REF], which concludes the proof of the theorem.

Extension to the strongly persistent case

In this section we present various arguments supporting the conjecture formulated at the end of Sect. 3 that Theorem 4.1 should remain valid in the strongly persistent case β ∈ (1, ∞). On the one hand, we prove in Proposition 5.1 that active queues only advertize a release when they are close to empty, which is the main theoretical result of this section. We also provide a corollary to Proposition 5.1 (Corollary 5.5 in Sect. 5.1.3) that brings closer the two cases β = +∞ and β > 1. On the other hand, we present extensive simulation results in Sect. 5.2 that support our conjecture. Finally, based on these theoretical and simulation results, we elaborate in Sect. 5.3 on possible interesting heavy-tailed phenomena that may arise for 1 < β < 2.

In the rest of this section we let T 1 be the time at which A 1 advertizes a release for the first time.

Proposition 5.1 If ρ < 2 and β > 1, then (A 1 (T 1 ), T 1 -τ 1 ) under P a 1 converges weakly as a 1 → +∞ to a non-degenerate random variable.

By non-degenerate, we mean a random variable (X, Y ) ∈ N × Z such that both X and Y are non-deterministic and almost surely finite (an explicit expression for the weak limit of (A 1 (T 1 ), T 1 -τ 1 ) is given in Lemma 5.3).

Proof of Proposition 5.1

Fix in the rest of this subsection some ρ < 2. The proof of Proposition 5.1 proceeds in two steps: in the first step we show that the proof of Proposition 5.1 reduces to proving a simpler property of some particular random walk [see [START_REF] Ni | Q-CSMA: queue length based CSMA/CA algorithms for achieving maximum throughput and low delay in wireless networks[END_REF]]. In the second step we prove that this property holds when β > 1.

First step

Since before time T 1 , the active queue A 1 does by definition not advertize any release, it is enough to prove Proposition 5.1 in the case ζ = 0, which we therefore assume in this subsubsection and the following one. In particular, A 1 is a random walk with step size distribution ξ -1 reflected at 0. The reduction of the proof of Proposition 5.1 to proving [START_REF] Ni | Q-CSMA: queue length based CSMA/CA algorithms for achieving maximum throughput and low delay in wireless networks[END_REF] relies on the following coupling of the processes A 1 for all possible initial states a ≥ 0.

Let V and W ↑ be two independent processes with the following distribution. Let V be a version of A 1 under P 0 , i.e., (V (k), k ≥ 0) is a random walk started at 0, with step size distribution ξ -1 and reflected at 0.

Let W ↑ be a random walk started at 0, with step size distribution 1 -ξ and conditioned on never visiting 0 after time 0: since E(1 -ξ) > 0 this conditioning is well-defined. Let moreover κ(a) = max{k ≥ 0 : W ↑ (k) = a} be the time of the last visit to a ∈ {0, 1, . . . , ∞} (to be understood as κ(a) = +∞ for a = +∞), so that κ(a) is almost surely finite if a is finite. Let finally W ↑ a be the process

W ↑ stopped at κ(a), i.e., W ↑ a (k) = W ↑ (k) if k ≤ κ(a) and W ↑ a (k) = W ↑ (κ(a)) = a if k ≥ κ(a). Lemma 5.2 Extend A 1 on Z by setting A 1 (k) = A 1 (0) for k ≤ 0,

and define the two processes A

+ = (A 1 (τ 1 + k), k ≥ 0) and A -= (A 1 (τ 1 -k)), k ≥ 0). Then for any finite a ≥ 0, (A + , A -) under P a is equal in distribution to (V, W ↑ a ).
In particular, as a → +∞, (A + , A -) under P a converges weakly to (V, W ↑ ).

Proof That A + is equal in distribution to V and is independent from A -follows from the strong Markov property at time τ 1 . That A -is equal in distribution to W ↑ a comes from duality. The weak convergence result then follows from the fact that κ(a) → +∞ almost surely as a → +∞, so that (V, W ↑ a ) → (V, W ↑ ) almost surely as a → +∞.

Essentially, this representation of A 1 shifts the origin of time at τ 1 : A + looks at A 1 from time τ 1 forward in time, while A -looks at A 1 from τ 1 backward in time. Moreover, this representation couples all the processes A 1 with different initial states on the same probability space, which yields a simple representation for the law of (A 1 (T 1 ), T 1 -τ 1 ). Let in the sequel Z = (Z (k), k ∈ Z) be the following process (indexed by Z):

Z (k) = V (k) if k ≥ 0 and Z (k) = W ↑ (-k) if k ≤ 0.
The previous coupling immediately implies the following result.

Lemma 5.3 Let (U k , k ∈ Z) be i.i.d., uniformly distributed in [0, 1], independent from Z , and for 0 ≤ a ≤ +∞ and k ∈ Z let D a,k = 0 if k < -κ(a), 1 {U k <ψ(Z (k))} else,
and T Z a = inf k ∈ Z : D a,k = 1 . Then for any finite a ≥ 0, (A 1 (T 1 ), T 1 -τ 1 ) under P a is equal in distribution to (Z (T Z a ), T Z a ) and in particular, it converges weakly as a → +∞ to

(Z (T Z ∞ ), T Z ∞ ) (to be understood as Z (T Z ∞ ) = +∞ if T Z ∞ = -∞).
Proof The equality in law between (A 1 (T 1 ), T 1 -τ 1 ) and (Z (T Z a ), T Z a ) is clear from the construction, and not difficult to formalize. Moreover, T Z a is by construction decreasing in a and so its limit as a → +∞ exists. It is not hard to show that its limit is exactly T Z ∞ and by continuity we deduce that Z (T Z a ) → Z (T Z ∞ ) as a → +∞, which implies the result. Thus to prove Proposition 5.1, we only have to establish that |T Z ∞ | is (almost surely) finite. Since V is positive recurrent and starts at 0, it is clear that min k ≥ 0 : D ∞,k = 1 is finite and so to prove that |T Z ∞ | is finite, we only have to demonstrate that the random variable inf k ≤ 0 : D ∞,k = 1 is almost surely finite. Going back to the definition of D ∞,k , we see that we have to prove that sup k ≥ 0 : U -k < ψ(W ↑ (k)) is finite, which informally means that W ↑ advertizes a release only finitely many times.

So in the sequel, we consider (U k , k ≥ 0) i.i.d. random variables, uniformly distributed in [0, 1] and independent of W ↑ , and we define

N = k≥0 1 {U k <ψ(W ↑ (k))} ,
which can be intuitively interpreted as the number of times W ↑ advertizes a release. The proof of Proposition 5.1 will thus be complete if we can prove that P(N < +∞) = 1.

(16)

Second step

We now assume that β > 1 (the results of the previous subsubsection indeed hold for any function ψ) and we prove that P(N ≥ n) → 0 as n → +∞, which will prove [START_REF] Ni | Q-CSMA: queue length based CSMA/CA algorithms for achieving maximum throughput and low delay in wireless networks[END_REF]. By definition,

P (N = 0) = P U k > ψ(W ↑ (k)), k ≥ 0 ,
and since W ↑ and the U k 's are independent this gives

P (N = 0) = E ⎡ ⎣ k≥0 1 -ψ(W ↑ (k)) ⎤ ⎦ . Let a ≥ 0: introducing ϕ(a) = -log(1 -ψ(a)) and L ↑ (a) = k≥0 1 {W ↑ (k)=a}
, the local time at level a, we obtain

P (N = 0) = E ⎡ ⎣ exp ⎛ ⎝ - a≥0 ϕ(a)L ↑ (a) ⎞ ⎠ ⎤ ⎦ . ( 17
)
Lemma 5. [START_REF] Coffman | Polling systems with zero switchover times: a heavytraffic averaging principle[END_REF] The quantity sup a≥0 E(L ↑ (a)) is finite. In particular, P(N = 0) > 0.

Proof Let W -be a random walk with step size distribution ξ -1, started at 0 and independent from W ↑ , and for k

∈ Z define W * (k) = W ↑ (k) if k ≥ 0 and W * (k) = W -(-k) if k ≤ 0. Thus, defining L * (a) = k∈Z 1 {W * (k)=a}
, we have the obvious inequality L ↑ (a) ≤ L * (a), and so we only have to prove that sup a∈Z E(L * (a)) is finite.

It is clear that L * stays the same if W * is shifted in time, and that shifting L * in time amounts to shifting W * in space. Moreover, for any w ∈ Z the process (W * (k) + w, k ∈ Z) shifted at the time of its last visit to 0 is equal in distribution to W * . Combining these facts, we see that L * is a stationary sequence and in particular, sup a∈Z E(L * (a)) = E(L * (0)). By the strong Markov property, L * (0) is a geometric random variable with parameter the probability that a random walk started at -1 and with step size distribution ξ -1 never visits 0. Since Eξ < 1, this probability is strictly positive and so E(L * (0)) is finite. This proves the finiteness of sup a E(L ↑ (a)).

As for P(N = 0), we have

E ⎛ ⎝ a≥0 ϕ(a)L ↑ (a) ⎞ ⎠ ≤ sup a E(L ↑ (a)) a≥0 ϕ(a),
and since ϕ(a) ∼ a -β as a → +∞ and β > 1, the sum a ϕ(a) is finite. In view of the last display, this implies that the random variable a ϕ(a)L ↑ (a) is almost surely finite. This proves P(N = 0) > 0 because of [START_REF] Rajagopalan | Network adiabatic theorem: an efficient randomized protocol for content resolution[END_REF] and concludes the proof of the lemma.

We now prove that P(N ≥ n) → 0 as n → +∞. Let W be a random walk with step size distribution 1 -ξ and I = inf k≥1 W (k). Then, W ↑ is by definition equal in distribution to W under P 0 ( • | I ≥ 1) (where the subscript refers to the initial state of W ). Let moreover B n be the time at which W advertizes a release for the nth time (which is well defined in the event {I ≥ 1}), so that

P(N = n) = b P 0 (B n < +∞, B n+1 = +∞, I ≥ 1) ,
with b = 1/P 0 (I ≥ 1). Writing the event {I ≥ 1} as the union between the two events {inf 1≤k≤B n W (k) ≥ 1} and {inf k>B n W (k) ≥ 1}, the strong Markov property at time B n entails

P(N = n) = b E 0 p(W (B n )); B n < +∞, inf 1≤k≤B n W (k) ≥ 1 ,
with p(w) = P w (N = 0, I ≥ 1). Coupling W under P w with a version of W under P 0 that stays below it, we see that p(w) is increasing in w and so

P(N = n) ≥ bp(0)P 0 B n < +∞, inf 1≤k≤B n W (k) ≥ 1 ≥ bp(0)P 0 (B n < +∞, I ≥ 1) .
This last lower bound is equal to p(0)P 0 (B n < +∞ | I ≥ 1) which by definition is equal to p(0)P(N ≥ n). Since p(0) = P(N = 0)/b is > 0 by Lemma 5.4, dividing by p(0) leads to

P(N ≥ n) ≤ b P(N = n) P(N = 0) .
Since P(N = n) → 0, this finally proves ( 16) and hence Proposition 5.1.

Corollary to Proposition 5.1

From Proposition 5.1, which is concerned with the behavior of one active queue, one can deduce the behavior of A(T * ) and T * . The intuition behind the following result is clear: Proposition 5.1 shows that an active queue only advertizes releases when it is of order 1. Thus when considering several active queues and the initial state of at least one of them blows up, by the time the last queue to advertize a release does so, all the other queues are already in their stationary regime. From there on, it thus only takes an additional (random) time of order 1 for all the queues to advertize a release simultaneously. We therefore omit the proof of the following result, which consists of a direct translation of this intuition and can be formalized using similar arguments as in the proof of Lemma 4.2 (it is actually easier, since we make no claim about the mean behavior of the random variables involved).

Corollary 5.5 Assume that ρ < 2 and that β > 1, and consider any sequence of initial states a n = (a n,r ) such that max r a n,r → +∞: then (A(T * ), T * -τ max ) under P a n converges weakly as n → +∞ to a non-degenerate random variable.

Simulation results

In this subsection we present simulation results which complement the theoretical result of the previous subsection and support our claim that Theorem 4.1 remains valid for β > 1. Based on simulation, we discuss stability issues and the asymptotic behavior of E ∞ ( Q(0) ) in the heavy-traffic regime ρ ↑ 1. Proposition 4.4 and Theorem 4.1 show that the stability of the system and the order of magnitude of E ∞ ( Q(0) ) are not affected by the precise value of R or by the precise distribution of ξ (as long as R ≥ 2 and E(ξ 2 ) < +∞). Proposition 5.1 suggests a similar result, and also that the precise distribution of ζ will not matter as far as stability, and the order of magnitude of E ∞ ( Q(0) ) are concerned. We thus performed our simulation with ξ a geometric random variable with parameter 2/(2 + ρ) and P(ζ = 1) = 1. We ran simulations using different distributions for ξ and ζ as well, including extreme cases such as distributions with infinite third moment (even infinite second moment for ζ ), that yielded qualitatively similar results.

Simulation results for stability

It is straightforward to prove that Q is transient if ρ > 1, irrespective of the value of β ∈ (0, ∞]. Indeed, if Q(t) is the number of packets at the beginning of the tth time slot, Q is lower bounded by a random walk with drift R(ρ -1). Thus when ρ > 1, we have Q(t) → +∞ as t → +∞ and since ( Q(k) , k ≥ 0) is a subsequence of ( Q(t), t ≥ 0) this proves the transience of Q in this case.

For ρ < 1 we present a heuristic argument which suggests that Q is stable. If the active queues are in state a = (a r ) with a r > 0 for every r , the variation of the mean number of packets in the system over the next time slot is equal to

-R 1 -ρ -z R r =1
ψ(a r ) (remember that z = Eζ ). Since ψ(a) → 0 as a → +∞, the drift is negative, close to -R(1 -ρ), when each a r is large enough. The problem in formalizing this argument is twofold: first, in order to prove stability, one must be able to control every possible initial configuration, not only those where every a r is large (note however that because of symmetry, it is natural to expect all a r 's to be large or small simultaneously); second, this argument considers the system on the normal time scale, whereas we are interested in the system embedded at switching times. In addition to this heuristic argument, simulation results strongly support stability of the system for ρ < 1. Indeed, Fig. 2 shows the evolution of Q(k) , starting at Q(0) = 0, in the case R = β = 2 and for two values of ρ: ρ = 0.99 and ρ = 1.01. When ρ = 0.99, Fig. 2a shows that Q(k) fluctuates between 2,000 and 8,000 for values of k up to 15,000. In contrast, Fig. 2b shows for ρ = 1.01 that Q(k) increases until we stop the simulation when 1.5 • 10 6 packets are present in the system, which only takes about 300 switching times. Note that for a transient system we would expect that, when the queues are large, the total queue size grows by a constant amount on average in every time slot, and that the time between two consecutive switching times increases. This explains the super-linear growth of Q(k) as we consider the system at switching times. In fact, the reasoning in Sect. 3 suggests that when Q(k) is large we have Q(k + 1) / Q(k) ≈ Eξ/(1 -Eξ). This gives a heuristic explanation for the exponential growth (at rate ρ/(2 -ρ) > 1) observed in Fig. 2b. All in all, this is in line with the known transience of Q for ρ = 1.01.

In general, it may be difficult to distinguish between positive recurrent and transient systems based on simulation results. Here however, Q obeys two clearly distinguishable types of behavior: stochastic fluctuations on a long time interval when ρ < 1 (Fig. 2a), and almost deterministic exponential growth when ρ > 1 (Fig. 2b). This phase transition is a further indication of the stability and instability of the system for ρ < 1 and ρ > 1, respectively.

Simulation results for the asymptotic behavior of E

∞ ( Q(0) )
Having discussed the stability of Q when ρ < 1, we now discuss the asymptotic behavior of E ∞ ( Q(0) ). To quantify its growth, it is convenient to introduce the notion of scaling exponent. Definition 5. [START_REF] Foster | A limit theorem for a branching process with state-dependent immigration[END_REF] We call scaling exponent the number α such that lim

ρ↑1 log E ∞ ( Q(0) ) log(1/(1 -ρ)) def. = α. ( 18
)
Our interest in the scaling exponent comes from an expected polynomial growth of E ∞ ( Q(0) ) in heavy traffic. In general, we expect as ρ ↑ 1 a behavior of the kind

E ∞ ( Q(0) ) ≈ C (1 -ρ) α (19)
for some finite constant C > 0. Note that such a behavior would be stronger than [START_REF] Resing | Polling systems and multitype branching processes[END_REF], but that it is consistent with the result of Theorem 4.1. We have proved in the case β = +∞ that the scaling exponent exists, and is equal to 2. In general we will assume that it exists and will be interested in discussing its value.

The scaling exponent depends on the four model parameters R, ξ , ζ and β. However, as explained in the beginning of Sect. 5.2, we will mostly be interested in its dependence on β and thus write α(β) when the other three parameters are kept fixed. In fact, our results suggest that α does not depend on these other parameters. As explained in Sect. 3, our main claim is that the lingering effect makes E ∞ ( Q(0) ) grow as 1/(1-ρ) 2 when β > 1. Formally, this amounts to conjecture that the scaling exponent (exists and) satisfies α(β) = 2 for β > 1.

In addition to the heuristic arguments presented in Sect. 3, we now present some simulation results supporting this claim. From the results in Fig. 2 we find by averaging over time E ∞ ( Q(0) ) ≈ 4.700 for ρ = 0.99, corresponding in view of the definition [START_REF] Resing | Polling systems and multitype branching processes[END_REF] of the scaling exponent to the estimate α(2) ≈ log 4.700/ log 100 ≈ 1.84. To facilitate the discussion we define in the sequel

F(ρ, β) = log E ∞ ( Q(0) ) log(1/(1 -ρ)) , β ∈ (0, ∞], ρ < 1. (20)
Then, the scaling exponent α(β) is defined in (18) via a limiting procedure, namely α(β) = F(1-, β) = lim ρ↑1 F(ρ, β). Using the results of Fig. 2a to estimate α(2) amounts for using the approximation F(1-, 2) ≈ F(0.99, 2). In order to check whether this approximation is valid, we performed the same simulation for different values of ρ. In Fig. 3 the value of F(ρ, 2) is plotted for ρ ∈ (0.87, 0.999). We plotted F(ρ, 2) against log(1/(1-ρ)) in order to "dilate" time around the value ρ = 1 that we are interested in and also because it is natural to regress F(ρ, 2), as function of ρ, against log(1/(1 -ρ)) as we discuss now.

Figure 3 shows that the limit F(1-, 2) seems to exist, but that F(ρ, 2) is still significantly increasing for ρ = 0.999. Thus F(0.999, 2), and in particular F(0.99, 2), cannot be used as an accurate estimate of α [START_REF] Bouman | Achievable delay performance in CSMA networks[END_REF]. It is numerically difficult to run a simulation for even higher values of ρ, and so to circumvent this problem, we use the simulation results displayed in Fig. 3 to find the asymptotic value of F(ρ, 2). To do so, we use the approximation [START_REF] Shah | Medium access using queues[END_REF] to infer the form of F(ρ, β), namely

F(ρ, β) ≈ α(β) + log C log(1/(1 -ρ)) , (21)
which suggests, as mentioned above, to regress F(ρ, 2) against a + b/x in the scale x = log(1/(1-ρ)). We performed this regression for the curve displayed in Fig. 3 and found an optimal value a = 1.9984, which gives an estimate for the scaling exponent α(2) ≈ 1.9984 in very good agreement with our conjecture. Applying the same approach, we can find an estimate for α(β) for any value of β. The results for R = 2, 3 and 5 are given in Fig. 4, and confirm that R does not seem to influence α(β). Further, the approximation α(β) ≈ 2 appears to be very good for any β > 1.2, namely, the estimated value of α(β) is at most 3 % away from 2 for any β > 1.2 and any R = 2, 3, 5.

More on the case

β > 1, β ≈ 1
The previous simulation results show a rather fuzzy behavior of α(β) for β close to 1. Indeed, the curves shown in Fig. 4 seem stable for β > 1.2 but much less so as β gets closer to 1. We believe that this may be due to interesting heavy-tailed phenomena. for R = 2. The solid line represents F(ρ, 2) versus log(1/(1-ρ)); the dashed line represents the best regression obtained by regressing F(ρ, 2) past its infimum as in [START_REF] Shah | Randomized scheduling algorithm for queueing networks[END_REF] The shape of the function ρ → F(ρ, β) depicted in Fig. 3 is typical for large values of β, say β > 1.2. In particular, this function is increasing which makes the regression of F against 1/ log(1/(1 -ρ)), such as in [START_REF] Shah | Randomized scheduling algorithm for queueing networks[END_REF], reasonable. However, as β gets closer to one, the shape of this function changes. For instance, Fig. 5 shows simulation results for F(ρ, 1.2) which are representative of F(ρ, β) for small β, say 1 < β < 1.2. Noticeably, the function F(ρ, 1.2) is not monotone in ρ and so the approximation (21) cannot be valid for every ρ. Rather, we find that F(ρ, β) decreases and then increases, and that the regression against 1/ log(1/(1 -ρ)) is only accurate past the minimum.

Regressing the curve obtained in Fig. 5 past the minimum leads to the approximation α(1.2) ≈ 1.94, which is still very much in line with the conjecture α(1.2) = 2. However, the point where the minimum of the function ρ → F(ρ, β) is attained shifts to the right when β gets closer to 1, leaving us with less points against which to regress. In particular, for β < 1.2 one would need to simulate the system at loads higher than 0.999 to get accurate results. We suspect that this numerical instability is caused by heavy-tailed phenomena that seem to appear for β < 2. More precisely, inspecting the proofs of Proposition 4.4 and Theorem 4.1, one sees that Corollary 5.5 is not strong enough for the proofs of the case β = +∞ to go through directly. Indeed, instead of controlling the behavior of A(T * ) and T * in distribution, one needs (at least, with the proposed proof strategy) to control their mean behavior. Let us do a small computation: let T Z ∞ be the random variable introduced in Lemma 5.3, which is the weak limit of T 1 -τ 1 , and let B ↑ be the first time the process W ↑ advertizes a release. Then

E(|T Z ∞ |; T Z ∞ ≤ 0) = E(B ↑ ; B ↑ < +∞) = k≥0 kP(B ↑ = k),
and as before, we have

P(B ↑ = k) = E ψ(W ↑ (k)) i<k (1 -ψ(W ↑ (i))) .
The arguments of Sect. 5.1 show that the random variable i≥0 (1 -ψ(W ↑ (i))) is finite. In view of the last expression, it therefore seems that the tail behavior of B ↑ is dictated by ψ(W ↑ (k)) as k → +∞ and since W ↑ (k) ≈ k(1 -Eξ) by the law of large numbers, we should obtain P(B ↑ = k) ≈ k -β as k → +∞. When β < 2, this suggests that B ↑ , and in particular |T Z ∞ |, has infinite mean, although both random variables are almost surely finite for β > 1. It is possible to use this result to show that the (almost surely finite) weak limits (as the initial state grows to +∞) of A(T * ) and T * -τ max have infinite first moment. This potentially invalidates the backof-the-envelope computations of Sect. 3, and so more care is needed. For instance, simulation experiments for β = 1.2 and R = 2 suggest that E a 1 (A 1 (T * )) grows as a 0.4 1 as a 1 → +∞, whereas A 1 (T * ) converges weakly to a finite random variable.

Concluding remarks and suggestions for further research

Motivated by the poor delay performance of "cautious" activation rules in queuebased schemes for distributed medium access control, we investigated more aggressive schemes. Our main contribution lies in highlighting a new effect that we called the lingering effect and in studying the performance ramifications of this effect for a special topology. In this section we explain and discuss various directions in which our framework could possibly be extended, and also relate our results to those of [START_REF] Ghaderi | Backlog-based random-access in wireless networks: fluid limits and instability issues[END_REF]. First of all, it would be straightforward to extend our results to the following asymmetric case: instead of having R queues in each group with identically distributed arrival processes across queues, we have two groups of R 1 and R 2 queues and the arrivals into the kth queue of group g have distribution ξ g,k . We chose to study a symmetric scenario for technical reasons, since then there is no need to label queues individually. In this setting, the lingering effect will occur whenever, informally speaking, the two dominant queues of at least one of the two groups have the same arrival rate. For instance, the delay will scale like 1/(1-ρ) 2 with ρ = max k E(ξ 1,k )+max k E(ξ 2,k ) if the condition E(ξ 1,1 ) = E(ξ 1,2 ) ≥ max g,k E(ξ g,k ) is satisfied.

We believe that the insights provided by the complete bipartite constraint graph carry over to more general topologies. Note that for a general topology, our model needs to be amended, since one needs then to specify more precisely how queues become active. One can for instance think of queues going into back-off, and then trying to acquire the shared resource at some rate. We conjecture that whenever the constraint graph is not complete, and thus contains an independent set of several nodes, the lingering effect can rear its head, provided some algebraic condition between the arrival rates at the various queues is satisfied. It would be very interesting to be able to formulate a precise and formal conjecture reflecting this intuition, and most probably quite challenging to prove it.

To conclude, we would like to put our results in perspective by linking them to those of [START_REF] Ghaderi | Backlog-based random-access in wireless networks: fluid limits and instability issues[END_REF]. On the one hand, our results show that the delay performance may be greatly improved by considering more aggressive schemes (compared to maximally stable algorithms known earlier). On the other hand, Ghaderi et al. [START_REF] Ghaderi | Backlog-based random-access in wireless networks: fluid limits and instability issues[END_REF] have shown that, by doing so, one may lose a fraction of the stability region. But in the example analyzed in [START_REF] Ghaderi | Backlog-based random-access in wireless networks: fluid limits and instability issues[END_REF], one only loses a small fraction of the stability region, namely about 3 %. Thus, our work suggests a potentially interesting trade-off between stability and delay performance, namely that more aggressive schemes may lead to a small loss of stability, whereas the delay in this stability region is much better than the delay for a maximum stable algorithm.

Fig. 2

 2 Fig. 2 Total number of packets at switching times: Q(k) versus k for R = β = 2 and a ρ = 0.99; b ρ = 1.01

Fig. 3

 3 Fig. 3 Approximating α(2) for R = 2. The solid line represents F(ρ, 2) versus log(1/(1-ρ)) obtained by simulation from the definition (20) of F; the dashed line represents the best regression of F(ρ, 2) against x → a + b/x in the scale x = log(1/(1-ρ)) [see (21)]

Fig. 4 α

 4 Fig. 4 α(β) (obtained by simulation) versus β for R ∈ {2, 3, 5}

Fig. 5

 5 Fig. 5 Approximating α(1.2)for R = 2. The solid line represents F(ρ, 2) versus log(1/(1-ρ)); the dashed line represents the best regression obtained by regressing F(ρ, 2) past its infimum as in[START_REF] Shah | Randomized scheduling algorithm for queueing networks[END_REF]

Acknowledgments This work was supported by Microsoft Research through its PhD Scholarship Programme and a TOP Grant from NWO.