The RESET and MARC techniques, with application to multiserver-job analysis

Introduction

Multiserver queueing theory predominantly emphasizes models in which each job utilizes only one server (one-server-per-job models), such as the M/G/k. For decades, such models were popular in the study of computing systems, where they provided a faithful reflection of the behavior of such systems while remaining conducive to theoretical analysis. However, one-server-per-job models no longer reflect the behavior of many modern computing systems.

Multiserver jobs: In modern datacenters, such as those of Google, Amazon, and Microsoft, each job now requests many servers (cores, processors, etc.), which the job holds simultaneously. A job's ''server need'' refers to the number of servers requested by the job. In Google's recently published trace of its ''Borg'' computation cluster [1,2], the server needs vary by a factor of 100,000 across jobs. Throughout this paper, we will focus on this ''multiserver-job model'' (MSJ), in which each job requests some number of servers, and concurrently occupies that many servers throughout its time in service (its ''duration'').

• Section 6: We build upon Section 5 to characterize MSJ FCFS mean response time using our RESET technique. • Section 7: Our results apply to a very broad class of models which we call ''finite skip'' models, and which we define in this section. • Section 8: We empirically validate our theoretical results.

Fixed number of servers, FCFS service

In this setting, most results focus on characterizing the stability region. Rumyantsev and Morozov characterize stability for an MSJ system with an arbitrary distribution of server needs, where the duration distribution is exponential and independent of server need [9]. This result can implicitly be seen as solving the saturated system, which has a product-form stationary distribution in this setting. A setting with two job classes, each with distinct server needs and exponential duration distributions has also been considered [20,21]. In this setting, the saturated system was also proven to have a product-form stationary distribution, which was also used to characterize the stability region.

The only setting in which mean response time E[T ] is known is in the case of k = 2 servers and exponential duration independent of server need [15,16]. In this setting, the exact stationary distribution is known. Mean response time is open in all other settings, including whenever k > 2.

Advanced scheduling policies

More advanced scheduling policies for the MSJ system have been investigated, in order to analyze and optimize the stability region and mean response time.

The MaxWeight policy was proven to achieve optimal stability region in the MSJ setting [22]. However, its implementation requires solving an NP-hard optimization problem upon every transition, and it performs frequent preemption. It is also too complex for response time analysis to be tractable. The Randomized Timers policy achieves optimal throughput with no preemption [23,24], but has very poor empirical mean response time, and no response time analysis.

In some settings, it is possible for a scheduling policy to ensure that all servers are busy whenever there is enough work in the system, which we call ''work conservation''. Work conservation enables the optimal stability region to be achieved and mean response time to be characterized. Two examples are ServerFilling and ServerFilling-SRPT scheduling policies [1,17]. However, the work-conservation-based techniques used in these papers cannot be used to analyze non-work-conserving policies such as FCFS.

Prior work on the saturated system

The saturated system is a queueing system which is used as analysis tool to understand the behavior of an underlying non-saturated queueing system [13,14]. Baccelli and Foss state that it is a ''folk theorem'' that the threshold of the stability region of the original open queueing system is equivalent to the completion rate of the saturated system: If the completion rate of the saturated system is , then the original system is stable for arrival rate if and only if < < = [14]. Baccelli and Foss give sufficient conditions for this folk theorem, known as the ''saturation rule'', to hold rigorously. These conditions are mild, and are easily shown to hold for the MSJ FCFS system. The strongest stability results in the MSJ FCFS system have either been proven by characterizing the steady state of the saturated system, or are equivalent to such a characterization [9,12,20].

Our novel contribution is characterizing the mean response time behavior of an original system by reducing its analysis to the analysis of a saturated system. All previous uses of the saturated system focused on characterizing stability. Specifically, our main theorem, Theorem 4.2, characterizes mean response time in terms of Sat (y), < , and Y Sat d . These functions and random variables are specific to the saturated system. They are defined in Section 3, and can be calculated in closed-form by analyzing the saturated system, as we walk through in Appendix C.

M/M/1 with Markovian service rate

The M/M/1 with Markovian service rate (MMSR) has been extensively studied since the 50's, often alongside Markovian arrival rates [25][26][27][28][29][30]. A variety of mathematical tools have been applied to the MMSR, including generating function methods, matrixanalytic and matrix-geometric methods, and spectral expansion methods [25,26,30,31]. However, these methods primarily result in numerical results, rather than theoretical insights [30,32].

More is known for special cases of the MMSR system [33,34]. For instance, the case where arrival rates alternate between a high and low completion rate at some frequency has received specific study. In this case, the generating function can be explicitly solved as the root of a cubic equation [35], but the resulting expression is too complex for analytical insights. In this simplified setting, scaling results [36][37][38][39] and monotonicity results [29] have been derived, but those results do not extend to more complex MMSR systems.

By contrast, our MARC technique provides the first explicit characterization of mean response time for the general MMSR system, up to an additive constant.

Drift method and MARC

The drift method is a popular method for steady-state analysis of queueing models (see, e.g., [18,19,40,41]). In the drift method, one takes a suitable test function (also known as a Lyapunov function) of the system state and computes its instantaneous rate of change starting from each state under the transition dynamics, which is called the drift. The drift can be formally calculated using the instantaneous generator, defined in Section 3.9. One then utilizes the fact that the drift of any test function has zero steady-state expectation (Lemma 3.2) to characterize system behavior in steady state, through metrics such as mean queue length. Through more specialized choices of test function, stronger results such as State Space Collapse can also be proven.

In prior work which analyzes the mean queue length, the test function is usually a quadratic function of the queue length. For instance, when analyzing the MaxWeight policy in the switch setting, an appropriate test function is ≥ i q 2 i , where q i is the number of jobs present of each class i [42]. For such a test function to provide useful information about the expected queue length, the system must achieve a constant work completion rate whenever there are enough jobs in the system. This constant work completion rate ensures that the test function's drift depends linearly on the queue length, allowing the mean queue length to be characterized. However, in our MSJ system, the work completion rate is variable regardless of the number of jobs in the system, because servers may always be left empty if a job in the queue requires more servers than are available. As a result, the standard test functions for the drift method do not provide useful information about the MSJ system.

Our innovation is to construct a novel test function that combines the queue length q and a new quantity called relative completions, defined in Section 3.8. Our use of relative completions allows us to ensure that the test functions f and f MSJ , defined in Definitions 5.1 and 6.1, have drift which depend linearly on the queue length. As a result, we can apply the drift method with our novel test functions to characterize mean queue length in the MSJ system, and hence characterize mean response time.

We call this technique the MArkovian Relative Completions (MARC) technique: using relative completions to define a test function for the drift method, to apply the drift method to systems with variable work-completion rate.

Multiserver-job model

The MSJ model is a queueing model in which each job requests an integer number of servers, the server need, for some duration of time, the service duration. Each job requires concurrent service on all of its servers throughout its duration. Let k denote the total number of servers in the system.

We assume that each job's server need and service duration are drawn i.i.d. from some joint distribution. The duration distribution is phase type, and it may depend on the job's server need. This assumption can likely be generalized, which we leave to future work. We assume a Poisson( ) arrival process.

We focus on the first-come first-served (FCFS) service discipline. Our RESET technique also applies to many other scheduling policies, as we discuss in Section 7. Under FCFS, jobs are placed into service, one by one, in arrival order, as long as the total server need of the jobs in service is at most k. If a job is reached whose server need would push the total over k, that job does not receive service until sufficient completions occur. We consider head-of-the-line blocking, so no subsequent jobs in arrival order receive service. It has been shown that in the MSJ FCFS setting, there exists a threshold < , such that the system is stable if and only if < < [13,14]. We assume that < < .

Note that the only jobs eligible for service are the k oldest jobs in arrival order. We conceptually divide the system into two parts: the front and the back. When the total number of jobs in the system is at least k, the front consists of the k-oldest jobs in the arrival order; otherwise, the front consists of all jobs in the system. The back consists of all jobs that are not in the front. Note that all of the jobs which are in service must be in the front, because at most k jobs can be in service at a time, and service proceeds in strict FCFS order. The front may also contain some jobs which are not in service, whenever less than k jobs are in service. All of the jobs in the back are not in service.

Equivalence between MMSR-sat and At-least-k

Now we are ready to connect the MMSR and At-least-k (Ak) systems. Consider the subsystem consisting only of the front of the Ak system, i.e., the k oldest jobs in the Ak system. This subsystem is stochastically identical to the saturated system. Whenever a job completes at the front of the Ak system, a new job enters the front, either from the back (i.e. the jobs not in the front) or from the auxiliary arrival process, if the back is empty. This matches the saturated system's completion-triggered arrival process.

As a result, the Ak system is stochastically equal to an MMSR-⇡ system whose service process ⇡ is identical to the saturated system. We refer to this system as the ''MMSR-Sat'' system. To clarify this equivalency, assume the Ak system starts in a certain front state y with an empty back. Then equivalently the MMSR-Sat system starts empty, with its service process in state y. If a job in the Ak system completes its service, a new job is generated, and the same transition occurs in the service process in the MMSR-Sat system. Similarly, assume a job arrives to the Ak system and enters the back. At the same time, a job arrives in the MMSR-Sat system and enters the queue. Through this mapping, the two systems are sample-path equivalent.

The above arguments are summarized in Lemma 3.1 below.

Notation

MSJ system state: A state of the MSJ system consists of a front state, y MSJ , and a number of jobs in the back q MSJ . A job state consists of a server need and a phase of its phase-type duration. The front state y MSJ is a list of up to k job states. If q MSJ > 0, then y MSJ must consist of exactly k job states, while if q MSJ = 0, y MSJ may consist of anywhere from 0 to k job states. Let Y MSJ denote the set of all possible front states y MSJ of the MSJ system. For instance, in our running example,

Note that in the first three states, the back must be empty, so q MSJ must equal 0.

MMSR system state: In the MMSR system, let ⇡ denote the Markov chain that modulates the service rate. As a superscript, it signifies ''the MMSR system controlled by the Markov chain ⇡''. A state of the MMSR-⇡ system consists of a pair (q ⇡ , y ⇡ ). The queue length q ⇡ is a nonnegative integer. The state y ⇡ is a state of the service process ⇡, and Y ⇡ is the state space of ⇡.

Because the MMSR-Sat system is stochastically equal to the Ak system, with the MMSR-Sat system's queue length equal to the Ak system's back length, we use the superscripts Sat and Ak interchangeably. A state of the Ak system is a pair (q Ak , y Ak ). In contrast to the MSJ system, y Ak always consists of exactly k job states. In particular, Y Ak oe Y MSJ . MMSR service process: When the service process ⇡ transitions from state y to y ® , there are two possibilities: Either a completion occurs, which we write as a = 1, or no completion occurs, which we write as a = 0. We therefore define ⇡ y,y ® ,a to denote the system's transition rate from front state y to front state y ® , accompanied by a completions, where a À {0, 1}. For instance, in our running example Sat [1,1], [1,2],1 = 2_3. Let the total completion rate from state y be denoted by ⇡ y, ,1 = ≥ y ® ⇡ y,y ® ,1 . For instance, in our running example Sat [1,1], ,1 = 2. MSJ service transitions: Let MSJ y,y ® ,a,b denote a transition rate in the Multiserver-job system, where y, y ® , and a have the same meaning as in Ak y,y ® ,a . Let b = 1 q>0 denote whether this transition is associated with an empty back (b = 0), or an occupied back (b = 1). Note that if y Ã Y Ak , then b = 0 for all nonzero MSJ y,y ® ,a,b , while if y À Y Ak , then both values of b are possible. Note that ≈y À Y Ak , MSJ y,y ® ,a,1 = Ak y,y ® ,a . If a job arrives to the MSJ system and finds that the front state y has fewer than k jobs (y Ã Y Ak ), a fresh job state is sampled and appended to y. Let S be a random variable denoting a fresh job state, let i be a particular fresh job state, let p i be the probability P(S = i), and let y i be the new front state with a job in state i appended. For instance, in the running example, p 1 = 2_3, p 2 = 1_3.

Steady-state notation: We will study the time-average steady states of each of these systems, which we write

Let Y ⇡ d denote the departure-average steady state of the MMSR service process ⇡: the steady-state distribution of the embedded DTMC which samples states after each departure from ⇡.

Let X ⇡ denote the long-term throughput of the service process ⇡. Let < ⇡ denote the threshold of the stability region of the MMSR-⇡ system. The MMSR-⇡ system is stable if and only if < < . Note that X ⇡ = < ⇡ by prior results relating the saturated system to the stability region of the original system [13,14]. In particular, X Sat = < Sat = < , where < denotes the threshold of the stability region of the MSJ FCFS system. We will typically write < to avoid confusion between X Sat and a random variable.

A concrete example of this notation is provided in Section 4.1.

Relative completions

Key to our MARC technique is the novel idea of relative completions, which we define for a general MMSR-⇡ system. Let y 1 and y 2 be two states of the service process ⇡. The difference in relative completions between two states y 1 and y 2 is the long-term difference in expected completions between an instance of the service process starting in state y 1 and one starting in y 2 . Specifically, let C ⇡ (y, t) denote the number of completions up to time t of the service process of ⇡ initialized in state y at time t = 0. Then let ⇡ (y 1 , y 2 ) denote the relative completions between states y 1 and y 2 :

We prove that ⇡ (y 1 , y 2 ) always exists and is always finite in Lemma A.1. We also allow y 1 and/or y 2 to be distributions over states, rather than single states. Specifically, we will often focus on the case where y 2 , rather than being a single state, is the steady state distribution Y ⇡ . In this case, note that

When it is clear from context, we write ⇡ (y) to denote ⇡ (y, Y ⇡ ). The relative completions formula for this case simplifies:

The relative completions function ⇡ (y) can be seen as the relative value of a given state y under a Markov reward process whose state is a state of the service process ⇡ and whose reward is the instantaneous completion rate in a given state y.

Generator

We also make use of the instantaneous generator of each of our queueing systems, which is the stochastic equivalent of the derivative operator. The instantaneous generator is an operator which takes a function from system states to real values, and returns a function from system states to real values. The latter function is known as the drift of the original function.

The generator operator is specific to a given Markov chain. Let ⌘ be a Markov chain, and let G ⌘ denote the generator operator for ⌘, which is defined as follows:

For any real-valued function of the state of ⌘, f (q, y),

Importantly, the expected value of the generator in steady state is zero:

Let f be a real-valued function of the state of a Markov chain ⌘. Assume that the transition rates of the Markov chain ⌘ are uniformly bounded, and

Proof. Follows from [43,Proposition 3]. Discussion deferred to Appendix A. ∏

We show in Appendix A that (2) holds for the MSJ, MMSR, At-least-k, and Saturated systems, for any f (q, y) with polynomial dependence on q.

Theorem 4.1 (Mean Response Time Asymptotics of MMSR Systems

). In the MMSR-⇡ system, the expected response time in steady state satisfies

where ⇡ is the relative completions function defined in Section 3.8:

To understand (3), first note that the dominant term has order ⇥(

). This is the equivalent of the ⇥( 1 1*⇢ ) behavior seen in simpler systems such as the M/G/1/FCFS. Next, to understand the numerator, examine the ⇡ (Y ⇡ d , Y ⇡ ) term. ⇡ , the relative completions function, smooths out the irregularities in completion times, so that the function q * ⇡ (y) has a constant negative drift.

⇡ is the analog of the remaining size of the job in service in the M/G/1. When a generic job arrives, it sees a time-average state of the service process, namely Y ⇡ . When it departs, it leaves behind a departure-average state of the service process, namely Y ⇡ d . The difference in relative completions between these states captures the asymptotic behavior of mean response time. The overall numerator,

term in the M/G/1/FCFS mean response time formula. We walk through calculating ⇡ (y), < ⇡ , and Y ⇡ d explicitly and in closed-form in Appendix C. Now that we have characterized the mean response time of the MMSR system, we can use this result to characterize the MSJ FCFS system. With our RESET technique, we show that the MSJ FCFS system has the same mean response time, up to an O (1) term, as the MMSR system whose service rate is controlled by the saturated system, or equivalently the At-least-k system.

Theorem 4.2 (Mean Response Time Asymptotics of MSJ Systems

). In the multiserver-job system, the expected response time in steady state satisfies

Empirically, the O (1) term is very small, as seen in Fig. 2(a) in Section 8. To clarify the meaning of the O (1) term in Theorem 4.2, let us restate the theorem explicitly:

In the multiserver-job system, for any joint duration and server need distribution and for any number of servers k, there exist constants c l and c h such that for all arrival rates < < ,

Rather than calculating Sat (Y Sat d , Y Sat ) in Theorem 4.2, we can calculate the equivalent value in the simplified saturated system (SSS) (due to Lemma 3.3). Define SSS , Y SSS d , and Y SSS analogously to the primary saturated system.

Corollary 4.1. In the MSJ FCFS model,

Corollary 4.1 follows from Theorem 4.2 because Sat (y 1 , y 2 ) is defined based on the completion times in the primary saturated system, and by Lemma 3.3, the SSS can be coupled to have the same completion times as the primary saturated system.

The quantities SSS (y), < , and Y SSS d can be calculated explicitly and in closed-form for any given parameterized distribution of server need and job duration, and any number of servers k, giving an explicit closed-form bound on mean response time. We walk through this calculation in Appendix C, and give the explicit closed-form expressions for a 2-server setting in Appendix C.2, to demonstrate the technique.

Example for demonstration

We now demonstrate applying Theorem 4.2 and Corollary 4.1 to characterize the asymptotic mean response time of our running example from Section 3.4. See Appendix C for a more extensive example, handling a setting with parameterized completion rates and arrival probabilities.

We start with the MSJ system. First, we convert to the Ak system, whose front has state space

By the RESET technique, this only increases mean response time by O (1). By Lemma 3.1, the Ak system is identical to a MMSR-Sat system. By Lemma 3.3, the Sat system is equivalent to Simplified Saturated System (SSS), which has state space

For the rest of this section, we focus on the SSS, leaving the superscript implicit. Transitions between these states only happen as a result of completions, leading to the following transition rates:

Now, we can calculate the steady states Y SSS and Y SSS d of the SSS's CTMC and DTMC respectively, and calculate the throughput

. Now, we can solve for (y), defined in (1). To do so, we split up the completions E[C(y, t)] into the time until the first completion, and the time after the first completion. For example, starting in state y = [1,1], the first completion takes an expected 1 2 second, during which 1 completion occurs, compared to the long-term average rate 1 2 < = 9 20 completions. The system then transitions to a new state, with corresponding (y). This gives rise to the following equation:

We use the same process to derive a system of equations that uniquely determines (y), given in Corollary D.1. We solve for (y) for each state y:

All decimals are exact. We can then average over the distribution

). We can therefore apply Theorem 4.2 and Corollary 4.1 to characterize the asymptotic mean response time of the original system:

MARC proofs

We start by analyzing the M/M/1 with Markovian service rate ⇡ (MMSR-⇡). Our main result in this section is the proof of Theorem 4.1, a characterization of the asymptotic mean response time of the MMSR-⇡ system.

The main challenge is choosing an appropriate test function f (q, y), to leverage (2), the fact that

via this approach, it is natural to choose a function f which is quadratic in q, because G ⇡ is effectively a derivative. However, if we choose f 1 (q, y) = 1 2 q 2 , the expression G ⇡ ˝f1 (q, y) will have cross-terms in which both q and y appear, preventing further progress.

Instead, our key idea is to use relative completions ⇡ in our test function:

The ⇡ (y) term smooths out the fluctuations in the system's service rate, so that the quantity q * ⇡ (y) has a constant drift of * < ⇡ whenever q > 0. This choice of test function ensures that G ⇡ ˝f ⇡ (q, y) separates into a linear term dependent only on q and a term dependent only on y. The separation allows us to characterize E[Q ⇡ ], and hence E[T ⇡ ], in Theorem 4.1.

Let u = 1{q = 0 • a = 1} denote the unused service caused by a given transition. Only completion transitions (a = 1) can cause unused service.

We start by decomposing G ⇡ ˝f ⇡ (q, y), into a term linearly dependent on q, and terms dependent only on y, a, and u: Lemma 5.1. For any state (q, y) of the MMSR-⇡ system,

Proof deferred to Appendix D We can now characterize the mean response time of the MMSR-⇡ system. We will use the fact that by Lemma 5.1, G ⇡ ˝f ⇡ (q, y) decomposes into a term linearly dependent on the queue length q, and terms that are not dependent on q except through the unused service u. We define c 0 (y, q) to comprise the later group of terms. We also define c 1 (y) and c 2 (y), which are simpler functions that are closely related to c 0 (y, q). Definition 5.2. Define c 0 (y, q), c 1 (y), and c 2 (y) as follows:

⇡ .

We will show that these functions' expected values,

This fact is crucial to our proof of Theorem 4.1.

Theorem 4.1 (Mean Response Time Asymptotics of MMSR Systems). In the MMSR-⇡ system, the expected response time in steady state satisfies

Proof. In this proof we omit ⇡ in the subscript of ⇡ (y) and in the superscript of ⇡ y,y ® ,a . We start from Lemma 5.1, which states that G ⇡ ˝f (q, y) = ( * < ⇡ )q + c 0 (y, q). Applying Lemma 3.2, we find that

We therefore focus on c 0 (q, y):

Let us separate out the terms where u appears in c 0 (y, q) from the terms without u:

Note that in the time-average steady state Y ⇡ , the fraction of service-process completions that occur while the queue is empty (i.e. where u = 1) is 1 * < ⇡ , because jobs arrive per second, and < service-process completions occur per second. As a result,

Note that a f 1 and u f 1, because at most 1 job completes at a time. Note that (y ® ) is bounded by a constant over all y ® , because y ® À Y ⇡ , which is a finite state space. Thus, the u_2 * a * (y ® ) term in ( 8) is bounded by a constant. As a result, (8) contributes

Let us now simplify c 2 (y), using the fact that a = 0 or 1:

We now apply Lemma D.3 to simplify the summation term of c 2 (y). Lemma D.3 states that 1

Thus, taking the expectation of the summation term of c 2 (y) over y Ì Y ⇡ , we find that

Note that for any x,

Note that in the ô < ⇡ limit, O ( 1 ) = O (1). Consider the ô 0 limit: E[T ⇡ ] is bounded for small . Likewise,

⇡ is bounded for small . As a result, the two differ by O (1):

RESET proofs

To characterize the asymptotic behavior of mean response time of the MSJ system, we use the At-least-k (Ak) system, which is stochastically equal to the MMSR-Sat system. The MARC results from Section 5 allow us to characterize the MMSR-Sat system. To prove that the MSJ FCFS and Ak systems have the same asymptotic mean response time behavior, our key idea is to show that Y MSJ and Y Ak , the steady states of their fronts, are ''almost identical''.

To formalize and prove the relationship between Y MSJ and Y Ak , we design a coupling in Section 6.1 between the MSJ system and the Ak system. We use a renewal-reward argument based on busy periods to prove Lemma 6.2, which states that under the coupling,

Then, in Section 6.2, we combine Theorem 4.1 and Lemma 6.2 to prove Theorem 4.2, our main result, in which we give the first analysis of the asymptotic mean response time in the MSJ system, by reduction to the saturated system. Theorem 4.2 parallels the proof steps that Theorem 4.1 uses to characterize the MMSR system, using Lemma 6.2 to prove that the equivalent proof steps hold for the MSJ system.

We will make use of a test function f MSJ (q, y) for the multiserver-job system which is similar to f ⇡ (q, y), which was defined in Definition 5.1. Definition 6.1. For states y À Y Ak , f MSJ (q, y) := f Ak (q, y) = f Sat (q, y).

Coupling between At-least-k and MSJ

To show that the Ak system and the MSJ system have identical asymptotic mean response time, we define the following coupling of the two systems. We let the arrivals of the two systems happen at the same time. We couple the transitions of their front states based on their joint state (q MSJ , y MSJ , q Ak , y Ak ). If y MSJ = y Ak , q MSJ > 0, and q Ak > 0, the completions happen at the same time in both systems, the same jobs complete, the same job phase transitions occur, and the jobs entering the front are the same. We call the two systems ''merged'' during such a time period. Note that under this coupling, if the two systems become merged, they will stay merged until q MSJ = 0 or q Ak = 0. If the systems are not merged, the two systems have independent completions and phase transitions, and independently sampled jobs.

The two systems transition according to synchronized Poisson timers whenever they are merged, and independent Poisson timers otherwise. Because all transitions are exponentially distributed, this poses no obstacle to the coupling.

We want to show that under this coupling, the two systems spend almost all of their time merged, in the limit as ô < . Specifically, we will show that the fraction of time in which the two systems are unmerged is O (1 * < ). This implies Lemma 6.2, which is the key lemma we need for our main RESET result, Theorem 4.2. Lemma 6.2 (Tight Coupling). In the MSJ system, for any < < , we have the following two properties:

Property 2: P

where property 2 holds under the coupling in Section 6.1.

To prove Lemma 6.2, we prove two key lemmas:

• Lemma 6.3: Whenever the two systems are unmerged, the expected time until the systems become merged is O (1). • Lemma 6.4: Whenever the two systems are merged, the expected time for which they stay merged is ⌦ ( 1 1* _ < ).

We then use a renewal-reward approach to prove Lemma 6.2.

Lemma 6.3 (Quick Merge). From any joint MSJ, Ak state, for any ✏ > 0, under the coupling above, the expected time until y MSJ = y Ak , q MSJ g k + 1, and q Ak g k + 1 is at most m 1 (✏) for some m 1 (✏) independent of the arrival rate and initial joint states, given that À [✏, < ).

Lemma 6.4 (Long Merged Period). From any joint MSJ, Ak state such that y MSJ = y Ak , q MSJ g k + 1, and q Ak g k + 1, the expected time until q MSJ = 0, q Ak = 0, or y MSJ ë y Ak , is at least

1* _ < for some m 2 independent of the arrival rate and initial joint states, given that < < .

Proofs deferred to Appendix G Using Lemmas 6.3 and 6.4, we can prove Lemma 6.2:

, and probabilities are bounded. Therefore, we will focus on the case where g ✏, where we can apply Lemmas 6.3 and 6.4.

Let us define a good period to begin when

, and end when Q MSJ (t) = 0 or Q Ak (t) = 0. Let a bad period be the time between two good periods. Note that throughout a good period, the front states are merged (Y MSJ (t) = Y Ak (t)) and both queues are nonempty. To bound the fraction of time that the joint system is in a good period, we introduce the concept of a ''y < -cycle''. Let y < be an arbitrary state in Y Ak . Let a y < -cycle be a renewal cycle whose renewal points are moments when a bad period begins, and

for some designated state y < . We will show that a y < -cycle has finite mean time. Given that fact, we can apply renewal reward to derive the equations below:

Note that Q MSJ (t) = 0 or Y MSJ (t) ë Y Ak (t) only during a bad period, so the two probabilities in (11) and ( 12) are both bounded by the fraction of time spent in bad periods. By Lemma 6.3 and Lemma 6.4, the expected length of a bad period is at most m 1 and the expected length of a good period is at least m 2 1* _ < , conditioned on any initial joint state. Let Z be a random variable denoting the number of good periods in a y < cycle. Note that good and bad periods alternate.

E[total time per y

If a y < -cycle has finite mean time, then we also have E[Z] < ÿ because each good period and bad period take a positive time. Plugging the above inequalities into (11) and ( 12), we derive Properties 1 and 2:

It remains to show that a y < -cycle has finite mean time. We first use a Lyapunov argument to show that the joint states of the two systems return to a bounded set in a finite mean time. Consider the Lyapunov function f MSJ (q MSJ , y MSJ ) + f Ak (q Ak , y Ak ). Its drift is:

Applying Lemma 5.1 to the Ak system, G Ak ˝f Ak (q Ak , y Ak ) = ( * < )q Ak + c 0 (y Ak , q Ak ),

where c 0 (y, q) is defined in Definition 5.2. Note that c 0 (y, q) is a bounded function because (y) is bounded, by Lemma A.1. Let c Ak max be the maximum of c 0 (y, q). For all y Ak , q Ak , G Ak ˝f Ak (q Ak , y Ak ) f ( * < )q Ak + c Ak max .

By similar reasoning, applying Lemma 6.1, there exists a c MSJ max such that

Let c max = max(c Ak max , c MSJ max ). Consider any q Ak g 2c max +1

< * . Then for any y Ak , G Ak ˝f Ak (q Ak , y Ak ) f *c max * 1.

Similarly, for any q MSJ g 2c max +1 < * and any y MSJ ,

Let c cap = max{ 2c max +1

< * , k + 1}. We define the bounded set S as S = (q MSJ , q Ak , y MSJ , y Ak ): q MSJ f c cap , q Ak f c cap .

By the calculation above, outside S,

In particular, outside of S, either q MSJ > c max or q Ak > c max , yielding a drift term f *c max * 1, outweighing the term where q is small. Thus, by the Foster-Lyapunov theorem [44,Theorem A.4.1], the system returns to S in finite mean time.

We call a period of time inside the bounded set S an S-visit. Each S-visit has a finite mean time because there is a positive probability of having a lot of arrivals in the next second and leaving S. Moreover, as proved above using the Lyapunov argument, the time between two S-visits has finite mean.

Each S-visit has a positive probability of ending the y < -cycle. To prove this, we construct a positive probability sample path of beginning a good period with q MSJ = q Ak and ending the good period in (0, 0, y < , y < ), while remaining in S.

• First, we have a lot of completions in the two systems, completely emptying both. q MSJ = q Ak = y MSJ  = 0. Next, k jobs arrive. Now q Ak = k and q MSJ = 0. During this time y MSJ ë y Ak .

• Then k jobs complete in the Ak system, no jobs complete in the MSJ system, and the newly generated Ak jobs are sampled such that y MSJ = y Ak , while q MSJ = q Ak = 0. • Next, k + 1 jobs arrive, and a good period begins.

• Finally, k + 1 jobs complete in both systems, ending with y MSJ = y Ak = y < , and q MSJ = q Ak = 0. Now a y < -cycle ends, and the next begins.

All of these events have strictly positive probability and are independent of each other, so their joint occurrence has strictly positive probability as well. Thus, the length of a y < -cycle is bounded by a geometric number of S-visits, each of which has finite mean time, completing the proof. ∏

Proof of Theorem 4.2

We now are ready to prove our main theorem, Theorem 4.2, progressing along similar lines as Theorem 4.1 and making use of Lemmas 5.1 and 6.2. First, we restate several definitions from Definition 5.2, specialized to Ak system: Definition 6.2. Recall the definitions of c 0 (y, q) and c 1 (y) from Definition 5.2:

We also make use of a key fact about c 1 (y), from ( 9):

Throughout this section, whenever we make use of results from Section 5, we set ⇡ = Sat. In particular, we make use of c 0 (y, q) and c 1 (y), from Definition 5.2. Theorem 4.2. In the multiserver-job system, the expected response time in steady state satisfies

Proof. We will show that the MSJ model has the same asymptotic mean response time as the Ak system. We will make use of the test function f MSJ (q, y), from Definition 6.1. Recall from Lemma 6.1 that G MSJ ˝f MSJ (q, y) = G Ak ˝f Ak (q, y)1 q>0 + 1 q=0 O (1).

Extensions of RESET: Finite skip models

While our main MSJ result, Theorem 4.2, was stated for the MSJ FCFS model, our techniques do not depend on the details of that model. Our RESET technique can handle a wide variety of models, which we call ''finite skip'' models: Definition 7.1. A finite skip queueing model is one in which jobs are served in near-FCFS order. Only jobs among the n oldest jobs in arrival order are eligible for service, for some constant n. Service is only dependent on the states of the n oldest jobs in arrival order, plus an optional environmental state from a finite-state Markov chain. Furthermore, jobs must have finite state spaces, and arrivals must be Poisson with i.i.d. initial job states. Definition 7.1 generalizes the work-conserving finite-skip (WCFS) class [1]. The MARC and RESET techniques can characterize the asymptotic mean response time of any finite skip model, via the procedure in Fig. 1. Additional finite skip MSJ models include nontrivial scheduling policies, including some backfilling policies; changing server need during service; multidimensional resource constraints; heterogeneous servers; turning off idle servers; and preemption overheads. For discussion of each of these variants, see Appendix H.

Accuracy of formula

In Fig. 2(a), we show that our predictions are an excellent match for the empirical behavior of the MSJ system in two different settings. In the first, there are k = 3 servers and jobs have server needs of 1, 2, and 3. In the second, there are k = 20 servers, and jobs have server needs 1 and 20. We thereby cover a spectrum from few-server-systems to many-server-systems, demonstrating extremely high accuracy in both regimes. The O (1) term in (15) is negligible in both of these examples.

In Fig. 2(b), we compare mean response time in two settings with the same size distribution and stability region, but which have very different . We discuss these settings further in Section 8.2.

The first setting has k = 4, and 42% of jobs have server need 1, while 58% of jobs have server need 4. The second setting has k = 10, and 10% of jobs have server need 1, while 90% of jobs have server need 10. The settings' stability regions are nearidentical, with thresholds < 4 ˘0.5413, < 10 ˘0.5411, and their size distributions, defined as duration times server need over k, are both Exp (1). However, our predictions for mean response time are very different in the two settings: (Y Sat d ) 4 ˘0.3271, (Y Sat d ) 10 ˘1.850. The k = 10 setting considered here, with its relatively large value of (Y Sat d ), is an especially difficult test-case. Nonetheless, our predictions are validated by the simulation results in Fig. 2(b).

In Fig. 3, we illustrate the relative error between our predicted mean response time and the simulated mean response time for the four settings depicted in Fig. 2. In all four settings, as the arrival rate approaches < , the threshold of the stability region, the relative error converges to 0.

Note that the convergence rate is slowest in the k = 10 setting, which also has the largest (Y Sat d ) value. We further explore the relationship between (Y Sat d ) values and convergence rates in Appendix I. We find that such a correlation exists in some settings, but it is not robust or reliable.

Understanding the importance of

Our results show that the relative completions function is key to understanding the response time behavior of non-workconserving systems such as the MSJ FCFS system. This is in contrast to work-conserving systems, in which response time is determined by the size distribution and load [1]. This contrast is illustrated by Fig. 2(b), in which we compare mean response time in two settings with the same size distribution and stability region, but which have very different .

The differing mean response time behavior in these two settings is caused by the difference in waste correlation. In the k = 10 case, wasteful states persist for long periods of time: If a 1-server job is the only job in service, it takes more time for it to complete than in the k = 4 system. Thus, in the k = 4 case, wasteful states are more short-lasting. This difference in waste correlation produces the differences in (Y Sat d ) and in mean response time. This example highlights a crucial feature of MSJ FCFS: The failure of work conservation injects idiosyncratic idleness patterns in to the system. To characterize E[T ], we need to characterize these patterns, which the RESET and MARC techniques enable us to do for the first time.

Conclusion

We introduce the RESET and MARC techniques. The RESET technique allows us to reduce the problem of characterizing mean response time in the MSJ FCFS system, up to an additive constant, to the problem of characterizing the M/M/1 with Markovian service rate (MMSR), where the service process is controlled by the saturated system. The MARC technique gives the first explicit characterization of mean response time in the MMSR, up to an additive constant. Together, our techniques reduce E[T MSJ ] to two properties of the saturated system: the departure-average steady state Y Sat d , and the relative completions function (y 1 , y 2 ). Our RESET and MARC techniques apply to any finite skip model, including many MSJ generalizations.

We also introduce the simplified saturated system, a yet-simper variant of the saturated system with identical behavior. We empirically validate our theoretical result, showing that it closely tracks simulation at all arrival rates .

An important direction for future work is to analytically characterize the relative completions (y 1 , y 2 ) for specific MSJ FCFS settings, such as settings where Y Sat d is known to have a product-form distribution [9,20].

Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Next, we calculate the throughput X ⇡ of the service process ⇡, which by prior results [14] is equal to the threshold of the MMSR-⇡ stability region, < ⇡ :

Next, we calculate the departure-average steady state Y ⇡ d . Recall that Y ⇡ d is the steady-state distribution of the embedded DTMC which samples states just after each departure from ⇡. To calculate P(Y ⇡ d = y) from P(Y ⇡ = d), we divide by the expected time spent in state y per visit, 1 y, , , and multiply by the probability that the transition into state y was a completion:

where Z ⇡ is a normalization constant. Finally, we calculate the relative completions function ⇡ (y). To do so, we use the system of equations given in Corollary D.1:

(C.4)

Next, we use (C.3) to calculate Y d , the departure-average steady-state. Note that all transitions are completions, so (C.3) simplifies to the following:

Note that this is a product-form distribution. This is a special case of the product-form behavior that was established for the general 2-class exponential MSJ setting [12,20]. Finally, we use (C.4) and (C.5) to derive (y) for each state y. Because all transitions are completions, (C.4) simplifies to the following:

Now, let us substitute in our expressions for < and the transition rates and simplify. First we characterize ([1, 1]):

Next ([1, 2]):

Finally, we characterize ([2]):

Note that our final equations, (C.7), (C.8), and (C.9), are redundant: We can omit any one and still calculate (y), up to an additive constant. From these equations, we find that

3) simply splits up the completions from time 0 to t + t ® into the completions from time 0 to t, and the completions from time t to t + t ® . Therefore,

where in the second inequality we replace t ® with t + t ® in the second term, which will not change the limit because t ® and t + t ® are both going to infinity. Plugging the above calculations into (D.2), we get

where in the last inequality we use the fact that lim tô0

(the instantaneous completion rate at state y). ∏ Lemma D.2. For any f (q, y) which is a real-valued function of the state of the MMSR-⇡ system,

Proof. In this proof we omit ⇡ in the subscript of ⇡ (y) and in the superscript of ⇡ y,y ® ,a for readability. Recall the definition of the generator

which can be interpreted as the instantaneous rate of change of the function

) can change either due to an arrival event, or a transition event of the Markov chain ⇡. An arrival event happens with rate , and causes Q ⇡ (t) to change from q to q + 1, so arrival events contribute

to G ⇡ ˝f (q, y). A transition event of the Markov chain ⇡ from y to y ® À Y ⇡ accompanied by a À {0, 1} completions happens with rate y,y ® ,a . Such a event causes (Q ⇡ (t), Y ⇡ (t)) to change from (q, y) to ((q * a) + , y ® ), so it contributes y,y ® ,a f ((q * a) + , y ® ) * f (q, y)

to G ⇡ ˝f (q, y), for each y ® À Y Ak and a À {0, 1}. This proves the expression in the lemma statement. ∏

As a corollary of Lemma D.1 and Lemma D.2, we can derive a forward recurrence for ⇡ (y) := ⇡ (y, Y ⇡ ). Solving the resulting system of equations, together with the fact that ⇡ (Y ⇡ ) = 0, gives the value of ⇡ (y).

Corollary D.1. For any MMSR-⇡ system and any state y

where y, , is the total transition rate out of state y.

Moreover, if all transitions in ⇡ are associated with completions (if a always equals 1), then the recurrence simplifies:

Proof. Start with Lemma D.1:

Here we write ⇡ (y) as a shorthand for ⇡ (y, Y ⇡ ).

Expand the left-hand side of (D.4) using Lemma D.2:

Note that Lemma D.2 simplifies because ⇡ (y) does not depend on q. Now we can perform algebraic manipulation to complete the proof:

Note that if all transitions are associated with completions, e.g. if a = 1, then ⇡ y, ,1 = ⇡ y, , ∏ Lemma 5.1. For any state (q, y) of the MMSR-⇡ system,

Proof. In this proof we omit ⇡ in the subscript of ⇡ (y) and in the superscript of ⇡ y,y ® ,a for readability. To calculate G ⇡ ˝f ⇡ (q, y), we begin by applying Lemma D.2:

Recall that the unused service u = 1{q = 0•a = 1}, so (q * a) + = q * a + u. We can decompose (D.7) into two terms, with and without q:

The coefficient of q in (D.8) can be simplified considerably using Lemma D.1. Note that either u = 0 or q = 0, because new jobs are only generated if the queue is empty. As a result, qu = 0. We can therefore further simplify the q-term in (D.8):

Substituting (D.9) into (D.8), (D.8) into (D.7), and performing some rearrangement, we find that

In the MMSR-⇡ system, the departure average distribution Y ⇡ d is given by 1

Proof. We will show that

As an intermediate step, let Y ⇡ DT MC be the transition-average steady state of the Markov chain ⇡. P(Y ⇡ DT MC = y) is the fraction of state-visits that are visits to y, in the embedded DTMC of ⇡.

Let y, , be the total transition rate out of state y:

Note that the CTMC that controls Y ⇡ and the DTMC that controls Y ⇡ DT MC visit the same states in the same order, but that Y ⇡ stays in state y for Exp( y, , ) time for each visit. As a result,

where a ⇡ is a normalization constant. Specifically, a ⇡ is the long-term transition rate, which can be calculated as the reciprocal of the average time per visit to a state:

From Y ⇡ DT MC , we can calculate the fraction of transitions that move from a generic state y to another generic state y ® via a completion. Call this fraction p yôy ® ,1 :

Summing over all initial states y, we can find the fraction of transitions that are completions which result in the state y ® :

Let b ⇡ be the overall fraction of transitions that are completions. Conditioning on the transition into state y ® being a completion, we find that the probability that a generic completion results in state y ® is

b ⇡ . Combining all of the above equations, we find that

Recall that a ⇡ is the long-term transition rate, and that b ⇡ is the fraction of transitions that are completions. Thus, a ⇡ b ⇡ is the long-term completion rate X ⇡ = < ⇡ . ∏

Appendix E. Lemmas about G MSJ

Lemma E.1. For any f (q, y) which is a real-valued function of the state of the MSJ system, G MSJ ˝f (q, y) = (f (q + 1, y) * f (q, y)) 1 {yÀY Ak } (E.1)

Ak y,y ® ,a f ((q * a) + , y ® ) * f (q, y) (E.3)

Proof. Recall the definition of the generator

which can be interpreted as the instantaneous rate of change of the function f (Q MSJ (t), Y MSJ (t)) when (Q MSJ (t), Y MSJ (t)) is initialized in (q, y). Note that (Q MSJ (t), Y MSJ (t)) can change either due to an arrival event, or a transition event of the front state. An arrival event happens with rate , and its effect depends on whether y À Y Ak : if y À Y Ak , there are k jobs in the front, so Q MSJ (t) changes from q to q + 1, Y MSJ (t) remains unchanged; if y Ã Y Ak , there are strictly fewer than k jobs in the front, so Q MSJ (t) remains zero after the arrival, and Y MSJ (t) changes from y to y i with probability p i (append a fresh job in state i to the front state with probability p i ). Therefore, arrival events contribute (f (q + 1, y) * f (q, y))

to G MSJ ˝f (q, y), which are the terms in (E.1) and (E.2) in the lemma statement. As for the transition events of the front, a transition from state y to state y ® accompanied by a completions causes (Q MSJ (t), Y MSJ (t)) to change from (q, y) to ((q * a) + , y ® ). Such a transition happens with the rate MSJ y,y ® ,a,1 = Ak y,y ® ,a if q > 0 and y ® À Y Ak , and happens with rate MSJ y,y ® ,a,0 if q = 0. Therefore, the transition events of the front contribute

Ak y,y ® ,a f ((q * a) + , y ® ) * f (q, y)

MSJ y,y ® ,a,0 f ((q * a) + , y ® ) * f (q, y)

to G MSJ ˝f (q, y), which are the terms in (E.3) and (E.4) in the lemma statement. ∏ Lemma 6.1.

Proof. Let us begin by using Lemmas D.2 and E.1 to give expressions for G MSJ ˝f MSJ (q, y) and G Ak ˝f Ak (q, y). Note that whenever q > 0, G MSJ ˝f MSJ (q, y) is identical to G Ak ˝f Ak (q, y), because the two systems have the same transitions and because f MSJ (q, y) and f Ak (q, y) are identical.

Note also that whenever q = 0, both G MSJ f MSJ (q, y) and G Ak ˝f Ak (q, y) are O (1), because (y) is bounded by a constant for all y, because Y MSJ is finite.

As a result,

Lemma F.1. In the At-least-k system, for all <

Proof. In this proof we omit Ak in the subscript of Ak y,y ® ,a for readability. To prove Lemma F.1, it suffices to show that P(Q Ak = 0) = O (1 * < ), and that the non-busy periods (periods when Q Ak = 0) have expected duration ⌦ (1). The latter follows from the fact that all transitions have expected duration ⌦ (1).

To prove the former, let u(q Ak , y Ak ) be the rate at which new jobs are generated due to completions in a particular state (q Ak , y Ak ) of the At-least-k system. Note that u(q Ak , y Ak ) is positive only if q Ak = 0. The time-average value of u(q Ak , y Ak ) is the difference between the completion rate of the system and the Poisson arrival rate, because in steady state the total completion rate and total arrival rate must match. Thus,

It therefore suffices to show that there exists a constant c > 0 not dependent on such that E[ Y Ak , ,1 Q Ak = 0] g c. From an arbitrary state y Ak with q Ak = 0, the distribution of time until a completion next occurs does not depend on . Consider the probability of a completion happening in the next second, with no arrivals happening before that completion. This probability is nonzero, and only dependent only via the arrival process. The probability can be lower bounded away from zero by substituting a Poisson( < ) process instead. We can thus lower bound the completion rate over the next second with an empty back away from 0. This therefore provides a lower bound on the completion rate conditional on the back being empty, E[ Y Ak , ,1 Q Ak = 0], as desired. Calling that lower bound c, we have:

This completes the proof. ∏

Let Y Ak*BP denote the long-term-average distribution of the front state in the At-least-k system at the start of a busy period. We let the initial state distribution of the M ®® system be y M ®® Ì Y Ak*BP and q M ®® = 1. As a result, E[B M ®® ] = E[B Ak ], the expected busy period length of the At-least-k system. By Lemma F.1, we have E[B M ®® ] g m 4 1* _ < for some positive number m 4 independent of and y M ® . Now, we wish to show (G.2): that the length of the first busy period in M ® , initialized in an arbitrary initial front state y M ® and q M ® = k + 1, is also long in expectation.

To prove this, let us introduce a very fast Poisson process with a rate < given by

Note that < is at least as fast as the transition rate of M ®® in any state, and < is independent of . Let us define a coupling between the Poisson( < ) process and the M ®® system. Transitions in the M ®® system only occur when the Poisson( < ) increment occurs, where with some probability sampled on each Poisson increment a transition happens, and otherwise no transition occurs. In state y, a transition happens with probability + ≥ y ® ,a y,y ® ,a < .

Note that this probability is always less than 1, by the definition of < .

To lower bound E[B M ® ], the expected busy period length in the

where A 1 and A 2 are the following two events: 1. Event A 1 : the first increment of the Poisson ( < ) process takes at least 1 s. 2. Event A 2 : during the first second M ® has exactly k completions, after each of which the job entering the front of the M ® system is sampled to have the same server need as the corresponding job of the M ®® system, and then all the jobs transition to the same phase as in the M ®® system. At the end of the first second, M ® and M ®® have identical front states y and back lengths q = 1 after exactly k completions in the M ® system.

First, note that

is lower bounded by a positive constant for every such that ✏ f f < , so we can focus on

. Note that if events A 1 and A 2 occur, the M ® and M ®® systems have the same busy period length, because after 1 s, the two systems have identical states. Specifically, both systems become empty at the same time, which is the first time after each is initialized when each becomes empty.

As a result,

Note that Event A 2 is conditionally independent of the behavior of the M ®® system, given that Event A 1 occurs. As a result,

Notice that event A 1 is independent of the state of M ®® . Conditioning on the event A 1 merely increases the time of the first transition in M ®® , without altering the future updates of M ®® at all. As a result,

2) and (G.3) and letting m 2 = m 3 m 4 , we get the desired lower bound on the expected length of the good period. ∏

H.1. Nontrival scheduling policies: Backfilling

A common family of MSJ scheduling policies in practice are backfilling policies [46][47][48]. Under a backfilling policy, the scheduler begins by placing jobs into service in arrival order, as in the FCFS policy. However, once a job is encountered which does not fit in the available servers, additional jobs are considered for service. By doing so, the stability region and mean response time are improved relative to FCFS, though it is unclear whether the full stability region can be achieved [49]. Some backfilling policies give rise to finite skip models, and can thus be handled by the RESET technique.

As an example, consider the ''First Fit-k'' policy: The scheduler iterates through the first k jobs in arrival order, checking for each job whether it can be served in the available servers. Each job that fits is served. This policy only serves jobs among the k oldest in arrival order, so it can be handled by the RESET technique.

Beyond backfilling policies, more advanced packing policies can also be considered. For instance, for small k the scheduler could simply search over all subsets of the k oldest jobs and serve the subset with maximal total server need f k. This policy is also finite skip, and the RESET technique also applies.

H.2. Changing server need during service

The standard MSJ model assumes that jobs require a fixed service need throughout their time in service. However, in some settings, jobs may require a varying number of servers. For example, consider a fork-join model with simultaneous start. Suppose that each job is made of some number of tasks, each with independent duration, and each requiring 1 server. As the tasks complete, the server need of the job as a whole diminishes, freeing up space for other jobs to run. This setting still gives rise to a finite-skip model, and poses no difficulty to our RESET technique.

Another natural setting in which server needs change over time is the directed acyclic graph (DAG) setting, in which jobs are broken up into small segments of work, with potentially complex dependencies between segments. The DAG scheduling literature often focuses on scheduling the segments of an individual DAG job. It is natural to consider a scheduling setting where many DAG jobs arrive over time. Holding the DAG scheduling policy constant, this model effectively gives rise to a MSJ model where server needs can vary over time, and potentially vary dynamically in response to the service conditions. As long as the high-level scheduling policy deciding which DAG jobs to run is finite-skip, the model as a whole is finite-skip, and our RESET technique can characterize its asymptotic mean response time.

Appendix I. Empirical correlation between (Y Sat d ) and convergence rate

As discussed in Section 8, we have empirically noticed a correlation between large (Y Sat d ) values and slower convergence rates of our predicted value of E[T ] to the exact value, as ô < . Our predicted value of mean response time is:

We prove in Theorem 4.2 that E[T pred ] * E[T ] = O (1), ensuring that the two values reliably converge in the ô < limit in all settings, as illustrated in Section 8.

In this section, we further investigate this correlation by comparing (Y Sat d ) with the relative error E[T pred ]*E[T ]

for a pair of parameterized sequences of workload settings. The setting we investigate has k = 5 servers, with jobs having server need either 1 or 5. We set the arrival rate = 0.8 < , using 80% of the stability region. ) and the relative error between our prediction of mean response time and the true value, in two parameterized workload settings, both with k = 5 servers and server needs either 1 or 5. We alternately parameterize 1 , the completion rate of 1-server jobs, and p 1 , the fraction of 1-server jobs. Load _ < = 0.8. Simulated 10 8 arrivals.

We separately parameterize the fraction of 1-server jobs present, as well as the duration of 1-server jobs. First, we vary p 1 , the fraction of 1-server jobs from 1% to 99%, in 1% increments, while setting 1-server jobs to have duration Exp(1_5). Second, we set the duration of 1-server jobs to be Exp( 1 ), with 1 ranging from 0.01 to 100 in 100 evenly multiplicatively-spaced increments, while setting 50% of jobs to have each server need. In both cases, we set the 5-server jobs to have duration Exp (1).

We plot the behavior of these two settings in in the case of parameterized 1 (R 2 = 0.526), but no significant correlation in the case of parameterized p 1 (R 2 = 0.005). This indicates that the correlation observed in Section 8 may exist in some settings, but is not robust or reliable. Further investigation will be needed to better understand this correlation.