{'fraction_non_alphanumeric': 0.03551709663879113, 'fraction_numerical': 0.011591488812114558, 'mean_word_length': 4.261977573904179, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Exclusion in a priority queue

We introduce the prioritising exclusion process, a stochastic scheduling mechanism for a priority queueing system in which high priority customers gain advantage by overtaking low priority customers. The model is analogous to a totally asymmetric exclusion process with a dynamically varying lattice length. We calculate exact local density profiles for an unbounded queue by deriving domain wall dynamics from the microscopic transition rules. The structure of the unbounded queue carries over to bounded queues where, although no longer exact, we find the domain wall theory is in very good agreement with simulation results. Within this approximation we calculate average waiting times for queueing customers.


Introduction
In this work we introduce a discrete particle hopping and exclusion process motivated by queueing theory: the prioritising exclusion process (PEP). The PEP is an example of a microscopic model of a driven system [1] describing the asymmetric diffusion of hard-core particles along a one-dimensional chain. The empty and occupied sites in the PEP represent low and high priority customers, and the lattice length grows and shrinks as customers arrive and are served. The PEP acts as a stochastic scheduling mechanism for a priority queue, and is closely related to a priority queueing model first introduced by Kleinrock [2], and the subject of more recent work [3].
The hopping and exclusion in the PEP is analogous to that of the totally asymmetric simple exclusion process (TASEP) [4,5], which is one of the most thoroughly studied and central models of non-equilibrium statistical mechanics [6][7][8][9]. The TASEP has been the focus of much mathematical interest due to the fact that it is integrable. Many tools have been applied to or developed for the TASEP. Its exact stationary distribution is known [10,11] and can be written in matrix product form [9,12]. Its dynamic properties are studied by means of the Bethe ansatz [8,13,14] and for the infinite lattice powerful techniques from random matrix theory are available [15]. Domain wall theory [16] provides a phenomenological explanation of the stationary behaviour of the TASEP. Domain wall theory is amenable to generalisation to more complicated models that may not be integrable, and we will describe it in more detail later.
Recently, several generalisations of the TASEP have been proposed, which allow the lattice length to vary dynamically as is the case in the PEP. These models have been motivated by applications in biological transport [17,18] and queueing theory [19]. They retain the basic rules of the TASEP: particles occupy sites on a one-dimensional lattice, and hop forward with a given rate to the site immediately ahead, if it is empty. In the biological transport models, particles actively [17] or passively [18] enlarge the domain. In the exclusive queueing process [19], the length of the lattice is defined by the position of the last particle (customer), and the hopping particles represent customers shuffling forwards in the queue.
In the PEP the varying lattice length is defined by the total number of customers at any given time. Aside from its application as a stochastic scheduling mechanism in queuing theory, the PEP is of theoretical interest in statistical physics as it connects systems of different sizes with dynamical rules, contrary to the traditional TASEP where the lattice length is fixed. This fact significantly complicates an exact analysis using techniques such as matrix product states and Bethe ansatz, but we find that the structure of the model makes domain wall theory naturally applicable.
For the PEP, the domain wall dynamics can be derived directly from the microscopic transition rules, similarly to [20]. We find that in the PEP there are two phase transitions. The first one, well known in queuing theory, is between a bounded and unbounded phase where the expected queue length becomes infinite. This transition is independent of the bulk hopping rate and only depends on the arrival and service rates.
The domain wall dynamics yields the exact stationary distribution in the unbounded queue, and gives rise to the second phase transition, which for fixed boundary rates takes place at a critical value of the hopping parameter. At this critical point, the expected jam length of high priority customers near the service end diverges. In other words, beyond this transition, with probability one, low priority customers will no longer be served.
The structure we find in the unbounded phase carries over to the bounded case where, although no longer exact, we see very good agreement with numerical simulations. In the bounded phase a remnant of the second, jamming transition can be observed as a crossover where the jam of high priority customers near the service end delocalises when the hopping parameter reaches a critical value, and the expected jam length becomes comparable to the the queue length.

The model
In the lattice bulk, the PEP behaves as a TASEP: sites are either occupied by a single particle or empty, and particles hop forwards into empty sites with rate p. At the boundaries the PEP differs from the TASEP. The PEP lattice can be extended on the left by the addition of a filled or empty lattice site, with rates λ 1 and λ 2 respectively. At the other boundary, the rightmost site is removed with rate µ, irrespective of its occupation. These rules, summarised in Figure 1, allow both the lattice length and particle number to vary. We specify a PEP configuration by binary variables τ i with τ i = 1 for a filled site and τ i = 0 for an empty site. Usually we will number sites from right to left and write a length n configuration as τ = τ n τ n−1 . . . τ 1 .

A queueing system
The PEP can be interpreted as a priority queueing system with two classes of customers. The lattice, itself, is the queue of customers, with filled sites representing high priority customers (class 1) and empty sites representing low priority customers (class 2). The rates λ 1 and λ 2 are the arrival rates of high and low priority customers respectively, and the rate µ, is the rate at which customers are served and leave the queue.
In this interpretation, a particle hopping forward one site corresponds to a high priority customer stepping ahead of the low priority customer immediately in front of them. The stochastic overtaking is the scheduling mechanism in this priority queue, giving high priority customers preferential treatment over low priority. The larger the overtake rate p, the greater the advantage.
The PEP is modelled on a well studied priority queueing system introduced by Kleinrock [2,21] and now known as the accumulating priority queue (APQ) [3]. In the APQ, customers have a priority value which accumulates linearly with time. Class 1 customers accumulate priority faster than class 2, thus overtaking them in the service queue. The key difference between the APQ and the PEP is that, for a given sequence of arrivals, overtaking in the APQ is deterministic, but in the PEP the overtakes occur stochastically.
The PEP is also related to a simpler queueing system, the M/M/1 queue (see, for example, [22]). The total arrival rate of customers to the PEP is λ = λ 1 + λ 2 , and the service rate is µ. Both these rates are independent of the internal arrangement of the queue, and the prioritising parameter p. So, if we are interested only in the total length of the queue, we can treat the system as a M/M/1 queue with arrival rate λ and service rate µ. The state of an M/M/1 queue is characterised simply by the length, n, with probability distribution P n obeying the master equation dP 0 dt = µP 1 − λP 0 (1) dP n dt = λP n−1 + µP n+1 − (µ + λ)P n , n > 0.
The stationary length distribution of the M/M/1 queue (and hence for the PEP) is the solution of dP n /dt = 0, which is when λ < µ, i.e. when the total arrival rate is less than the service rate. In this case the system is described as stable, because the queue length does not grow without bound. The expected queue length is finite, given by We will call this the bounded phase of the PEP. When λ > µ, the system is unstable and the expected queue length grows as In the late time limit, we can treat the queue as infinite in length. We call this the unbounded phase of the PEP.

Density profiles and waiting times
To define a density profile for the PEP we must specify both the site, i, and the lattice length, n, so that τ i n = P (queue length is n, and site i is occupied).
These are one-point functions. We can similarly define higher order correlations The rate equations for the one-point functions are d dt These couple the one-point functions to the two-point correlations, and length n to length n±1. The rate equations imply a conserved current of particles across the lattice, but because of the coupling between lengths, some care is required in how this current is defined. We will return to this for the bounded and unbounded phases separately. Viewing the PEP as a queueing system, we are interested in performance measures, and how these differ for high and low priority customers. The current tells us the rate at which customers pass through the system, and from the density profile we can calculate the average waiting time for customers of each class.
To calculate waiting times, we use Little's result (see Chapter 2.1 of [22]), which states that the average waiting time, W i , is related to the average number of waiting customers, N i , for each class i = 1, 2, by The average number of high priority customers can be calculated from the density profile as and the average number of low priority customers is Here we take the total time from arrival to removal from the system as the waiting time for a customer. Our aim, now, is to compute the density profile for the PEP.

Domain wall theory
Domain wall theory [16,23] reduces the multi-particle dynamics of the TASEP ‡ to the motion of a single random walker on the lattice. The TASEP boundary conditions (the particle entry and exit rates) create domains of low or high density at the boundaries. These domains extend through the lattice, and where they meet a shock, or domain wall, forms. Domain wall theory models the motion of this shock as a random walk, with the simplifying assumptions that density is constant throughout each domain, and that there is a sharp transition between domains so that the shock can be localised to a single site. Though the stationary solution of the TASEP is known exactly, domain wall theory provides a simple physical explanation of the stationary behaviour [16], and beyond this it allows accurate approximation of some dynamic properties [23]. Domain wall theory can also be applied to more complex models [24,25] where the exact solution is not known.
The PEP has a natural domain wall structure. As high priority customers overtake and reach the service end, they form a jam (Figure 2(a)): a jam is a section of high priority customers (filled sites) at the service end ahead of any low priority customer (empty site). The jam is characterised by k, the number of consecutive high priority customers. As there are no gaps, there is no overtaking in the jammed region, and the length of the jam reduces only as customers are served. This is similar to the situation in [20], where a TASEP with parallel update and deterministic bulk motion is considered.
Let us assume that the region beyond the jam has uniform density, and that the conditional probability that site i is filled, given the queue length, n, and jam length, k, is ( Figure 2 (14) ‡ Domain wall theory applies more generally to the partially asymmetric exclusion process.
Then the bulk equation (n > k + 1, k > 0) for P (n, k), the probability of a length k jam in a length n queue, is d dt Let us explain the meaning of each of the terms in equation (15). The term is the entry into the (n, k) configuration from a length n queue due to the arrival of a customer, and the terms represent the service of a customer. The second term is the transition into the k-jam state from the (k = 0)-jam state by the service of a low priority customer who was followed by k consecutive high priority customers. The term is a (k − 1)-jam extending to length k with rate pα: there is a high priority customer at site k + 1 with probability α, which overtakes with rate p the low priority customer at site k (the low priority customer marking the end of the (k − 1)-jam). The low priority customer thus moves to position k + 1 defining the new end of the jam. The loss terms are the rate at which the (n, k) configuration is left due to a customer arrival or service, or growth of the jam.
In the next section, we will show that the n → ∞ limit of (15) follows from the unbounded phase master equation and, together with the equation for k = 0, leads to the exact solution. In the bounded phase (Section 3), domain wall theory leads to two complementary approximations, which describe the behaviour of the system and allow calculation of waiting times.

The unbounded phase
We consider first the unbounded phase of the PEP, where the total arrival rate exceeds the service rate (λ > µ). The expected lattice length increases with time, so in the late time limit we can treat it as infinite. On an infinite lattice, the density profile must be given relative to a specified reference frame [17]. For the PEP, there are two reference frames of interest. The service frame is fixed at the right hand end of the lattice where customers are served and depart, removing a site from the lattice. The arrival frame is fixed at the left hand end of the lattice where customers arrive, adding a filled or empty site to the lattice.

Domain wall ansatz
To apply domain wall theory to a queue of infinite length, we consider a general but finite section of length m in the service frame, with a jam of length k where 1 k indicates a string of k 1's. Sites are numbered right to left. The configuration of any finite segment can be written this way, as long as we can take m ≥ k + 1. We will assume that the conditional probability for a high at site i given a jam of length k is which is (14) in the n → ∞ limit. Then the probability of the finite segment (16) is where h is the number of highs in the configuration beyond the jam up to position m, and l is the number of lows, that is and P jam (k) is the probability of a length k jam. The jam probabilities are normalised such that Equation (18) is an ansatz for the stationary probabilities. We now show that α and P jam (k) may be determined such that all rate equations are satisfied.

The service frame
We use the notation τ | (i,i−1) to indicate the exchange of customers in places i and i − 1.
The stationary rate equation for the k-jam configuration (16) with k ≥ 1 is Let us again explain the various terms. The terms give the rate of arrival to the k-jam configuration after, respectively, a high or low priority customer is served. Then there are the hopping terms. A high in mth place in τ 01 k can arrive from place m + 1: Overtaking within the low density region behind the jam is given by and a (k − 1)-jam extends to a k-jam when a high hops onto the end: The loss term is the reduction of the jam as a customer is served, and are overtakings within the m places of τ 01 k . The final loss term arises if the configuration has a low in mth place, which can be overtaken by a high from place m + 1. Substituting the ansatz (18), the terms representing overtaking within the m sites of τ 01 k combine and telescope to The factor α h (1 − α) l is common to all terms in the rate equation. Cancelling, and simplifying leaves This agrees with the n → ∞ limit of (15), but we have derived it from the full PEP rate equations. Were it not for the P jam (0) term, this equation for the position of the jam would have the same form as the domain wall theory for the TASEP [23]. The k = 0 case differs only slightly. In this case the rate equation is Substituting the ansatz (18), this reduces to and rearranging gives With this as the base case, we use (22) to show by induction that This recurrence for P jam (k) has solution The normalisation condition (20) fixes subject to the constraint The domain wall picture makes the meaning of this constraint clear. The jam of high priority customers grows with rate pα and is reduced with rate µ. If pα > µ the jam grows with rate pα − µ > 0, that is and as t → ∞ the expected length of the jam becomes infinite. In contrast, when (29) is satisfied, the service rate is fast enough to prevent a backlog of high priority customers, and the expected jam length is finite and given by

The arrival frame
To determine α, we examine the PEP in the arrival frame. Sites are now numbered left to right, and the interchange operation is defined as We will assume that the jam is always far from the arrival end. In the late time limit this is guaranteed if This condition is clearly met when (29) is satisfied, but we will show that α can be determined consistently with this requirement. Then in the arrival frame, the ansatz (18) implies for any site. A configuration on the first m sites, occurs with probability The stationary rate equation for this configuration is Substituting (33), the summed hopping terms again combine and telescope, and the factors of α and 1 − α common to all terms can be cancelled. This leaves which for both τ 1 = 0 and τ 1 = 1 reduces to The two solutions are with 0 < α − < 1 and α + > 1 for p, λ 1 , λ 2 > 0. As α is a density value we must take α = α − . Substituting this value for α, it is seen that pα < λ (the constraint (32)) is satisfied for all physical parameter values. Thus, starting from the assumption that the jam never reaches the arrival end, we arrive at a consistent solution.

Density profile, conserved currents, and service rates
To obtain the service frame rate equations, we take the n → ∞ limit of (7 -10). In this limit, the boundary cases can be neglected, and the bulk equations can be written d dt where In the stationary state the time derivatives are zero so (36) defines a conserved current The bulk current, J (i) ∞ , has the usual TASEP hopping term, p τ i (1 − τ i−1 ) ∞ . The additional term µ τ i ∞ arises due to the choice of reference frame.
The one-point functions are computed from the domain wall solution as and the two-point correlation The resulting service frame current is and is the rate at which particles exit the system. In terms of the queueing model, the current is the average rate at which high priority customers leave the queue. As the total rate at which customers leave the system is µ, § low priority customers leave the queue at rate (43) § If the queue was ever empty, the rate at which customers leave would be less than the service rate, but in the unbounded phase this is not a concern.
The constraint pα < µ (equation (29)) ensures that this rate is greater than zero and low priority customers always receive a share of the service. For pα > µ, the jam of high priority customers at the service end becomes unbounded, and low priority customers can no longer reach the front of the queue to be served. Thus the low priority current has a second order phase transition at pα = µ .

The bounded phase
In the queueing theory interpretation, it is the bounded phase of the PEP (with λ < µ) that is of greatest interest. In this phase the queue lengths and waiting times remain finite, and we can compare how the waiting time varies with the overtake rate, p, for high and low priority class customers.
The fluctuating lattice length proves a challenge in applying domain wall theory directly to the bounded phase. We will take two approaches, each leading to an approximate solution revealing different aspects of the system. The first method tells us about the shape and length dependence of the density profiles, while the second method allows us to calculate customer waiting times.
The simple domain wall picture breaks down when the jam reaches the arrival end, i.e. for configurations 01 n−1 or 1 n . Our strategy is to find a solution of the bulk equations, without requiring it to satisfy these boundary equations. We can hope that this will give an approximation to the true solution. What we will show is that, within the range of validity, the approximation is very good.

Length assumption.
To solve the bulk equations we assume the length dependence factorises as where P n is the length distribution (3). Then equation (49), for k > 0, becomes 0 = pαP * jam (k−1)+λP * jam (k+1)+λ(1−α)α k P * jam (0)−(λ+pα)P * jam (k), (52) and equation (50), for k = 0, gives These have the same form as the unbounded queue domain wall equations, (22), (24), but with λ in place of µ. Therefore they are solved by The normalisation of P * jam (k) must be independent of n. For the solution to be valid for n → ∞ (as there is no cap on queue length) we must require fixing subject to the constraint pα < λ.
The total probability at each length, n, must sum to the length distribution (3), that is As only P (1 n ) is undertermined, we must have that This is analogous to the unbounded queue. There the probability that the first n sites from the service end are filled is ∞ k=n P jam (k).

Density profile.
To summarise, we have solved the bulk equations in the domain wall approximation, giving the solution in the form (51), which with (3) and (54) results in In general this solution does not satisfy the boundary equations for k = n, n − 1, i.e. the cases we neglected were where the jam extends to the length of the queue. The jam grows with rate pα, so the constraint pα < λ (equation (57) arising from the normalisation condition) requires that the queue length grows faster on average then the jam. Since we have totally neglected the boundary equations, we expect our approximation to be best when pα ≪ λ.
The density at site i in a length n queue, computed from this solution is (65) Figure 4 shows length dependent density profiles for pα < λ (Figure 4(a)) and pα > λ (Figure 4(b)). Triangle markers show Monte Carlo simulation results, while the solid This is for k > 0, but (47) for k = 0 gives the same result.   curves in Figure 4(a) are the density profiles τ i n calculated from (65). The simulation points in Figure 4(b) have been connected by dashed lines to aid the eye.
In Figure 4(a), we see good agreement between simulated and calculated profiles, the discrepancy between the two decreasing as n increases. But what is most striking is the difference in length dependence between Figures 4(a) and 4(b), with the length factorisation assumption (51) clearly not holding in 4(b). The almost linear profiles in 4(b) are reminiscent of the behaviour of the TASEP on the coexistence line. In that phase, the domain wall occurs at all positions with equal probability, resulting, on average, in a linear profile [11]. In the bounded PEP the evidence suggests that the constraint pα < λ marks a crossover between the localised jam, for pα < λ and the delocalised jam for pα > λ.

Aggregate density profile and current
In this section we take a different approach, working with the rate equations for the one-point functions. We start by defining a conserved current for the bounded phase. To do so, we sum the density at each position over all lengths, thus aggregating the effect of the length fluctuations. Define the summed one-point functions Note that as τ i n ≤ P n , so the sum is bounded, and it converges as M n=i τ i n is monotone increasing in M. Thus τ i is well defined. Higher order summed correlations are defined similarly, e.g.
Summing the rate equations (7) -(10) gives These can be written as a conservation equation for three currents d dt where is the site-to-site current with a hopping term and frame current term. But customers can also step directly into place at the end of the queue, which gives the external current J (i) ext . In the stationary distribution the time derivatives are zero, and so (71) gives a recurrence for the site-to-site current which reduces to We have lim i→∞ J (i+1,i) = 0, as both terms on the right hand side of (74) go to zero.
Therefore (76) implies that and Now (73) tells us that This result is exact -it is the probability that the lattice is at least length one with a particle in site 1.
We could have derived this result directly from the notion of the PEP as a queue: high priority customers leave the system at an average rate µ τ 1 . The rate at which high priority customers leave the system cannot be higher than λ 1 , the rate they arrive. But as the service capacity exceeds the total arrival rate (λ = λ 1 + λ 2 ) there is no bottleneck at the server, so high priority customers ¶ leave at the rate they arrive, that is µ τ 1 = λ 1 .
The presence of two-point correlations prevent us from calculating exact densities for i = 2, 3, etc. The mean field method [10,17] is the standard way to deal with this, assuming the correlation between neighbouring sites is small so that the two point correlations can be approximated as products of the one-point functions. But for the PEP, we can exploit the similarity to the unbounded system, for which we have an exact solution.
By the definition (66), τ i is the probability We can instead work with the conditional probability the two are related by Substituting into (73), (74) gives These have the same form as the current equations for the unbounded queue, (38), with an effective current so are solved by the unbounded queue one-and two-point functions (40), (41). That is and To determine α, we substitute (86), (87) into (84), and take i → ∞ (assuming pα < µ). This gives back the quadratic for α (61), so we again must take α = α − , given by (62). Note that pα < µ if p, µ, λ 2 > 0, so the density profile is always exponentially decaying. Figure 5 shows the aggregated density profiles, τ i computed from (82), (86), plotted against simulation results for several different parameter values. The shape ¶ A corresponding argument applies to low priority customers.     of the profiles, and dependence on the overtake rate, p, can be understood in terms of the domain wall model. For i = 1, where the exact value of τ 1 is known, and for large i, where the length dependence in the form of the (λ/µ) i factor dominates, there is excellent agreement between the simulated and calculated density profiles. At intermediate values of i the dependence on p is seen. In the calculated density profile, this dependence enters through the (pα/µ) i term, which can be understood as describing a jam growing with rate pα and being reduced with rate µ. It is here that there is the greatest discrepancy between calculated and simulated profiles, although the agreement is still very good.
Note we could also compare the aggregated profiles with τ i n (65) summed over n. However, even at position 1 the summed τ 1 n does not agree with τ 1 (79) for which the exact result is known. The direct application of the domain wall ansatz in Section 3.1 gave an indication of the length dependence in the system, but the approach in this section, following from the current conservation equation, is in much better agreement numerically with simulation results.

Waiting times
We can use the aggregated one-point functions to compute the average number of customers in the queue, and in turn the waiting times for both classes of customers.
Switching the order of the sums in (12), we can write N 1 , the average number of high priority customers, as Substituting (82), (86) into (88), Little's result (11) gives the average high priority waiting time, With (13), the average low priority waiting time is Though (89), (90) come from an approximate solution, in the p → 0 and p → ∞ limits they give the correct waiting times. Taking first the limit p → 0, we find With p = 0, high and low priority customers are treated identically. The PEP reduces to a M/M/1 queue with arrival rate λ and service rate µ, for which the waiting time is as given by (91). Conversely, if we make the overtake rate infinite, then high priority customers arriving at the queue will immediately overtake any waiting low priority customers. In this limit, high priority customers see an M/M/1 queue with arrival rate λ 1 and service rate µ, and indeed we find The waiting time for low priority customers is This can be found by directly taking the limit, or via the requirement that N 1 +N 2 = n . Figure 6 shows W 1 , W 2 plotted as a function p. Again we see good agreement between simulation results and the calculated values. Increasing p interpolates between a first come first served queue (p = 0) and strict prioritisation according to customer class (p → ∞). In designing a queueing system, one would choose p to give the desired high priority waiting time, within the constraints imposed by the asymptotic limits.
The greatest response in W 1 , defined as the maximum value of |dW 1 /dp|, occurs at p = 0 in Figure 6(a), and so there is a strong relative benefit to high priority customers using even small values of p. In Figure 6(c) the value of the parameters give rise to an inflection point at p > 0, and hence the largest response in W 1 occurs at some positive value of p. A sufficient condition for such an inflection point to occur + is d 2 W 1 /dp 2 | p=0 < 0, which happens if and only if Then d 2 W 1 /dp 2 must change sign as lim p→∞ d 2 W 1 /dp 2 > 0. For these values of the parameters the benefit to high priory customers of switching on p is relatively small compared to the penalty for low priority customers.

Conclusion
In this paper we introduced a new model, the prioritising exclusion process, and analysed its stationary behaviour. In the unbounded phase, we used domain wall theory to derive the exact stationary distribution, and found a further subdivision of this phase into finite and infinite jam phases. In the bounded phase, although domain wall theory did not give exact results, it led to two complementary approximate solutions. From the direct application of the domain wall ansatz we found that the shape of the density profile could again be understood in terms of a jam, in this case either localised at the service + This is simpler than trying to solve dW 2 1 /dp 2 = 0.
end, or able to grow and fill the lattice. The second approach, following from a current conservation equation, allowed accurate calculation of customer waiting times. The connection to queueing theory guided our approach to the problem and interpretation of results. The recent work on the APQ [3] points to future directions. It would be of interest to compute the complete waiting time distribution, and to compare it to that for the APQ. Additionally, the Maximum Priority Process introduced in [3] bears a strong resemblance to the jam of high priority customers in the PEP, although the exact correspondance is not clear.