{'fraction_non_alphanumeric': 0.047165471519415504, 'fraction_numerical': 0.015938303341902313, 'mean_word_length': 3.9209054593874835, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Age of information without service preemption

When designing a message transmission system, from the point of view of making sure that the information transmitted is as fresh as possible, two rules of thumb seem reasonable: use small buffers and adopt a last-in-first-out policy. In this paper, we measure freshness of information using the"age of information"performance measure. Considering it as a stochastic process operating in a stationary regime, we compute not just the first moment but the whole marginal distribution of the age of information (something important in applications) for two well-performing systems. In neither case do we allow for preemption of the message being processed because this may be difficult to implement in practice. We assume that the arrival process is Poisson and that the messages have independent sizes (service times) with common distribution. We use Palm and Markov-renewal theory to derive explicit results for Laplace transforms. In particular, this approach can be used to analyze more complex last-in-first-out systems with larger buffer sizes.


Introduction
Traditionally, networked systems performance is measured with respect to buffer sizes and delays. Relatively recently, there has been a shift in what is considered important both in terms of design and performance. The introduction of the so-called "age of information" (usually abbreviated as AoI), defined as the elapsed time since the information possessed by a monitor is generated and time stamped at the source, has received a lot of attention. The reason is simple: in several applications it is the freshness of information that is important rather than the correct transmission of all packets. Examples include virtual reality, online gaming, weather reports, autonomous driving, stock market trading, decision systems for an airplane, power systems, sensor/actuator systems and other other "cyber physical" systems.
We start by precisely defining the concept of AoI in general. Consider a message processing facility with one input stream of arriving messages. The facility can be a single queue or a complex network system. An arriving message has a certain positive "size" (expressed in time units and interpreted as processing or service time) and three things can happen: (i) the message is immediately rejected upon arrival; (ii) the message is accepted but rejected while in the system; (iii) the message is successfully transmitted as soon as it is processed in its entirety. We are interested in the time that the latter will happen in comparison to the time that the message arrives in the system. If messages are labeled by integers in a way that the message with label n ∈ Z arrives at time T n ∈ R and T m < T n if m < n, if T n + ∆ n denotes the time at which message labeled n leaves the system either by being rejected or successfully transmitted, and if ψ n is a binary variable indicating the latter (ψ n = 1 if message n is successful or 0 if not), then we let D(t) := sup{T n + ∆ n : n ∈ Z, T n + ∆ n ≤ t, ψ n = 1}, A(t) := sup{T n : n ∈ Z, T n + ∆ n ≤ t, ψ n = 1}, (2) and define the AoI at time t by α(t) := t − A(D(t)).
Quite simply, D(t) is the time of the last successful departure before t and A(D(t)) is the arrival time of the message that departed at time D(t). This definition is quite general, that is, it does not depend on the details of the system design.
Typically, systems that adopt freshness of information as performance measure should be designed so that its AoI "be as small as possible". The last phrase can mean several things. For example, it can mean that the quantity α(t) is least for all t under identical traffic conditions. Or it could mean least in terms of an expectation or another functional of the process. Adopting AoI as a performance criterion immediately poses some simplifications over traditional queueing theory performance criteria but also presents some new challenges.
Suppose that the processing facility is a queue with one server and buffer consisting of a finite or infinite number of cells. One of the cells of the buffer is occupied by the message being processed and the rest of the cells are occupied by stored messages. If we are free to design the buffer and the service policy as we wish, how do we do this if we wish to keep the AoI "as small as possible"?
It is reasonable to conjecture that every time a message arrives we process it immediately (after all, we are not interested in obsolete information.) That is, even if the server is busy at the moment of arrival, the currently served message is immediately discarded and the new one starts being processed. Systems working in this manner are service-preemptive. It also seems reasonable to serve messages in reverse order of arrival: the most recent message must be served first (LIFO).
One may thus conjecture that LIFO-preemptive (meaning: service preemptive) is "best". But numerical examples and simulations show that this is false depending on the model assumptions. In particular, a single buffer system with no service preemption (called B 1 below) has smaller AoI both in expectation and stochastically under particular assumptions on the message size distribution [14,6,10]. In fact, we conjectured in [10] that the so-called P 2 system (see below and Figure 1 for the definition) has lower AoI than B 1 . In this paper, inter alia, we resolve this issue.
The simplest systems with small-size buffer and no service preemption are defined next. One of them, denoted as B 2 , is nothing else but a single-server queue with buffer of size 2 and blocking. That is, an incoming message finding the buffer full is immediately discarded. The other one, denoted as P 2 , also works without service preemption. An arriving message in P 2 finding the buffer full displaces or "pushes out" the stored message. See Figure 1 for a typical scenario in P 2 . Figure 1: The P 2 system. The lower cell contains the message being processed (if any). Message a arrives at an empty system and is immediately processed. Message b arrives and is stored in cell the upper cell. While the buffer still contains a and b, a third message c arrives and immediately kicks b out. When a completes being processed it departs and c moves to the lower cell.
More generally, we define, for n ≥ 2, B n and P n as follows. The B n system is simply a single-server queue with buffer of size n, operating under FIFO (First In First Out) policy and blocking of any incoming message finding the buffer full. The P n system, for n ≥ 2, works as follows: messages are stored in an order that is reverse to their order of arrival; so if there is a message being processed in cell 1 at time t, the message in cell 2 arrived last before t while the message in cell n is the oldest; a new message arriving at a full buffer is always stored in cell 2, displacing the other messages upwards and pushing out the one sitting in cell n (oldest one). For n ≥ 2, P n has no service preemption.
Note that in some cases, queuing and service policies may be subject to technological constraints (e.g., whether non-FIFO dequeueing or preemptive service policies are feasible, and what aspects of the queueing system are observable). In particular, B 2 may be the best policy if LIFO dequeueing, queue pushout, and service preemption are all infeasible but blocking is, cf. Section 5.6.
For n = 1, the system B 1 is simply a single-buffer blocking queue: an arriving message is immediately rejected if there is a message in the system. The P 1 system is the single-buffer push-out system: an arriving message pushes out the currently processed message and takes its place. The P 1 and B 1 systems were analyzed under very general conditions in [6,10].
Of all systems P n , B n , n ≥ 1, the P 1 system is special because it is the only one for which service preemption is allowed.
In this paper, we analyze the AoI processes and derive the stationary AoI distribution for the B 2 (in Section 3) and P 2 (in Section 4) systems under a Poisson arrival process but generally distributed message sizes. The distribution for P 2 case was previously derived in [6]. The technique used herein is different from that of [6,10] and is easily generalizable to other systems, particularly to LIFO "dequeuing" policies P n for n > 2 [11]. Indeed, we use the classical embedding technique, valid for queueing systems with Poisson arrivals (see, e.g. [4]), giving that the system sampled at certain epochs (the departures of successful messages in our case) has a Markovian property. This, of course, depends crucially on the Poisson property of the arrival process, so, for more general arrival processes (as in the case of [6,10]) we need a different method that is substantially more complex and shall not be considered herein.
Under our assumptions, and because we consider finite buffers, it holds that there is a unique stationary version of the stochastic process α in all systems considered. We will not offer any reasons for this technical result, but only point out that even existence may not hold if the arrival and message size processes are neither independent nor renewal, and point out the difficulties by referring to [2]. We shall always be considering the stationary version. Hence α(t) has the same distribution for all t. This is precisely what we are interested in describing. We note that computing the expectation is, in general, not that much easier than deriving the whole distribution. We also note that deriving the distribution is essential in case that we are interested not just in maintaining a low AoI on the average but also in maintaining the tail of the probability distribution small. While our techniques are generalizable to all P n and B n , for any positive integer n, we only work with n = 2 for the following reason. We claim that the random variables α P n (t), α B n (t), n ≥ 3, are stochastically larger than α P n (t), α B n (t), n ∈ {1, 2}. Although, currently, we have no full proof of this fact, we have enough evidence to pose this as a conjecture. We partially prove and justify this conjecture in Section 5.6.
Throughout the paper, we let λ be the rate of the (Poisson) arrival process and G the distribution of a typical message size σ, a random variable that is positive with probability 1 and has finite expectation denoted by 1/µ. We thus only assume that λ > 0 and µ > 0 (but σ may have infinite variance). It is assumed that the message sizes are i.i.d. copies of σ and independent of the arrival process. The ratio ρ = λ/µ is referred to as traffic intensity.
The main results of the paper are Theorems 1 and 2. We here present a special case. When the message sizes are i.i.d. exponential, having (for notational convenience) rate µ = 1, we shall show as a corollary that, in steady-state, the value of AoI at some (and hence any) point of time, has density in the P 2 and B 2 cases, respectively, where when λ 1; while, for λ = 1, the densities become (For general µ, simply replace λ by λ/µ and t by µt in the foregoing expressions.) These results are by themselves generalizations of what is already in the literature. For instance, in [14] the expectations for B 2 and P 2 , see (33) and (23) in Corollaries 2 and 4 infra, have been computed under the same probabilistic assumptions. Notice that, in particular, and the limiting functions are probability densities as well. The first one is Erlang(3) and the second Erlang (2). Similar limits can be obtained for P n and B n , without computations, simply by considering the system dynamics. In fact, we can interpret B ∞ as a single server queue with infinite buffer operating under the FIFO discipline. From the point of view of AoI, this system is worst and should not be considered. Our practical rule of thumb says that one should store at most one message and discard everything beyond that, insofar as keeping AoI low is the goal. This rule of thumb may not be always optimal but it is frequently close to optimal.
The rest of the paper is organized as follows. We explain the basis of the technique used in Section 2 and see why it is absolutely general, as long as the system, possibly a network, has Poisson arrivals. The B 2 system is considered in Section 3 and the P 2 in Section 4. Section 5 contains a number of interesting observations. First it provides comparisons of the systems analyzed in this paper, together with the systems P 1 and B 1 (analyzed under more general assumptions in [6,10]). Second, it explains what the limits of the AoI are when λ → ∞. Third, it gives a way to understand the AoI for P 1 when the message size is deterministic. In this case the Laplace transform is not invertible (we only invert it numerically) but the moments have an interesting combinatorial explanation. Fourth, we justify our observation that the "best system" is among P n , B n , for n = 1, 2. We conclude with some words for future work in Section 6.

Basic framework
We discuss the technique used in the analysis for all systems described in the introduction from the point of view of the distribution of the age of information. By this phrase, we will always mean that the age of information process α(t), t ∈ R, is stationary and that we shall be interested in the distribution of α(t) for some, and hence all, t which will be taken to be the point t = 0. The goal is to derive a "fixed point equation" for α(0), see equation (11) below. We note right away, that the present analysis is different than that of paper [10, 6] as we take advantage of an embedded Markov chain. The arrival process is always taken to be Poisson process on R (=time) with rate λ. As mentioned above, T n is the arrival time of message labeled n. Its size is σ n . The collection of message sizes are i.i.d. and independent of the arrival process. Let be the distribution function of the typical size and let 1/µ be its expectation, assumed to be finite. Also assume that G(0) = 0. Abusing notation, we shall let G denote the probability measure defined by the function G(x) and byĜ(s) its Laplace transform: Recall that T n + ∆ n is defined as the time at which message n departs either because it was pushed out or rejected or because it was successfully processed (ψ n = 1 in the latter case). See discussion around (1) and (2) where these symbols were introduced. Then the number of messages in the system at time t ∈ R is given by Note that if the message is immediately rejected then ∆ n = 0 and so this message does not contribute to ξ. We let {S m , m ∈ Z} := {T n + ∆ n : n ∈ Z, ψ n = 1}, and, thinking of the two sets as sequences, {S m } is a subsequence of {T n + ∆ n } and is enumerated so that We note that ξ is right-continuous for all t. Recalling the notions of Markov renewal and semi-Markov processes, see, e.g., [1,VII.4], our first observation is: For both B 2 and P 2 cases, the process ξ(t), t ∈ R, is a semi-Markov process [4, Ch.10] with respect to the points S n , n ∈ Z. Moreover, the distribution of ξ is the same in both B 2 and P 2 cases.
This follows easily by standard arguments in queueing theory, for instance in the analysis of a queue with Poisson arrivals; see, e.g., [4, Ch. 6, Sec. 5]. Thus, ξ does not "see" the difference between B 2 and P 2 . The distinction between these two will become important in the next section when we discuss the details about α in each case.
We further assume that the arrival process together with the process ξ are stationary under a probability measure P. (This assumption is non-vacuous; we shall not elaborate on this further but refer the reader to [2] for an exposition of techniques used to establish it.) We refer to the intervals [S n , S n+1 ) as segments and split the paths of ξ into union of paths over segments. See Figure 2. By convention, we assume that the segment labelled 0 contains the point t = 0. Denote by P 0 Figure 2: What ξ(t) looks like when S n ≤ t < S n+1 , regardless of the policy used.
the Palm probability of P with respect to the point process {S n }. We refer to [2] for this concept. Intuitively, P 0 is P conditional on the event that 0 ∈ {S n , n ∈ Z}. Hence P 0 (S 0 = 0) = 1. Let The sequence {K n } is a Markov chain with state space {0, 1} while {(S n , K n )} is the Markov renewal sequence [1,4] associated to the semi-Markov process ξ. The latter has transition kernel as follows easily by considering the cases of Figure 2. Letting x → ∞ in (6) we obtain the transition matrix for the Markov chain {K n }, from which it is evident that K n , n ≥ 1, is not just Markovian but also a sequence of independent Bernoulli random variables with Figure 2 shows the four different types of segments depending on the values of K n and K n+1 . We next and, using the kernel (6), we obtain From (8), (9), and (7) we obtain the Laplace transform of the segment length: From this, we obtain the mean length of a segment as We shall henceforth use the abbreviation E(X; A) for the expectation of a random variable X on the event A, that is, the quantity E(X1 A ). The following result depends entirely on the semi-Markov property of ξ.
Proof. The Palm inversion formula [1,2] applied to the P-stationary process α gives Take a look at (3) and notice that the process α is right-continuous. Its set of discontinuities is {S n }. Moreover, it increases at unit rate on each segment: To see this, notice that, for S n ≤ t < S n+1 , we have D(t) = D(S n ) = S n , by the definition of D in (1), and so A(D(t)) = A(D(S n )) = A(S n ). Since, from the definition (3), α(t) = t − A(D(t)) for all t, we have whenever S n ≤ t < S n+1 . Writing this for t = S n , we have and so (13) is obtained by subtracting the last two displays. In particular, S 0 = 0 and α(t) = α(0) + t for t ∈ [S 0 , S 1 ), P 0 -a.s. Hence, for i = 0, 1, where the last equality follows from the fact that α(0) and S 1 − S 0 are conditionally independent given {K 0 = i}, a consequence of the semi-Markov structure of the process {ξ(t)}, see Lemma 1. Using expressions (8) and (9) and adding the terms in (14) we obtain the numerator of (12). The denominator is given by (10). This shows the validity of (11).

Remark 1.
It should be clear that (11) holds for a much larger class of systems with one (or several independent) Poisson arrival process(es). For example, we may define B n to be an extension of B 2 when the buffer has n cells where messages are stored according to the order of their arrivals and a message arriving to a full buffer is immediately rejected (the so-called M/GI/1/n queue). On the other hand, we may define P n to be an extension of P 2 : messages are stored in an order that is reverse to their order of arrival; so if there is a message being processed in cell 1 at time t, the message in cell 2 arrived last before t while the message in cell n is the oldest; a new message arriving at a full buffer is always stored in cell 2, displacing the other messages upwards and expels the one sitting in cell 1 (oldest one). In both B n and P n , the process ξ is semi-Markov and thus Proposition 1, depending only on this semi-Markov property, applies and formula (11) holds. In fact, one can assert that proposition holds for networks with i.i.d. message sojourn times, e.g., due to a single bottleneck server.. We shall not attempt to formalize this further in this paper.

The B 2 system
Recall that the B 2 system is the same as a single server queue with buffer size 2. Under our Poisson assumption for the arrival process and i.i.d. assumptions for message sizes, this is further denoted by M/GI/1/2 in standard queueing theory. We are, however, interested not in the number of messages in the system neither on message delays but, rather, on the age of information process α. Assuming that α is stationary, we compute the Laplace transform of α(0) under P by using (11) which requires knowledge of E 0 [e −sα(0) ; K 0 = j], j = 0, 1. To obtain the latter, we consider the segment [S −1 , S 0 ) and further condition on K −1 and summarize the results in Lemma 2 below. In what follows, we let τ, σ be two independent random variables, where τ is exponential with rate λ and σ has distribution G.
Proof. Recall that the K n are i.i.d. with distribution (7): P 0 (K n = 0) =Ĝ(λ). We shall consider the four cases separately and, in each case, we shall be referring to the definition (3) to figure out what α(0) is. Figure 3. But and so Figure 3. Since we obtain    Case 4. Again, we have to consider two consecutive segments to realize that see Figure 5. The two random variables (S −1 − T −1 ) and (S 0 − S −1 ) are conditionally independent given that K −1 = 1 and thus This completes the proof. DefineĜ This is the Laplace transform of a probability measure G I that is well-known in renewal theory: If we consider a renewal process with points, say, Z n , n ∈ Z, such that Z 0 = 0 and Z n+1 − Z n having distribution G, then there it has a stationary version (with no point at 0) and in such a way that Z 1 has distribution G I .

Theorem 1.
For B 2 , the Laplace transform of the stationary Age of Information is given by Proof. Summing (15) and (16) we obtain Substituting the last two lines into the right hand side of (11) we obtain which gives (20) if we take into account the definition ofĜ I . (20) gives the stationary AoI as a sum of three independent random variables. In particular, the middle term in the right hand side of (20) corresponds to the Laplace transform of the random variable (σ − τ) + . Moreover, the expectation of α(0) is given by
We obtained this corollary directly from the Laplace transform (20) where we recognize that . Notice that if the message size has high variance then so does Eα(0). In particular, Eα(0) = ∞ if x 2 dG(x) = ∞. Rather than seeing this as a problem, one should change the point of view and adopt another function of α as a performance measure, for instance, Eα(0) p for some p < 1.

Corollary 2.
For B 2 , with G being exponential with mean 1/µ we have Inverting the last Laplace transform gives a measure with density equal to (4). Interestingly, as λ → ∞ we immediately see from (22) that E[e −sα(0) ] → (µ/(s + µ)) 3 , the Laplace transform of the sum of 3 i.i.d. exponentials. See Section 5.4 for an explanation of this.

The P 2 system
We remind the reader that P 2 differs from B 2 in that the arriving message is always admitted by replacing the message (if any) sitting in the second cell of the buffer, see Figure 1. Again, P 2 is not service-preemptive: once a message starts being processed it will not be interrupted. The strategy for obtaining the Laplace transform of α(0) is the same as before. We make use of (11) of Proposition 1 which needs computation of the quantities involving α(0) in its right-hand side. The analog of Lemma 2 is Lemma 3 below which looks conspicuously the same. In fact, the first two formulas are identical. The last two differ.
Proof. 1) When K −1 = 0, K 0 = 0 or when K −1 = 0, K 0 = 1 the AoI same as in the B 2 system, the reason being that the number of messages in the system is always at most 1, see Figure 3.
2) Suppose next that K −1 = 1, K 0 = 0. In Figure 6 we depict the two scenaria corresponding to the possible values of K −2 , namely (K −2 , K −1 , K 0 ) = (0, 1, 0) or (1, 1, 0). In both cases, (3) and the system dynamics imply that Therefore, and the first factor on the right is easy: To evaluate E 0 [e −sV | K −1 = 0, K 0 = 1] we note that, V is the distance of the last Poisson point inside the interval (T −1 , S −1 ) (in the left scenario of Figure 6) or the interval (T −1 , S −1 ) in the right scenario. (In both cases the length of the interval is that of a message size conditioned on containing at least one Poisson point.) To obtain the Laplace transform of V look backward in time starting from S −1 until the first Poisson point appears and condition on the event that this occurs between S −1 and S −2 . Thus, the density of V at v > 0 is which gives Putting these together we obtain (26).
3) Finally, assume that K −1 = 1, K 0 = 1. This situation is similar to the previous one and thus will be treated succinctly. We are guided by Figure 7. Firstly, we have  Secondly, the argument used to derive (28) can be used here again with no changes to obtain .
Putting these together we obtain (26) as well.

Theorem 2.
For P 2 , the Laplace transform of the stationary Age of Information is given by Proof. Adding up (24) and (25) of Lemma 3 and similarly (26) and (27) we obtain Substituting these expressions in the numerator of (11), and recalling the definition (19) of G I , we obtain (29).
An alternative expression for (29) is: Corollary 3. In expression (29) we recognize that α(0) is equal in distribution to the sum of three independent random variables, of which the middle one,Ĝ(λ) + λ λ+s 1 −Ĝ(s + λ) , is the Laplace transform of the random variable τ1 τ>σ . Moreover, One should compare this to the expectation for the P 1 system, [14,10,6], .

Comparisons and optimality
Slightly abusing notation, we write α P n instead of α P n (0); To further simplify life, we shall now use normalized units, assuming µ = 1. We draw conclusions from the work above, as well as the results of [14,6,10], attempting to justify our claim that "small buffers suffice". We first summarize observations regarding P n , B n , n = 1, 2, and then consider larger n.

Recalling formulas for P 1 and B 1
Concerning the P 1 system we have, from [10,Corollary 4], On the other hand, for B 1 , [10, Corollary 9(i)], gives We now have information about all systems that we now compare. The comparisons depend on the message size distributions. We choose to consider two "extremes". First, exponentially distributed size, second, deterministic, representing maximal and minimal randomness. The observations are summarized in plots rather than formulas because the latter, albeit explicit in almost all cases (but see §5.5 below for an exception), are not succinctly presentable.
The odd system is B 1 . For small ρ, M B 1 (ρ) is worst (highest). For large ρ, M B 1 (ρ) is between M P 1 (ρ) and M P 2 (ρ). There is also an intermediate zone, where M B 1 (ρ) is between M P 2 (ρ) and M B 2 (ρ). We can also ask whether the comparisons above remain true in the sense of stochastic ordering. Recall that a real random variable X is stochastically smaller than Y, and write Note that stochastic ordering is a partial order in the space of probability measures on the real line so two random variables may not be comparable at all. The information is obtained by inverting the Laplace transforms (22) and (32) which give the densities (4) and (5), respectively. It is also easy to invert the Laplace transforms (34) and (35). Integrating the densities from t to ∞, we obtain the complementary distribution functions, better summarized in a couple of plots: Figure 9: P(α > t) plotted against t for small ρ on the left and high ρ on the right.
The following figure gives plots of variances as functions of ρ. Note that they all converge to integers.

Deterministic message sizes
We now assume that P(σ = 1) = 1: message sizes are all equal to 1 with probability 1. We can thus easily obtain M(ρ) in all cases by setting σ = 1 in the formulas of Corollaries 1 and 3 and in (35) and (34). They are summarized in Figure 11. We observe that Whereas P 1 was best in the exponential case, it is now worst. In fact, as lim ρ→∞ M P 1 (ρ) = ∞.
The worst system, from the point of view of expectation, is thus P 1 . However, as in the exponential case, B 1 is the odd system in that it is between B 2 and P 1 for small ρ, but M B 1 (ρ) < M P 2 (ρ) for all large enough ρ. However, the difference between the two goes to 0 as ρ → ∞. We can easily see that lim ρ→∞ M B 1 (ρ) = lim ρ→∞ M P 2 (ρ) = 3/2, while lim ρ→∞ M B 2 (ρ) = 5/2. We again ask whether the comparisons in the mean translate to stochastic comparisons. We observe that The reason for this is clear: when ρ is high, the message being processed is constantly interrupted. Since the message size is always 1 no message has a chance to ever be completed. To obtain information about P(α P 1 > x) for all x, we resort to numerics as the Laplace transform (34) withĜ(s) = e −s is not invertible. For further discussion on the distribution of α P 1 see §5.5 below. Luckily, the Laplace transforms for all other variables, α B 1 , α B 2 , α P 2 are all invertible and correspond to random variables with densities that can all be analytically computed. We summarize the comparisons of the distributions in the plot below. Our observation is then that whereas α B 1 is not comparable to any of the other three random variables. Figure 13 shows the densities for α P 2 and α B 2 for various values of ρ. Variance plots are in Figure 14. We have lim ρ→∞ var P (α B 1 ) = lim ρ→∞ var P (α P 2 ) = lim ρ→∞ var P (α B 2 ) = 1/12.

High traffic asymptotics
"High traffic asymptotics" refers to the regime ρ → ∞. Even though we have no explicit formulas for P n or B n when n ≥ 3, we can easily obtain asymptotics from the system dynamics. Sketch of proof. In both systems, the buffer consists of n cells. The message being processed sits in cell 1. In P n , the freshest message is either in cell 1, in which case all other cells are empty, or in cell 2. When ρ is high there is always a message being processed in cell 1 and the freshest message is in cell 2. Hence, at any time t, the AoI α P n (t) equals the service time of the message in cell 2 plus the remaining service time of the message in cell 1. These are two independent random variables. The first one is distributed as σ.
The second is distributed as σ I since the system is stationary. For B 1 , we can obtain the limit from the Laplace transform of (35). It is easy to to see that lim ρ→∞ E[e −sα B 1 ] =Ĝ(s)Ĝ I (s) and so For general n, when ρ is high, the AoI α B n (t) equals the remaining service time of the message in cell 1 (in distribution equal to σ I ) plus the time elapsed until the beginning of its service which is, in distribution, equal to the sum of n independent service times.

Remark 2.
When σ = 1 with probability 1, σ I is a uniform random variable in the interval [0, 1]. Hence σ 1 + · · · + σ n + σ I = n + σ I and the variance of this random variable is 1/12, in agreement with the observation around Figure 14 for B 1 and B 2 . Similarly, for P 2 , the asymptotic variance is again 1/12. In fact, the limits in Proposition 2 also explain the asymptotic shapes of the densities in Figure 13. The limits of the variances in Figure 14 for B 1 , B 2 , P 2 are also explainable in the light of the proposition above.
It remains to see what the limit of α P 1 is as ρ → ∞. This should be considered separately as the limit very much depends on the distribution of σ. If σ = 1 with probability 1, we explained above why α P 1 converges to a random variable that takes value ∞ with probability 1. In fact, this should be true if σ has a distribution whose support is at positive distance from 0. If σ is exponential with mean 1, we see directly from (34), that lim ρ→∞ E[e −sα P 1 ] = 1/(s + 1). Thus the limit of α P 1 depends both on the tail of the distribution and on its behavior at 0.

On the distribution of α P 1 for deterministic message size
We now complete the discussion in §5.3 by giving some more information on α P 1 , when σ = 1 with probability 1, whose distribution is not explicitly computable but has some interesting properties, including a combinatorial explanation of all of its moments. Another reason we devote a little more ink on α P 1 is that it seems to be an upper bound on the age of information so long as message sizes are close to being deterministic. From This Laplace transform cannot be analytically inverted. However, since L m (s) as a function of a complex variable s has no singularity on the closed right-half plane Re(s) ≥ 0, we used the inversion formula [13, together with a numerical approximation of this extended Riemann integral in order to obtain information about the tail of the distribution of α P 1 which is plotted in Figure 12 as a dotted line. We can make a few remarks about f m .
First, it is obviously a probability density function for all m ≥ e since we know that inf ρ>0 e ρ /ρ = e. One might conjecture that f m remains a probability density function for all m ≥ 0. However, L m seizes to be completely monotone [5,XIII.4] for m small enough and thus, the conjecture is false. To see this, it is easy to see that L m (s) < 0 for s in a neighborhood of zero if (and only if) m < 1.
We strengthen the conjecture by claiming that Conjecture 1. Let m ≥ 0. Then L m (s) = 1/(mse s + 1) is the Laplace transform of some random variable if and only if m = 0 (corresponding to a trivial random variable) or m ≥ e.
Second, since L m (s) is infinitely differentiable at all s ≥ 0, we have that all moments of α P 1 exist. Using a formal series expansion, we can easily express the p-th moment in terms of the polynomial with m = e ρ /ρ, and then show that this is correct. It is easy to see that Q p (z) has a combinatorial interpretation. It is the generating function of the sequence (p) k k p−k , 1 ≤ k ≤ p, where (p) k = p(p − 1) · · · (p − k + 1), counting the number of ways to form k labeled groups, each with a distinct leader, using p different people. For values and other properties, see [15]. One can also see that, for p large, that is, the p-th moment of an exponential random variable with the same mean.

The best systems
We now return to the problem of choosing the best system so that we keep AoI "as small as possible". Even though we have no proof for the optimal system, we have enough reasons to justify making the following conjecture.

Conjecture 2.
Consider the collection P n , B n , n = 1, 2, . . . Assume that each system is driven by a Poisson arrival process of rate λ. Then, regardless of the message size distribution, α I < st α J for all I ∈ {P 1 , B 1 , P 2 , B 2 } and all J ∈ {P n , B n , n ≥ 3}.
Evidence for this conjecture is provided by the results of [6,10], the results in this paper and the following observations. First, it is clear that α P n (t) ≤ α B n (t), for all t and all n ≥ 2 provided that all systems are driven by identical arrival processes and the same sequence of message sizes. In other words, this is a pathwise inequality. Similarly, α B 2 (t) ≤ α B 3 (t) ≤ · · · ≤ α B ∞ (t), for all t.
One can show that we cannot expect a similar pathwise inequality for the P n systems. But when ρ is sufficiently large, we showed that, for all n ≥ 2, α P n (t) is approximately distributed as σ + σ I , so there is no reason to believe that α P n+1 will improve α P n at high ρ. A crucial step in proving the veracity of the last conjecture would be to show that, in stationarity, Thus if the conjecture is true then it would be irrelevant to consider any system other than P 1 , P 2 , B 1 , B 2 insofar as stochastically minimizing the stationary AoI is concerned. However, see [12].

Some final words
Using the Markov embedding and Palm inversion formula, we derived the stationary AoI distribution of B 2 and P 2 under Poisson message arrivals and generally distributed message sizes (processing times). The AoI of these systems and two other systems with low AoI, B 1 and P 1 , were compared for exponential and deterministic service times, which, in some sense, are two extremes. We paid particular importance to their complementary distribution functions which play a role in important performance requirements. P 1 has generally lower AoI for exponentially distributed message sizes, while P 2 had lower AoI for deterministic message sizes when the traffic load was sufficiently low. The performance of B 1 is interesting, having smallest AoI among these four considered policies in some cases. The B 2 system may need to be used instead of these other three owing to technological constraints.
The rules of thumb derived can roughly be summarized as follows: If the message sizes are deterministic or nearly so then it is best to use B 1 or P 2 , which is pretty close to B 1 . In particular, P 1 seems to be an upper bound for AoI and this is the reason that we paid some special attention to it in §5.5 (where we had to resort to analytical tricks to approximate it, as there is no closed-form formula for the distribution). On the other hand, if message sizes are "very random", we expect the opposite: P 1 performs best stochastically so. Granted, the study in this paper has been done only for Poisson arrivals and so, to be able to analyze general renewal arrivals and service times one should use a different method which we leave for future work. We should also mention that dynamic policies should also be studied, that is, policies that decide on rejection or not of a message based on information such as the time the message has spent in the system, the arrival process up to the current time, etc. [12].