Nicolas Gast

Approximations to Study the Impact of the Service Discipline in Systems with Redundancy

Keywords: CCS Concepts:, General and reference → Performance, • Mathematics of computing → Queueing theory, • Theory of computation → Scheduling algorithms load balancing, redundancy, scheduling, queueing theory, mean field approximation, pair approximation

As job redundancy has been recognized as an effective means to improve performance of large-scale computer systems, queueing systems with redundancy have been studied by various authors. Existing results include methods to compute the queue length distribution and response time but only when the service discipline is First-Come-First-Served (FCFS). For other service disciplines, such as Processor Sharing (PS), or Last-Come-First-Served (LCFS), only the stability conditions are known.

In this paper we develop the first methods to approximate the queue length distribution in a queueing system with redundancy under various service disciplines. We focus on a system with exponential job sizes, i.i.d. copies, and a large number of servers. We first derive a mean field approximation that is independent of the scheduling policy. In order to study the impact of service discipline, we then derive refinements of this approximation to specific scheduling policies. In the case of Processor Sharing, we provide a pair and a triplet approximation. The pair approximation can be regarded as a refinement of the classic mean field approximation and takes the service discipline into account, while the triplet approximation further refines the pair approximation. We also develop a pair approximation for three other service disciplines: First-Come-First-Served, Limited Processor Sharing and Last-Come-First-Served. We present numerical evidence that shows that all the approximations presented in the paper are highly accurate, but that none of them are asymptotically exact (as the number of servers goes to infinity). This makes these approximations suitable to study the impact of the service discipline on the queue length distribution. Our results show that FCFS yields the shortest queue length, and that the differences are more substantial at higher loads.

INTRODUCTION

Job redundancy has been shown to improve performance in a variety of practical systems [START_REF] Ananthanarayanan | Effective straggler mitigation: Attack of the clones[END_REF][START_REF] Dean | The tail at scale[END_REF][START_REF] Vulimiri | Low latency via redundancy[END_REF]. The main idea is to assign replicas of incoming jobs to multiple servers in the hope that one of the replicas completes quickly in one of the servers. This has lead to the introduction of several queueing models with redundancy. These models can be classified in a number of ways. A first classification can be made based on the assumptions made on the size of the replicas. In some models replicas are assumed to have independent and identically distributed (i.i.d.) job sizes [START_REF] Anton | On the stability of redundancy models[END_REF][START_REF] Bonald | Balanced fair resource sharing in computer clusters[END_REF][START_REF] Gardner | Redundancy-d: The power of d choices for redundancy[END_REF][START_REF] Gardner | Reducing latency via redundant requests: Exact analysis[END_REF], while other models assume that replicas have identical sizes [START_REF] Anton | On the stability of redundancy models[END_REF][START_REF] Hellemans | Analysis of redundancy(d) with identical replicas[END_REF][START_REF] Raaijmakers | Stability of redundancy systems with processor sharing[END_REF]]. An intermediate model is the S&X model [START_REF] Gardner | A better model for job redundancy: Decoupling server slowdown and job size[END_REF], which assumes that the time required to complete a job on a server is a mixture of a fixed job size and an i.i.d. slowdown of the server.

Another classification can be made based on when the replicas are cancelled. A first option is to cancel all replicas as soon as one completes [START_REF] Anton | On the stability of redundancy models[END_REF][START_REF] Bonald | Balanced fair resource sharing in computer clusters[END_REF][START_REF] Gardner | Redundancy-d: The power of d choices for redundancy[END_REF][START_REF] Gardner | Reducing latency via redundant requests: Exact analysis[END_REF][START_REF] Hellemans | Analysis of redundancy(d) with identical replicas[END_REF][START_REF] Raaijmakers | Stability of redundancy systems with processor sharing[END_REF], this model is called the cancelon-complete (CoC) model. For servers using First-Come-First-Served (FCFS) replicas may also be cancelled as soon as one replica starts service [START_REF] Ayesta | On a unifying product form framework for redundancy models[END_REF][START_REF] Hellemans | On the power-of-d-choices with least loaded server selection[END_REF], in which case the model is referred to as the Cancel-on-Start (CoS) model. Other variations such as delayed CoC have also been considered [START_REF] Hellemans | Performance analysis of workload dependent load balancing policies[END_REF]. While the stability condition of the CoS model typically demands that the load is bounded by one, Authors' addresses: Nicolas Gast, nicolas.gast@inria.fr, Univ. Grenoble Alpes, Inria, Grenoble, France; Benny Van Houdt, benny.vanhoudt@uantwerpen.be, Dept. Computer Science, University of Antwerp, Antwerp, Belgium.

determining the stability condition of a CoC model is much more challenging [START_REF] Anton | On the stability of redundancy models[END_REF][START_REF] Gardner | Redundancy-d: The power of d choices for redundancy[END_REF][START_REF] Raaijmakers | Achievable stability in redundancy systems[END_REF][START_REF] Raaijmakers | Stability of redundancy systems with processor sharing[END_REF], see [START_REF] Anton | A survey of stability results for redundancy systems[END_REF] for a recent survey.

Two main approaches have been used to derive performance measures of queueing models with redundancy. When a finite number of servers is considered [START_REF] Bonald | Balanced fair resource sharing in computer clusters[END_REF][START_REF] Gardner | Redundancy-d: The power of d choices for redundancy[END_REF][START_REF] Gardner | Reducing latency via redundant requests: Exact analysis[END_REF], product form solutions for the queue length distribution under FCFS have been obtained in a number of settings as these models can be linked either with the order-independent queues in [START_REF] Krzesinski | Order Independent Queues[END_REF] or with the framework presented in [START_REF] Visschers | A product form solution to a system with multi-type jobs and multi-type servers[END_REF]. Another approach to study queueing models with redundancy exists in developing approximations for systems with a large number of servers (typically a homogeneous system) by using mean field models [START_REF] Gardner | Redundancy-d: The power of d choices for redundancy[END_REF][START_REF] Hellemans | Performance analysis of workload dependent load balancing policies[END_REF][START_REF] Hellemans | On the power-of-d-choices with least loaded server selection[END_REF][START_REF] Hellemans | Analysis of redundancy(d) with identical replicas[END_REF][START_REF] Shneer | Large-scale parallel server system with multi-component jobs[END_REF]. In this case the workload process is studied, which yields approximation results for the FCFS response time distribution in a large system. In some particular cases these approximations are proven to be asymptotically exact [START_REF] Shneer | Large-scale parallel server system with multi-component jobs[END_REF].

Apart from the line of work focusing on the stability of CoC models, surveyed in [START_REF] Anton | A survey of stability results for redundancy systems[END_REF], all prior queueing models with redundancy focused on the performance of FCFS servers. In this paper we are the first to study the impact of the service discipline on the queue length distribution in a queueing system with redundancy. The service disciplines considered are Processor Sharing (PS), FCFS, Last-Come-First-Served (LCFS) and Limited Processor Sharing 𝐾 (LPS(𝐾)), where up to 𝐾 of the oldest jobs are served in parallel. We consider a CoC queueing model 1 with 𝑛 servers, exponential job sizes and i.i.d. replicas where jobs arrive according to a Poisson process with rate 𝜆𝑛 and each new incoming job is assigned to 𝑑 random servers. Throughout the paper we mainly consider the case with 𝑑 = 2, but most of the presented models generalize to the setting with 𝑑 > 2 (see Appendix B). We focus on developing accurate approximations for systems with many servers.

The contributions made in the paper can be summarized as follows. First we introduce a mean field model that is not affected by the service discipline and that can be used to approximate the queue length distribution in a server. This model basically assumes that queues that hold replicas of the same job have independent queue lengths. While this is true when the replicas are placed in the servers, this assumption becomes false afterwards. This is intuitively clear, if a replica of a job has spent a long time period in a long queue, the other replica did not complete service during that period and is therefore more likely to be part of a long queue as well.

Second, we introduce an exact dynamic graph model when the service discipline is PS. However solving this graph model seems to be intractable. We therefore introduce a so-called pair approximation that relies on the assumption that the graph model becomes a local tree when the number of nodes in the graph becomes large and that there exists a conditional independence between the degree of two nodes that are both connected to the same node with a given degree. We show by simulation that this pair approximation is highly accurate for systems with many servers. We provide numerical evidence that shows that the pair approximation is not asymptotically exact as the number of servers goes to infinity.

Our third contribution is the introduction of a further refinement of the pair approximation for PS servers, called the triplet approximation that uses a more involved conditional independence assumption on the degree of the nodes in the graph. Simulation shows that this approximation is even more accurate than the pair approximation. Despite its remarkable accuracy the triplet approximation is also asymptotically inexact and coming up with an approximation that captures the exact limiting behavior for PS servers appears to be hard.

The fourth contribution of the paper exists in applying the idea of the pair approximation for PS servers to other service disciplines. More specifically, we show how to develop pair approximations for systems with FCFS, LCFS and LPS(𝐾) servers. The main distinction between the initial mean field model and these pair approximations is that the pair approximations take some of the correlations between the queue lengths of servers that share a job into account. We also show that if we assume independence between queue lengths of replicas, all the pair approximations collapse to the initial mean field model. As such all our pair approximations can be regarded as refinements of the original mean field model, tailored such that they take the specifics of the queueing discipline into account.

Finally we compare numerically the performance of the different service disciplines. The results show that FCFS performs best in terms of the queue length distribution and thus in terms of the mean response time with gains exceeding 20% compared to LCFS under high loads.

The paper is structured as follows. Section 2 introduces the model and shows that the service discipline matters. Section 3 presents the mean field approximation, which is insensitive to the service discipline. Section 4 contains the pair and triplet approximations for PS servers. Section 5 shows how to derive pair approximations for FCFS, LPS(𝐾) and LCFS. Section 6 presents numerical results on the impact of the service discipline. Section 7 contains conclusion and future work.

MODEL

The redundancy-d model

We consider a system of 𝑛 identical servers where 𝑛 is large. Jobs arrive in the system at rate 𝑛𝜆. When a job arrives, 𝑑 replicas of this jobs are created and sent to 𝑑 servers chosen at random. We consider a cancel-on-complete policy: this means that when a replica of a job is completed, the 𝑑 -1 other replicas are canceled and removed from the other servers. This occurs instantaneously. We refer to these 𝑑 -1 other replicas of a job as its 𝑑 -1 buddies. We assume that the size of all replicas are i.i.d and exponentially distributed with mean 1. While i.i.d. and exponentially distributed job sizes is somewhat restrictive from a practical point of view, we explain in Appendix A that this restricted setting is of particular interest to study Join-Idle-Queue load balancing with redundancy (JIQ-RED), which was recently introduced in [START_REF] Harte | Token redundancy in distributed JIQ[END_REF].

Service discipline matters

It is shown in [START_REF] Anton | On the stability of redundancy models[END_REF] that the stability region of PS and FCFS is identical, that is, both models are stable for 𝜆 < 1 under exponential job sizes when the mean job size equals 1. Further, in [START_REF] Anton | The stationary distribution of the redundancy-d model with random order of service[END_REF] the authors illustrate a coupling approach that suggests that the queue length distribution is also identical for a variety of service disciplines, including PS and FCFS, in a redundancy-𝑑 system. However, we provide numerical evidence in this section that illustrates that the queue length distribution of a server is affected by the service discipline even for a model of exponentially distributed and i.i.d. replicas. We illustrate this in two settings: (i) in a system with 𝑛 = 3 servers, where we present both numerical and simulation results, and (ii) in a system with 𝑛 = 10 5 servers using simulation.

For the 3 server case we numerically compute the steady-state distribution for the redundancy-d model with 𝑑 = 2. For FCFS, an explicit formula can be derived from the product form distribution of [START_REF] Gardner | Redundancy-d: The power of d choices for redundancy[END_REF], and is obtained by using the order-independent-queue framework. For PS, we construct a Markov chain with (𝐾 + 1) 3 states, where 𝐾 is the maximal number of jobs per class. In such a chain, the state is represented as (𝑠 1 , 𝑠 2 , 𝑠 3 ) where 𝑠 𝑖 is the number of jobs for which there is a replica in servers 𝑖 and 𝑖 + 1 (with the convention that 3 + 1 = 1). For each 𝑖, 𝑠 𝑖 becomes 𝑠 𝑖 + 1 at rate 𝜆 (arrival) and 𝑠 𝑖 becomes 𝑠 𝑖 -1 at rate 𝑠 𝑖 /(𝑠 𝑖 + 𝑠 𝑖+1 ) + 𝑠 𝑖 /(𝑠 𝑖 + 𝑠 𝑖 -1 ) because there are 𝑠 𝑖 + 𝑠 𝑖 -1 replicas currently served in server 𝑖 (with the convention 𝑠 0 = 𝑠 3 ). We obtain the steady-state distribution by inverting the matrix. The steady-state distribution of the number of jobs in a server for PS and for FCFS are reported in For the setting with 𝑛 = 10 5 servers we simulated a system with 𝑑 = 2 for FCFS, LPS(𝐾), PS and LCFS,. Table 2 presents simulation results for 𝜆 = 0.9 averaged over four runs of length 10 5 . While we observed in Table 1 that the differences between the different service disciplines are quite small at low loads, the differences are much more pronounced at high load. Our simulation results clearly show differences in queue length distribution that cannot be attributed to simulation noise.

MEAN FIELD APPROXIMATION

In this section, we construct a mean field approximation for the redundancy-d model. This approximation does not depend on the service discipline as long as it is work-conserving. As we will see later, this approximation is not asymptotically exact, and one can derive more accurate approximations by using pair or triplet approximations.

Derivation of the ODE: transient regime

To construct the mean field approximation, let us first compute the rate at which a replica is served. Let 𝑞 𝑡 (𝑥) be the fraction of servers who have 𝑥 replicas at time 𝑡 and pick a replica at random (uniformly among all replicas in the system at time 𝑡). This replica is in a server with 𝑦 replicas with probability 𝑦𝑞 𝑡 (𝑦)/ q𝑡 , where q𝑡 = 𝑦 ≥1 𝑦𝑞 𝑡 (𝑦). This implies that a random replica is served at rate

∑ 𝑦 ≥1 1 𝑦 𝑦𝑞 𝑡 (𝑦) q𝑡 = 1 -𝑞 𝑡 (0) q𝑡
, where in the above equation the factor 1 𝑦 is due to work-conserving nature of the policy: each server serves replicas at rate 1, which means that a randomly chosen replica among these 𝑦 is served at rate 1/𝑦. For instance, using PS all 𝑦 replicas are served at rate 1/𝑦, hence also a random one. Under FCFS or LCFS the random replica is served with probability 1/𝑦 at rate 1, under limited-PS the replicas in the first 𝐾 positions are served at rate 1/𝐾 (if 𝑦 ≥ 𝐾) and the random replica is served at rate 1/𝐾 with probability 𝐾/𝑦.

Let us now focus on a given server that has 𝑥 replicas in its queue. There are three types of events that affect this server:

(1) A replica can be added to its queue, which occurs at rate 𝑑𝜆.

(2) The server might complete the service of one of its replicas, which occurs at rate 1.

(3) One of the replica can be removed from the queue because another replica of the same job, that is, a buddy, has been served by another server. The rate at which this last event occurs is complex and depends on the queue lengths of all servers who hold the buddies of the 𝑥 jobs that our current server has. This is where we need an approximation. The mean field approximation consists in assuming that the queue lengths of the servers holding the different replicas of the same job are independent. This is equivalent to stating that the 𝑑 -1 buddies are random replicas. This means that each of the 𝑑 -1 buddies disappears at rate (1 -𝑞 𝑡 (0))/ q𝑡 . Hence, the total rate at which this event occurs is

(𝑑 -1)𝑥 (1 -𝑞 𝑡 (0))/ q𝑡 .
To summarize, replicas appear at rate 𝑑𝜆 and disappear at rate (1 + (𝑑 -1)𝑥 (1 -𝑞 𝑡 (0))/ q𝑡 ) in a server that has 𝑥 replicas. This leads to a system of differential equations for 𝑞 𝑡 (𝑥): for 𝑥 > 0:

𝑑𝑞 𝑡 (𝑥) 𝑑𝑡 = 𝑑𝜆 [𝑞 𝑡 (𝑥 -1) -𝑞 𝑡 (𝑥)] + 𝑞 𝑡 (𝑥 + 1) -𝑞 𝑡 (𝑥) (1)
+ (1 -𝑞 𝑡 (0)) (𝑑 -1)
q𝑡

[(𝑥 + 1)𝑞 𝑡 (𝑥 + 1) -𝑥𝑞 𝑡 (𝑥))] ,
where

𝑞 𝑡 (0) = 1 -𝑥 ≥1 𝑞 𝑡 (𝑥).
The solution of the ODE ( 1) is what we call the mean field approximation. In this equation, the first line corresponds to the local arrival and service of replicas (type 1 and type 2 events), while second line is caused by the completion of buddies in other servers. We emphasize that this model is just an approximation: as we will see later in Section 6, it is not asymptotically exact as the number of servers grows, contrary to what happens in many systems. This is due to the fact that the queue lengths of servers holding a replica of the same job are not independent (when the number of servers is very large, the 𝑑 queue lengths are independent at the time when the job arrives, but a dependence is created as time progresses). It can be shown that this implies that the model for JIQ-Red(𝑑) in [START_REF] Harte | Token redundancy in distributed JIQ[END_REF] is not asymptotically exact either.

Fixed point analysis

The mean field equation leads to an almost-closed form result for the fixed point. Theorem 1. The set of ODEs given by (1) has a unique fixed point given by

𝑞(𝑥) = 𝑞(𝑥 -1) 𝑑𝜆 1 + 𝜆𝑥 (𝑑 -1) q = (1 -𝜆) (𝑑𝜆) 𝑥 𝑥 ℓ=1 (1 + 𝜆ℓ (𝑑 -1) q ) , ( 2
)
where q is the unique solution on (0, ∞) of the equation

𝜆 1 -𝜆 = ∑ 𝑥 ≥1 (𝑑𝜆) 𝑥 𝑥 ℓ=1 (1 + 𝜆 (𝑑 -1)ℓ q ) = 𝑑 q 𝑑 -1 -q/(𝜆 (𝑑 -1) )
𝑒 𝑑 q/(𝑑 -1) 𝛾 (1 + q/(𝜆(𝑑 -1)), 𝑑 q/(𝑑 -1)), where 𝛾 (𝑠, 𝑥) = ∫ 𝑥 0 𝑡 𝑠 -1 𝑒 -𝑡 𝑑𝑡 is the lower incomplete gamma function and where the right-hand side is increasing in q.

Proof. Assume 𝑞(0) and q are fixed, then the ODE (1) essentially corresponds to a birth-death process. Hence, summing (1) for 𝑥 ≥ 𝑧 implies

∑ 𝑥 ≥𝑧 𝑑𝑞 𝑡 (𝑥) 𝑑𝑡 = -𝑞 𝑡 (𝑧) + 𝑑𝜆𝑞(𝑧 -1) -(𝑑 -1) (1 -𝑞 𝑡 (0)) 𝑧𝑞 𝑡 (𝑧) q𝑡
.

By setting

𝑑𝑞 𝑡 (𝑥 ) 𝑑𝑡 = 0, this implies that a fixed point of (1) must satisfy (for 𝑥 > 0):

𝑞(𝑥) = 𝑞(𝑥 -1) 𝑑𝜆 1 + (1 -𝑞(0)) (𝑑 -1) 𝑥 q .
(3)

To compute 𝑞(0), let us sum 𝑥 𝑑𝑞 𝑡 (𝑥 ) 𝑑𝑡 over 𝑥. This gives:

∑ 𝑥 ≥1 𝑥 𝑑𝑞 𝑡 (𝑥) 𝑑𝑡 = 𝑑𝜆 - ∑ 𝑥 𝑞 𝑡 (𝑥) + 1 -𝑞 𝑡 (0) q𝑡 ∑ 𝑥 𝑥𝑞 𝑡 (𝑥) = 𝜆 -1 + 𝑞 0 (𝑡). (4)
This shows that any fixed point of the ODE (1) satisfies 𝑞(0) = 1 -𝜆 and therefore implies [START_REF] Anton | On the stability of redundancy models[END_REF].

As 𝑥 ≥1 𝑞(𝑥) = 𝜆, q is a solution of

𝜆 1 -𝜆 = ∑ 𝑥 ≥1 (𝑑𝜆) 𝑥 𝑥 ℓ=1 (1 + 𝜆ℓ (𝑑 -1) q ) . (5)
The right-hand side of this equality is clearly increasing in q and equals 0 in 0. We may therefore conclude that q is the unique fixed point of [START_REF] Ayesta | On a unifying product form framework for redundancy models[END_REF]. Remark that

∑ 𝑥 ≥1 𝑎 𝑥 𝑥 ℓ=1 (1 + 𝑏ℓ) = 𝑎 𝑏 -1/𝑏 𝑒 𝑎/𝑏 𝛾 (1 + 𝑎/𝑏, 𝑎/𝑏),
where 𝛾 (𝑠, 𝑥) = ∫ 𝑥 0 𝑡 𝑠 -1 𝑒 -𝑡 𝑑𝑡 is the lower incomplete gamma function. Letting 𝑎 = 𝜆𝑑 and 𝑏 = 𝜆(𝑑 -1)/ q completes the proof. □

RED-PS: DYNAMIC GRAPH MODEL AND PAIR/TRIPLET APPROXIMATIONS

What makes the mean field approximation asymptotically inexact is the dependencies between the servers: if a job has one replica in a server with 𝑥 replicas and its buddy is located in a server with 𝑦 replicas, then this job is more likely to disappear if 𝑦 is small than if 𝑦 is large. This implies that the queue lengths of servers holding replicas of the same job are not independent (notwithstanding the fact that they were independent when the job was just added). In this section, we take this dependence into account for the redundancy system with PS service by looking at the graph of dependence between servers. Other service disciplines are discussed in Section 5. For simplicity and numerical tractability, we restrict our attention to 𝑑 = 2 replicas. In Appendix B we indicate how our models can be generalized to 𝑑 > 2 replicas.

The dynamic graph model

When there are 𝑑 = 2 replicas per job, the RED-PS model can be represented by a dynamic random (multi)graph (𝑉 , 𝐸 𝑡 ). The graph is undirected and the set of vertices 𝑉 is the set of servers. The set of edges 𝐸 𝑡 evolves over time and there is an edge between 𝑢 ∈ 𝑉 and 𝑣 ∈ 𝑉 for each job that is shared by servers 𝑢 and 𝑣 at time 𝑡. The graph (𝑉 , 𝐸 𝑡 ) is in fact a multigraph since there can be multiple edges between two nodes when two servers share more than one job. There can be also loops if two replicas of the same jobs are connected to the same server. An example of such a graph is depicted in Figure 1(a). The multigraph evolves as follows: • For any pair of servers (𝑢, 𝑣), a new edge (𝑢, 𝑣) is added to the graph at rate 2𝜆/𝑛.

2 4 2 2 2 1 0 0 1 1 1 3 1 2 2 1 0 0 1 1 (𝑥, 𝑦) (1,1) (1,2) (1,3) (2,3) (2,2) (2,
• Any vertex has an internal Poisson clock of intensity 1. When this clock ticks, it destroys one of its edges (taken uniformly at random among all its edges). Let us denote by 𝑑 𝑡 (𝑢) the degree of a node 𝑢 at time 𝑡, which is also equal to the number of replicas that this server holds. The above transitions imply that if an edge connects two servers of degree 𝑑 𝑡 (𝑢) and 𝑑 𝑡 (𝑣), then this edge disappears at rate 1/𝑑 𝑡 (𝑢) + 1/𝑑 𝑡 (𝑣).

The multigraph model corresponds exactly to the RED-PS model. In what follows, we will use this graph representation to construct two sets of ODEs that are a very good approximation of the RED-PS model when the number of servers 𝑛 is large. Yet, to simplify the derivation of the equations, we will construct these ODEs by using a slightly simpler model in which we forbid the creation of multi-edges or loops -the rest of the model remains the same. The argument to do so is that, when the number of servers 𝑛 is large, the rate at which loops or multi-edges are created is 𝑂 (1/𝑛), while the rate at which such edges are removed remains 𝑂 (1). Hence, the difference between the two models is likely to be of order 𝑂 (1/𝑛).

The Pair Approximation

To construct our mean field approximation in Section 3, the idea was to focus on servers and study the number of replicas per server. To obtain a more accurate approximation, here we change our point of view and focus on the jobs rather than on servers, and we look at how many replicas do the two servers of a job hold.

Fraction of pairs.

As before, we denote by 𝑑 𝑡 (𝑢) the degree of a node 𝑢 at time 𝑡. It is equal to the number of neighbors in the graph 𝐺 𝑡 , that is, 𝑑 𝑡 (𝑢) = |Γ 𝑡 (𝑢)|, where Γ 𝑡 (𝑢) = {𝑣 | (𝑢, 𝑣) ∈ 𝐸 𝑡 } is the set of neighbors of the node 𝑢. We denote by 𝜋 𝑡 (𝑥, 𝑦) the number of edges that connect a node of degree 𝑥 with a node of degree 𝑦 at time 𝑡 divided by 𝑛 (the number of servers) if 𝑥 = 𝑦, and by 2𝑛 if 𝑥 ≠ 𝑦:

𝜋 𝑡 (𝑥, 𝑦) = 1 2𝑛 ∑ 𝑢 ∈𝑉 ∑ 𝑣 ∈Γ 𝑡 (𝑢 ) 1[𝑑 𝑡 (𝑢) = 𝑥, 𝑑 𝑡 (𝑣) = 𝑦], (6)
where the factor 1/2 is because one can exchange the role of 𝑢 and 𝑣: an edge that connects two nodes with a different degree, say degree 𝑥 and 𝑦, contributes 1/2𝑛 to 𝜋 𝑡 (𝑥, 𝑦) and 1/2𝑛 to 𝜋 𝑡 (𝑦, 𝑥) whereas an edge that connects two nodes of degree 𝑥 simply contributes 1/𝑛 to 𝜋 𝑡 (𝑥, 𝑥). By construction, the quantity 𝜋 𝑡 (𝑥, 𝑦) is symmetric and only makes sense if 𝑥 ≥ 1 and 𝑦 ≥ 1 because if a server is connected to a job, it has at least one replica. For 𝑥 ≥ 1, we denote:

𝜋 𝑡 (𝑥) = ∑ 𝑦 ≥1 𝜋 𝑡 (𝑥, 𝑦) = ∑ 𝑦 ≥1
𝜋 𝑡 (𝑦, 𝑥).

As for the mean field approximation, we denote by 𝑞 𝑡 (𝑥) the fraction of servers holding exactly 𝑥 jobs. The total number of replicas residing in servers with queue length 𝑥 is equal to 2𝑛𝜋 𝑡 (𝑥).

Notice that here we count every edge (𝑥, 𝑦) with 𝑥 ≠ 𝑦 once (as it contributes 1/2𝑛 to 𝜋 𝑡 (𝑥, 𝑦)) and every edge (𝑥, 𝑥) twice as this edge corresponds to two such replicas. Dividing this total number 2𝑛𝜋 𝑡 (𝑥) by 𝑛𝑥 yields 𝑞 𝑡 (𝑥) (for 𝑥 ≥ 1):

𝑞 𝑡 (𝑥) = 2𝜋 𝑡 (𝑥) 𝑥 . ( 8
)
We end by defining the conditional probability that a random job in a queue of length 𝑥 has a buddy in a queue with length 𝑦, which we denote as 𝜋 𝑡 (𝑦|𝑥). As stated above the total number of replicas residing in servers with queue length 𝑥 is equal to 2𝑛𝜋 𝑡 (𝑥), while 2𝑛𝜋 𝑡 (𝑥, 𝑦) is the total number of replicas in a queue with length 𝑥 connected to a queue with length 𝑦. Hence,

𝜋 𝑡 (𝑦|𝑥) = 𝜋 𝑡 (𝑥, 𝑦) 𝜋 𝑡 (𝑥) , (9)
which holds irrespective of whether 𝑥 equals 𝑦.

We illustrate the definition of 𝜋 in Figure 1(c) where we show the values of 𝜋 (𝑥, 𝑦) for the graph of Figure 1(b). One can verify that the degree distribution is

𝑞(1) = 𝜋 (1) = 2(1/20 + 1/10 + 1/10) = 5/10, 𝑞(2) = 2𝜋 (2)/2 = (1/10 + 1/20 + 1/20) = 2/10, 𝑞(3) = 2(1/10 + 1/20)/3 = 1/10 and 𝑞(0) = 1 -𝑞(1) -𝑞(2) -𝑞(3) = 2/10
. For the conditional probabilities, we also have for instance that

𝜋 (2|1) = 𝜋 (1, 2)/(𝜋 (1, 1) + 𝜋 (1, 2) + 𝜋 (1, 3)) = 1/5,
and 𝜋 (1|2) = 1/4. Note that conditional probabilities are (in general) not symmetric.

Rates.

In what follows, we call (𝑥, 𝑦) the type of a job. There are two main types of events that can modify the number of jobs of a given type. First, there can be a completion or a creation of a job: at rate 1/𝑥 + 1/𝑦 a job of type (𝑥, 𝑦) is served, in which case we have one job less of type (𝑥, 𝑦). A new job is created at rate 𝑛𝜆, in which case it connects to two servers at random. These servers have 𝑥 -1 and 𝑦 -1 jobs with probability 2𝑞 𝑡 (𝑥 -1)𝑞 𝑡 (𝑦 -1) if 𝑥 ≠ 𝑦 and 𝑞 𝑡 (𝑥 -1) 2 otherwise. Notice that when 𝑥 ≠ 𝑦 the edge that is created contributes 1/2𝑛 to 𝜋 𝑡 (𝑥, 𝑦) and 1/2𝑛 to 𝜋 𝑡 (𝑦, 𝑥) so the 2 vanishes. Hence, there is a creation of a job of type (𝑥, 𝑦) at rate 𝑛𝜆𝑞 𝑡 (𝑥 -1)𝑞 𝑡 (𝑦 -1).

Second, jobs can also change type. The type can change from (𝑥, 𝑦) to (𝑥 + 1, 𝑦) (or to (𝑥, 𝑦 + 1)) if a replica is added to the first server (or to the second). This occurs at rate 2𝜆. The type can also change from (𝑥, 𝑦) to (𝑥 -1, 𝑦) in two cases:

(1) When any of the other 𝑥 -1 replicas is completed in the first server. This occurs at rate (𝑥 -1)/𝑥. (2) When a job is cancelled because the buddy of one of the 𝑥 -1 replicas in the first server completes. Here, we need to make an approximation. The pair-approximation consists in assuming that if two jobs happen to share a single server 𝑠, the queue lengths of the two other servers (other than 𝑠) that also serve these jobs have independent queue lengths given the length of 𝑠. Mathematically speaking the pair approximation consists in assuming that 𝜋 𝑡 (𝑦 ′ |𝑥) is the probability that the buddy of a job in a server of length 𝑥 has length 𝑦 ′ . This corresponds to assuming that the server length of the buddy of any of these 𝑥 -1 jobs only depends on 𝑥 (and not on 𝑦). As a result, a buddy of the 𝑥 -1 other replicas completes at rate 𝑦 ′ ≥1 𝑞 𝑡 (𝑦 ′ |𝑥) 1 𝑦 ′ , where 1/𝑦 ′ is the completion rate of a replica when there are 𝑦 ′ jobs under PS. Summing both terms, a job transitions from type (𝑥, 𝑦) to (𝑥 -1, 𝑦) at rate 𝑥 -1 𝑥 + ℎ 𝑡 (𝑥), where

ℎ 𝑡 (𝑥) = (𝑥 -1) ∑ 𝑦 ′ ≥1 𝜋 𝑡 (𝑦 ′ |𝑥) 1 𝑦 ′ . (10)
Similarly, a job transitions from (𝑥, 𝑦) to (𝑥, 𝑦 -1) at rate 𝑦-1 𝑦 + ℎ 𝑡 (𝑦). Note that the rate at which the job transitions from (𝑥, 𝑦) to (𝑥 -1, 𝑦) does not depend on 𝑦. This is because we approximate the rate at which buddies are served by [START_REF] Gardner | Reducing latency via redundant requests: Exact analysis[END_REF]. This equation is where we make an approximation, by considering that the queue length of the buddies of the replicas in a server of length 𝑥 only depends on 𝑥, but not on the other buddies. This is called a pair approximation because we limit the graph of dependence to pairs.

4.2.3

The set of ODEs for the pair approximation. Based on the above transitions, we can now write an ODE that indicates how the quantities 𝜋 𝑡 (𝑥, 𝑦) evolve. For 𝑥, 𝑦 ≥ 1, this ODE is:

𝑑𝜋 𝑡 (𝑥, 𝑦) 𝑑𝑡 = 𝜆𝑞 𝑡 (𝑥 -1)𝑞 𝑡 (𝑦 -1) + 2𝜆 [𝜋 𝑡 (𝑥 -1, 𝑦) + 𝜋 𝑡 (𝑥, 𝑦 -1) -2𝜋 𝑡 (𝑥, 𝑦)] + 𝜋 𝑡 (𝑥 + 1, 𝑦) ℎ 𝑡 (𝑥 + 1) + 𝑥 𝑥 + 1 + 𝜋 𝑡 (𝑥, 𝑦 + 1) ℎ 𝑡 (𝑦 + 1) + 𝑦 𝑦 + 1 -𝜋 𝑡 (𝑥, 𝑦) [2 + ℎ 𝑡 (𝑥) + ℎ 𝑡 (𝑦)] , (11)
where 𝑞 𝑡 is defined as in ( 7) and ( 8), and with the convention that 𝜋 𝑡 (0, 𝑦) = 𝜋 𝑡 (𝑥, 0) = 0 for all 𝑥, 𝑦 ≥ 0. Equation ( 11) can be understood as follows. The first term corresponds to the creation of jobs of type (𝑥, 𝑦), and the second term corresponds to job changing types because of arrivals. The second line corresponds to jobs changing from type (𝑥 + 1, 𝑦) or (𝑥, 𝑦 + 1) to type (𝑥, 𝑦). The third line is actually a sum of two transition types: completions of jobs of type (𝑥, 𝑦) (which would be a term 𝜋 𝑡 (𝑥, 𝑦) (1/𝑥 + 1/𝑦)), plus jobs of type (𝑥, 𝑦) transitioning to (𝑥 -1, 𝑦) or (𝑥, 𝑦 -1) (which would be a term 𝜋 𝑡 (𝑥, 𝑦) [(𝑥 -1)/𝑥 + ℎ 𝑡 (𝑥) + (𝑦 -1)/𝑦 + ℎ 𝑡 (𝑦)]). Summing both terms lead to the last line of [START_REF] Harte | Token redundancy in distributed JIQ[END_REF]. In Appendix C, we preset additional results for the pair approximation concerning the properties of the fixed point and the relationship between the pair approximation and the mean field approximation.

Model Validation.

In this section we present some numerical results to illustrate the accuracy of the pair approximation and the original mean field model using simulation. It also includes numbers for the triplet approximation for later reference, which we ignore for now. We simulated systems with 𝑛 = 10 2 , 10 3 , 10 4 and 10 5 servers and loads 𝜆 = 0.5, 0.7 and 0.9. The simulation numbers were averaged over 4 runs of length 10 5 (or more for smaller 𝑛) each. Table 3 presents the results for 𝜆 = 0.9. The numbers for 𝜆 = 0.5 and 0.7 can be found in the Appendices in Tables 8 and9. The first column in each table presents the mean queue length, the second to last column present the probability that the queue length equals 1, 2, 3, 5 and 10, respectively. The fixed point of the set of ODEs characterizing the pair approximation was computed by using a simple Euler iteration starting from an empty system at time 𝑡 = 0.

We first note that the pair approximation is much more accurate than the mean field approximation, with relative errors below 0.1% except for the last probability. We also remark that first the five digits of the simulation numbers are identical for 𝑛 = 10 4 and 𝑛 = 10 5 , meaning that increasing 𝑛 further probably has limited impact. This suggests that convergence has occurred and the pair approximation is asymptotically inexact.

Triplet approximation

In this section we introduce the so-called triplet approximation, which is meant to further improve upon the pair approximation. While the pair approximation was obtained by considering pairs of servers that share jobs, here we go beyond, by consider triplets of servers such that the first two share a job and the last two share another job. This requires more formalism to construct the approximation. As for the pair approximation, we consider the case with two replicas (𝑑 = 2).

Connected triplets.

Recall from ( 6) that 𝜋 𝑡 (𝑥, 𝑦) is the number of pairs of servers with degree 𝑥 and 𝑦 rescaled by the number of servers 𝑛 (or 2𝑛 if 𝑥 ≠ 𝑦). In this part, we now focus on triplets. Consider three nodes 𝑢, 𝑣, 𝑤 ∈ 𝑉 such that (𝑢, 𝑣) ∈ 𝐸 𝑡 , (𝑣, 𝑤) ∈ 𝐸 𝑡 , 𝑑 𝑡 (𝑢) = 𝑥, 𝑑 𝑡 (𝑣) = 𝑦 and 𝑑 𝑡 (𝑤) = 𝑧. We refer to these three nodes as a triplet of type (𝑥, 𝑦, 𝑧) or (𝑧, 𝑦, 𝑥), and we denote by 𝑐 𝑡 (𝑥, 𝑦, 𝑧) the number of triplets of type (𝑥, 𝑦, 𝑧), rescaled by 𝑛 (or 2𝑛 if 𝑥 ≠ 𝑧). For all 𝑥, 𝑦, 𝑧, they can be expressed as:

𝑐 𝑡 (𝑥, 𝑦, 𝑧) = 1 2𝑛 ∑ 𝑣 ∈𝑉 ∑ 𝑢 ∈Γ 𝑡 (𝑣) ∑ 𝑤 ∈Γ 𝑡 (𝑣),𝑤≠𝑢 1[𝑑 𝑡 (𝑢) = 𝑥, 𝑑 𝑡 (𝑣) = 𝑦, 𝑑 𝑡 (𝑤) = 𝑧], (12)
where as before Γ 𝑡 (𝑢) are the neighbors of 𝑢.

The factor 1/2 in the above equation is because the triplet can be read in two directions when 𝑥 ≠ 𝑧 : (𝑥, 𝑦, 𝑧) and (𝑧, 𝑦, 𝑥). We therefore let every such triplet contribute 1/(2𝑛) to 𝑐 𝑡 (𝑥, 𝑦, 𝑧) and 1/(2𝑛) to 𝑐 𝑡 (𝑧, 𝑦, 𝑥) if 𝑥 ≠ 𝑧. When 𝑥 = 𝑧 it simply contributes 1/𝑛 to 𝑐 𝑡 (𝑥, 𝑦, 𝑧). Note that the model is symmetric in the sense that 𝑐 𝑡 (𝑥, 𝑦, 𝑧) = 𝑐 𝑡 (𝑧, 𝑦, 𝑥). By construction, 𝑐 𝑡 (𝑥, 𝑦, 𝑧) is zero if 𝑦 = 1 or if any of 𝑥, 𝑦 or 𝑧 equals 0. For example, if we look at Figure 1

(b) we find that 𝑐 𝑡 (1, 2, 2) = 𝑐 𝑡 (2, 2, 1) = 1/20 and 𝑐 𝑡 (1, 3, 2) = 𝑐 𝑡 (2, 3, 1) = 1/10.
To build our approximation, we will need the degree distribution and the conditional degree of a node given its neighbors. As shown in [START_REF] Gardner | A better model for job redundancy: Decoupling server slowdown and job size[END_REF], the degree can be expressed from 𝜋 𝑡 (𝑥, 𝑦) for 𝑥 ≥ 1. Similarly, when 𝑦 ≥ 2, the quantity 𝜋 𝑡 (𝑥, 𝑦) can be expressed from the quantities 𝑐 𝑡 (𝑥, 𝑦, 𝑧) by noting that each triplet (𝑥, 𝑦, 𝑧) corresponds to 𝑦 -1 pairs (𝑥, 𝑦). By using [START_REF] Gardner | A better model for job redundancy: Decoupling server slowdown and job size[END_REF], we can also recover the degree from 𝑐 𝑡 (𝑥, 𝑦, 𝑧) for all 𝑦 ≥ 2:

𝜋 𝑡 (𝑥, 𝑦) = 1 𝑦 -1 ∑ 𝑧 ≥1 𝑐 𝑡 (𝑥, 𝑦, 𝑧), 𝑞 𝑡 (𝑦) = 2 𝑦 ∑ 𝑥 ≥1 𝜋 𝑡 (𝑥, 𝑦) = 2 𝑦 (𝑦 -1) ∑ 𝑥,𝑧 ≥1 𝑐 𝑡 (𝑥, 𝑦, 𝑧).
This last expression is also immediate because every degree 𝑦 node has 𝑦 (𝑦 -1)/2 triplets with 𝑦 as a middle node.

When 𝑦 = 1, the node 𝑣 cannot be in the middle of a triplet. It can be connected to a node of degree 1 (in which case they form a pair but not a triplet), or it can be connected to a node of degree 𝑥 ≥ 2 which is again connected to a node 𝑧 ≥ 1. When 𝑥 ≥ 2, there are 𝑥 -1 triplets that have the degree one node 𝑣 as an end node. This implies that

𝑞 𝑡 (1) = 2 ∑ 𝑥 ≥1 𝜋 𝑡 (1, 𝑥) = 2𝜋 𝑡 (1, 1) + 2 ∑ 𝑥 ≥2,𝑧 ≥1 𝑐 𝑡 (1, 𝑥, 𝑧) 𝑥 -1 .
We also need the conditional probability, denoted as 𝑐 𝑡 (𝑥 |𝑦) that a random neighbor of a random degree 𝑦 node has degree 𝑥 at time 𝑡 (which was denoted as 𝜋 𝑡 (𝑥 |𝑦) in the pair approximation model). Assume 𝑦 ≥ 2, then we can count the scaled number of triplets with a degree 𝑦 middle node and a degree 𝑥 end node, which equals 2 𝑧 𝑐 𝑡 (𝑥, 𝑦, 𝑧)/(𝑦 -1) as every such triplet is counted 𝑦 -1 times, and divide by the scaled number of neighbors of all degree 𝑦 nodes, given by 𝑦𝑞 𝑡 (𝑦). Therefore, for 𝑦 ≥ 2 and 𝑥 ≥ 1, we have:

𝑐 𝑡 (𝑥 |𝑦) = 2 𝑦 (𝑦 -1)𝑞 𝑡 (𝑦) ∑ 𝑧 ≥1 𝑐 𝑡 (𝑥, 𝑦, 𝑧), ( 13
)
where the 2 is due to the symmetry. Note that the same expression also follows from [START_REF] Gardner | Redundancy-d: The power of d choices for redundancy[END_REF]. For a degree 1 node we can use the same reasoning to find

𝑐 𝑡 (𝑥 |1) = 2 (𝑥 -1)𝑞 𝑡 (1) ∑ 𝑦 ≥1 𝑐 𝑡 (1, 𝑥, 𝑦) for 𝑥 ≥ 2, ( 14
)
𝑐 𝑡 (1|1) = 2𝜋 𝑡 (1, 1) 𝑞 𝑡 (1)
.

It can be verified from the formulas that, by construction, 𝜋 𝑡 (𝑦|𝑥) = 𝑐 𝑡 (𝑦|𝑥).

The last building block that we need to define is the conditional probability that the degree of an end node of a triplet equals 𝑧 given that its other end node has degree 𝑥 and the middle node has degree 𝑦 at time 𝑡, which we denote as 𝑐 𝑡 (𝑧|𝑥, 𝑦). Due to symmetry we have

𝑐 𝑡 (𝑧|𝑥, 𝑦) = 𝑐 𝑡 (𝑥, 𝑦, 𝑧) 𝑧 ′ 𝑐 𝑡 (𝑥, 𝑦, 𝑧 ′ ) . ( 16
)
4.3.2 Rates. We first look at the evolution of 𝜋 𝑡 (1, 1), the number of edges between two degree one nodes divided by 𝑛. Such an edge disappears whenever there is either a service completion or an arrival in either of its nodes. Service completions occur at rate 1 in each server, while arrivals occur at rate 2𝜆 in each node. This results in a total death rate of 2 + 4𝜆. Creation of pairs (1, 1), with an edge between two degree one nodes, can be caused by two types of events:

• First, there could be an arrival where both jobs are assigned to an idle server. This event occurs at rate 𝜆𝑞 𝑡 (0) 2 . • Second, it is also possible that a triplet (𝑢, 𝑣, 𝑤) is such that 𝑑 𝑡 (𝑢) = 1 and 𝑑 𝑡 (𝑣) = 2 and that the edge that connects 𝑣 to its other neighbor, say node 𝑤, disappears due to a service completion. The rate at which this edge (𝑣, 𝑤) disappears due to a service completion depends on 𝑑 (𝑤). If 𝑑 (𝑤) = 𝑥, then this rate equals 1/𝑑 𝑡 (𝑢) + 1/𝑑 𝑡 (𝑤) = 1/2 + 1/𝑥. This yields a total creation rate of pairs (1, 1) equal to

𝜆𝑞 𝑡 (0) 2 + 2 ∑ 𝑥 ≥1 𝑐 𝑡 (1, 2, 𝑥) 1 2 + 1 𝑥 , ( 17
)
where the factor 2 is due to symmetry. We now turn our attention to the evolution of 𝑐 𝑡 (𝑥, 𝑦, 𝑧) over time.

(1*) A new triplet is created if a new arrival links two nodes (one of which has a degree larger than 0). There are two ways to create an (𝑥, 𝑦, 𝑧) triplet: (1) a degree 𝑥 -1 node connects to a degree 𝑦 -1 node that has a degree 𝑧 neighbor, or (2) a degree 𝑧 -1 node connects to a degree 𝑦 -1 node that has a degree 𝑥 neighbor. For case (1) the new arrivals must occur in a degree 𝑥 -1 and 𝑦 -1 node. Moreover we demand that the server selected for the first replica has degree 𝑥 -1 and the server selected for the second replica has degree 𝑦 -1. If the two job replicas are placed in the other order, we state that a type (𝑧, 𝑦, 𝑥) triplet is created. In this manner the symmetry in the system is preserved. As the degree 𝑦 node had 𝑦 -1 neighbors and each of these has degree 𝑧 with probability 𝑐 (𝑧|𝑦 -1) the rate at which a type (𝑥, 𝑦, 𝑧) triplet is created is given by 𝜆𝑞 𝑡 (𝑥 -1)𝑞 𝑡 (𝑦 -1)𝑐 (𝑧|𝑦 -1) (𝑦 -1), in case [START_REF] Ananthanarayanan | Effective straggler mitigation: Attack of the clones[END_REF]. For case [START_REF] Anton | On the stability of redundancy models[END_REF] we state that a type (𝑥, 𝑦, 𝑧) triplet is created when replica one goes to the degree 𝑦 -1 server and the second to the degree 𝑧 -1 server (otherwise we state that it is a type (𝑧, 𝑦, 𝑥) triplet). For this case, the rate a which we create type (𝑥, 𝑦, 𝑧) triplets is therefore given by 𝜆𝑞 𝑡 (𝑦 -1)𝑞 𝑡 (𝑧 -1)𝑐 (𝑥 |𝑦 -1) (𝑦 -1).

Consider now an existing triplet (𝑥, 𝑦, 𝑧). (2*) There could be an arrival in either one of the three nodes (at rate 2𝜆). This simply changes the type to (𝑥 + 1, 𝑦, 𝑧), (𝑥, 𝑦 + 1, 𝑧) or (𝑥, 𝑦, 𝑧 + 1) depending on where the arrival occurs. Arrivals in servers that do not belong to the triplet (𝑥, 𝑦, 𝑧) and that share a job with one of the three servers do not affect a triplet (𝑥, 𝑦, 𝑧).

(3*) There could be a service completion in either of the three servers (at rate 1 in each server). Assume a service completion occurs in the first node (with degree 𝑥), then with probability 1/𝑥 the job that is shared with the middle node completes service and the triplet (𝑥, 𝑦, 𝑧) disappears. Otherwise, with probability (𝑥 -1)/𝑥, the triplet changes from type (𝑥, 𝑦, 𝑧) to (𝑥 -1, 𝑦, 𝑧). The same holds for the other end node. For the middle node there is a probability of 2/𝑦 that a job shared with either one of the endpoints completes, making the triplet (𝑥, 𝑦, 𝑧) disappear. Or with probability (𝑦 -2)/𝑦 the triplet changes into a type (𝑥, 𝑦 -1, 𝑧) triplet.

(4*) Service completions in a server 𝑠 not belonging to the triplet (𝑥, 𝑦, 𝑧) that share a job with one of the nodes part of the triplet do however affect the type of the triplet (𝑥, 𝑦, 𝑧). Let us first consider the case where 𝑠 is a neighbor of an end point of the triplet, say the node with degree 𝑥 (for 𝑧 the argument is similar). In this case the degree 𝑣 of 𝑠 is computed as 𝑐 𝑡 (𝑣 |𝑦, 𝑥). Notice that this degree is only an approximation as we assume that it is independent of the degree of the other endpoint, that is, it is assumed independent of 𝑧. As the degree 𝑥 node had 𝑥 -1 neighboring nodes that are not part of the triplet, the rate of such service completions equals

∑ 𝑣 ≥1 𝑐 𝑡 (𝑣 |𝑦, 𝑥) 𝑥 -1 𝑣 .
In this case the type (𝑥, 𝑦, 𝑧) of the triplet becomes (𝑥 -1, 𝑦, 𝑧). The same happens when a service completion occurs in a neighbor of the endpoint with degree 𝑧 different from 𝑦 and the rate is given by 𝑣 𝑐 𝑡 (𝑣 |𝑦, 𝑧) 𝑧-1 𝑣 , and the type becomes (𝑥, 𝑦, 𝑧 -1). A more difficult case arises when 𝑠 is a neighbor of the middle node with degree 𝑦. In order to determine the probability that 𝑠 has degree 𝑣, we should use the fact that it is connected to the middle node of an (𝑥, 𝑦, 𝑧) triplet. However, in order to define our triplet approximation we only have triplet information. We therefore need to define an approximation. One option would be to neglect one of the endpoints. For instance we could neglect 𝑧 and use 𝑐 (𝑣 |𝑥, 𝑦). Or we could neglect the end node with the smallest or largest degree. After experimenting with different such choices, we decided to determine the degree 𝑣 of 𝑠 as follows. We count all the triplets of the form (𝑥, 𝑦, 𝑣) and (𝑣, 𝑦, 𝑧) and divide by all the triplets that have a degree 𝑥 and 𝑦 nodes as neighbors. In other words, we use 𝑐 𝑡 (𝑣 |𝑥, 𝑦, 𝑧) which we define as

𝑐 (𝑣 |𝑥, 𝑦, 𝑧) = 𝑐 𝑡 (𝑥, 𝑦, 𝑣) + 𝑐 𝑡 (𝑣, 𝑦, 𝑧) 𝑣 ′ (𝑐 𝑡 (𝑥, 𝑦, 𝑣 ′ ) + 𝑐 𝑡 (𝑣 ′ , 𝑦, 𝑧)) . ( 18
)
As the middle node has 𝑦 -2 neighbors not belonging to the triplet, the rate is given by

∑ 𝑣 𝑐 𝑡 (𝑣 |𝑥, 𝑦, 𝑧) 𝑦 -2 𝑣 . 4.3.3
The set of ODEs. For ease of notation let 𝑐 𝑡 (𝑥, 𝑦, 𝑧) = 0 of 𝑥 < 1, 𝑦 < 2 or 𝑧 < 1. Given our discussion of the rates in the previous subsubsection, we have

𝑑 𝑑𝑡 𝜋 𝑡 (1, 1) = 𝜆𝑞 𝑡 (0) 2 -(2 + 4𝜆)𝜋 𝑡 (1, 1) + 2 ∑ 𝑥 𝑐 𝑡 (1, 2, 𝑥) 1 2 + 1 𝑥 , (19)
𝑧 𝑣 + 𝑐 𝑡 (𝑥, 𝑦 + 1, 𝑧) ∑ 𝑣 𝑐 𝑡 (𝑣 |𝑥, 𝑦 + 1, 𝑧) 𝑦 -1 𝑣 (20)
where the first two terms are due to (1*), the next four terms are due to case (2*), the next 4 due to (3*), and the last 4 due to (4*).

We show in Appendix D that one can recover the pair approximation from the triplet approximation, which suggests that the triplet approximation can be regarded as a refinement of the pair approximation that takes more correlations into account.

Model Validation.

In this section we illustrate the accuracy of the triplet approximation. We refer back to Tables 3, 8 and 9 for the fixed point values obtained by the triplet approximation. The results confirm that the triplet approximation can be regarded as a further refinement of the pair approximation (though not every probability is necessarily closer). We also illustrate this improvement using Figure 2 that visualizes that the triplet approximation is asymptotically more accurate than the pair approximation. These results suggest that the pair approximation is asymptotically inexact. Similarly we believe that the triplet approximation is also asymptotically inexact and can probably be further refined, for instance using a quadruplet approximation. Note that the gain in accuracy of the triplet approximation is, however, minor and as such the pair approximation might suffice to gain insights on the impact of the service discipline.

EXTENSION TO OTHER SERVICE DISCIPLINES

We now turn our attention to three other service disciplines: First-Come-First-Served (FCFS), Limited Processor Sharing (LPS) and Last-Come-First-Served (LCFS). In each case, we explain how to construct a pair approximation. The key difference with processor sharing is that one also needs to keep track of the position of the jobs in a queue as the queue length alone does not suffice. These approximations collapse to the same mean field approximation when an independence assumption is made. As before we consider a system with 𝑑 = 2, but these models can be generalized to 𝑑 > 2 in a similar fashion as the generalization for PS servers discussed in Appendix B. 5.1 First-Come-First-Served (FCFS)

𝛿 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 ) = 𝑦 2 ≥𝑦 1 𝛿 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 ), 𝛿 𝑡 (𝑥 1 , 𝑥 2 ) = 𝑦 1 ≥1 𝛿 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 ), 𝛿 (𝑝𝑜𝑠 ) 𝑡 (𝑥 1 ) = 𝑥 2 𝛿 𝑡 (𝑥 1 , 𝑥 2 ) and by 𝛿 (𝑞𝑙 ) 𝑡 (𝑥 2 ) = 𝑥 1 𝛿 𝑡 (𝑥 1 , 𝑥 2 )
. We once more denote by 𝑞 𝑡 (𝑥) the fraction of the servers holding exactly 𝑥 replicas. There are different ways to relate 𝑞 𝑡 and 𝛿 𝑡 . In total, there are 2𝑛𝛿 (𝑝𝑜𝑠 ) 𝑡 (𝑥) replicas that are residing in position 𝑥 of a server. Hence, we have:

𝑞 𝑡 (𝑥) = 2𝛿 (𝑝𝑜𝑠 ) 𝑡 (𝑥) -2𝛿 (𝑝𝑜𝑠 ) 𝑡 (𝑥 + 1), (21)
as a queue has length 𝑥 if there is a replica in position 𝑥, but no replica in position 𝑥 + 1. An alternate, equivalent way to define 𝑞 𝑡 (𝑥) based on 𝛿

(𝑞𝑙 ) 𝑡 (𝑥) is to state that 𝑞 𝑡 (𝑥) = 2𝛿 (𝑞𝑙 ) 𝑡 (𝑥) 𝑥 , (22)
as in the PS pair approximation (see [START_REF] Gardner | A better model for job redundancy: Decoupling server slowdown and job size[END_REF]). Finally note that 𝑞 𝑡 (𝑥) can also be expressed as 2𝛿 𝑡 (1, 𝑥) as there is exactly one replica in position 1 of any queue with length 𝑥.

Rates.

We now look at the evolution of number of jobs of type (𝑥 Jobs can also change type. When using FCFS, a job type can never increase 𝑥 1 or 𝑦 1 because future arrivals join at the back of the queue. Future arrivals do increase 𝑥 2 and 𝑦 2 as follows. As any arrival picks two servers at random, any server is subject to an arrival rate of 2𝜆. This implies that jobs of type (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 ) change into jobs of type (𝑥 1 , 𝑦 1 , 𝑥 2 + 1, 𝑦 2 ) at rate 2𝜆 and similarly into jobs of type (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 + 1) at the same rate of 2𝜆.

The state of a job can also change due to service completions. We distinguish two cases: First, the job at the head of the line can complete service, which occurs at rate 1. In this case both the position and queue length decrease by one. Second, a buddy of another job that shares a queue with our tagged job may complete service in some other server. Here we must further differentiate between two possibilities: it can be the buddy of a job ahead of the tagged job (so the buddy of a job in positions 1 to 𝑥 1 -1 in the first queue or positions 1 to 𝑦 1 -1 in the second queue) or a buddy of a job that is positioned after the tagged job. In the former case again both the position and queue length decrease by one, but in the latter case only the queue length decreases by one.

To compute these rate as a function of 𝛿 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 ), we need an approximation. Here, we need the probability that the buddy of the job in position 𝑥 ′ of the current queue with length 𝑥 2 is in position 1 of its queue. We assume this probability only depends on 𝑥 ′ and 𝑥 2 and is equal to 𝛿 𝑡 (𝑥 ′ , 1, 𝑥 2 ) 𝛿 𝑡 (𝑥 ′ , 𝑥 2 ) and does not depend on 𝑥 1 , 𝑦 1 or 𝑦 2 . In other words we assume this probability only depends on the position and queue length. Summing the two possibilities that decrease both 𝑥 1 and 𝑥 2 implies that the rate of change from

(𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 ) for 𝑥 1 > 1 to ((𝑥 1 -1, 𝑦 1 , 𝑥 2 -1, 𝑦 2 ) is equal to 1 + 𝑥 1 -1 ∑ 𝑥 ′ =1 𝛿 𝑡 (𝑥 ′ , 1, 𝑥 2 ) 𝛿 𝑡 (𝑥 ′ , 𝑥 2 )
, for all 𝑥 1 ≥ 2, while the case that only decreases 𝑥 2 by one has rate

𝑥 2 ∑ 𝑥 ′ =𝑥 1 +1 𝛿 𝑡 (𝑥 ′ , 1, 𝑥 2 ) 𝛿 𝑡 (𝑥 ′ , 𝑥 2 ) , For further use let 𝜅 𝑡 (𝑥 𝑎 , 𝑥 𝑏 ) = 𝑥 𝑎 𝑥 ′ =1 𝛿 𝑡 (𝑥 ′ ,1,𝑥 𝑏 )
𝛿 (𝑥 ′ ,𝑥 𝑏 ) . The above two rates can be denoted as 1 + 𝜅 𝑡 (𝑥 1 -1, 𝑥 2 ) and 𝜅 𝑡 (𝑥 2 , 𝑥 2 ) -𝜅 𝑡 (𝑥 1 , 𝑥 2 ). The situation is symmetric for 𝑦.

5.1.3

The set of ODEs. The above rates lead to the following set of ODEs for 𝛿 𝑡 (𝑥, 𝑦), where 𝛿 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 ) = 0 if one of its entries equals zero or 𝑥 1 > 𝑥 2 or 𝑦 1 > 𝑦 2 :

𝑑 𝑑𝑡

𝛿 𝑡 (𝑥 1 , 𝑦 1 ,𝑥 2 , 𝑦 2 ) = 𝜆𝑞 𝑡 (𝑥 2 -1)𝑞 𝑡 (𝑦 2 -1)1[𝑥 1 = 𝑥 2 , 𝑦 1 = 𝑦 2 ] -4𝜆𝛿 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 ) + 2𝜆𝛿 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 -1, 𝑦 2 ) + 2𝜆𝛿 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 -1) -𝛿 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 ) 2 + 𝜅 𝑡 (𝑥 2 , 𝑥 2 ) - 𝛿 𝑡 (𝑥 1 , 1, 𝑥 2 ) 𝛿 𝑡 (𝑥 1 , 𝑥 2 ) + 𝜅 𝑡 (𝑦 2 , 𝑦 2 ) - 𝛿 𝑡 (𝑦 1 , 1, 𝑦 2 ) 𝛿 𝑡 (𝑦 1 , 𝑦 2 ) + 𝛿 𝑡 (𝑥 1 + 1, 𝑦 1 , 𝑥 2 + 1, 𝑦 2 ) [1 + 𝜅 𝑡 (𝑥 1 , 𝑥 2 + 1)] + 𝛿 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 + 1, 𝑦 2 ) [𝜅 𝑡 (𝑥 2 + 1, 𝑥 2 + 1) -𝜅 𝑡 (𝑥 1 , 𝑥 2 + 1)] + 𝛿 𝑡 (𝑥 1 , 𝑦 1 + 1, 𝑥 2 , 𝑦 2 + 1) [1 + 𝜅 𝑡 (𝑦 1 , 𝑦 2 + 1)] + 𝛿 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 + 1) [𝜅 𝑡 (𝑦 2 + 1, 𝑦 2 + 1) -𝜅 𝑡 (𝑦 1 , 𝑦 2 + 1)] . (23)
5.1.4 Model Validation. Tables 4, 10 and 11 correspond to Tables 3, 8 and 9, except that the PS service discipline has been replaced by FCFS servers. An additional line has also been inserted that correspond to 𝐸 [𝑇 ] = (ln(1/(1 -𝜆)) -𝜆)/𝜆 2 which is an approximation of the mean queue length for Redundancy-2 with FCFS servers presented in [START_REF] Gardner | Redundancy-d: The power of d choices for redundancy[END_REF] and shown to be asymptotically exact in [START_REF] Shneer | Large-scale parallel server system with multi-component jobs[END_REF]. These tables demonstrate that the pair approximation for FCFS servers drastically reduces the error of the mean field approximation and yields errors below 0.1%, except for the last probability. They do not provide the value for 𝐸 [𝑇 ] as [START_REF] Gardner | Redundancy-d: The power of d choices for redundancy[END_REF] and therefore are not asymptotically exact. The advantage of our method compared to [START_REF] Gardner | Redundancy-d: The power of d choices for redundancy[END_REF] is to provide an approximation of the full queue length distribution.

Limited Processor Sharing (LPS)

In this subsection we generalize the FCFS model to a model for limited processor sharing LPS(𝐾) where 𝐾 is the maximum number of jobs that are served in parallel by a single server. LPS(K) works as follows: When there are 𝐾 or more 𝐾 jobs in the queue, the oldest 𝐾 are served in parallel (in a PS fashion), otherwise they are all served in parallel (as for PS). The model reduces to the FCFS model of Section 5.1 when 𝐾 = 1, and to the pair approximation for PS of Section 4.2 when 𝐾 = ∞.

5.2.1

Types of jobs and rates. The type of a job is represented as (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 ), where 𝑥 2 and 𝑦 2 are the queue lengths of the servers holding the two replicas for the job as in the FCFS model. However, 𝑥 1 now equals 1 if the first replica is being served (meaning it is in one of the first 𝐾 positions), while 𝑥 1 > 1 if the replica is in position 𝐾 + 𝑥 1 -1, which means it is not in service. The same holds for 𝑦 1 and replica 2. Remark that when 𝑥 1 > 1 (or 𝑦 2 > 1), then 𝑥 2 > 𝐾 (or 𝑦 2 > 𝐾). If we set 𝐾 = ∞ then both 𝑥 1 and 𝑦 1 always equal one and the type of a job is simply characterized by the queue lengths (𝑥 2 , 𝑦 2 ) as for the PS pair approximation.

Let 𝜇 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 ) be the number of type (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 ) jobs scaled by the number of servers at time 𝑡. Define 𝜇 𝑡 (𝑥 1 , 𝑥 2 ) = 𝑦 1 ,𝑦 2 𝜇 𝑡 (𝑥 1 , 𝑦 1 , 𝑥, 𝑦 2 ) and 𝜇 𝑡 (𝑥) = 𝑥 1 𝜇 𝑡 (𝑥 1 , 𝑥). The queue length distribution can be expressed in terms of the 𝜇 𝑡 (𝑥)

𝑞 𝑡 (𝑥) = 2𝜇 𝑡 (𝑥) 𝑥 , (24)
using the same reasoning as in ( 8) and [START_REF] Van Houdt | On the performance evaluation of distributed join-idle-queue load balancing[END_REF]. New arrivals increase the 𝑥 2 or 𝑦 2 value of a job by one, where each server is subject to new arrivals at rate 2𝜆. A new job is also created when an arrival occurs. The difference with the FCFS model is that the 𝑥 1 and 𝑦 1 values do not match 𝑥 2 and 𝑦 2 , respectively, when a new job is created. Let [𝑥] + = max(0, 𝑥), then 𝑥 1 equals 1 + [𝑥 2 -𝐾] + if a new job joins a queue with length 𝑥 2 (such that 𝑥 1 equals 1 if 𝑥 2 ≤ 𝐾). Similarly 𝑦 1 equals 1 + [𝑦 2 -𝐾] + . This yields the first two lines in (28).

Service completions occur in both servers at rate 1. Assume the service completion occurs in the server holding the first replica. If 𝑥 1 = 1 the tagged job completes service with probability 𝑝 𝐾 1 (𝑥 2 ) = min((𝑥 2 -1)/𝑥 2 , (𝐾 -1)/𝐾), otherwise the tagged job only changes type (that is, 𝑥 1 and 𝑥 2 decrease by one). This explains lines 3 and 4 in (28).

Job types can also change due to a service completion of a buddy of a job that shares a server with the tagged job. To determine the rate at which these service completions occur we need to introduce an approximation. We focus on the change in 𝑥 1 and 𝑥 2 as the same holds for 𝑦 1 and 𝑦 2 due to the symmetry of the model. Consider the buddy of the job that is not our tagged job. Let 𝑥 ′ = 1 if this job is in one of the first 𝐾 positions and let 𝑥 ′ > 1 if this job is in position 𝐾 + 𝑥 ′ -1. The approximation exists in assuming that the probability that this buddy is in service in a server with length 𝑦 ′ is given by 𝜇 𝑡 (𝑥 ′ , 1, 𝑥 2 , 𝑦 ′ )/𝜇 𝑡 (𝑥 ′ , 𝑥 2 ). In other words, the probability that the buddy of the job is in service in a queue of length 𝑦 ′ depends only on 𝑥 2 and the value of 𝑥 ′ (which is fully determined by its position). If a buddy is in one of the first 𝐾 positions of a server with queue length 𝑦 ′ , then it is served at rate 1/min(𝐾, 𝑦 ′ ). Hence the completion rate of the buddy of 𝑥 ′ is

𝑟 𝐾 𝑡 (𝑥 ′ , 𝑥 2 ) = ∑ 𝑦 ′ 𝜇 𝑡 (𝑥 ′ , 1, 𝑥 2 , 𝑦 ′ ) 𝜇 𝑡 (𝑥 ′ , 𝑥 2 ) min(𝐾, 𝑦 ′ ) . ( 25
)
When 𝑥 2 ≤ 𝐾 the total rate at which buddies of jobs other that the tagged job complete service is thus min(𝐾 -1, 𝑥 2 -1)𝑟 𝐾 𝑡 (1, 𝑥 2 ). When 𝑥 2 exceeds 𝐾, we find that this rate is given by

𝐾𝑟 𝐾 𝑡 (1, 𝑥 2 ) + 𝑥 2 -𝐾+1 ∑ 𝑥 ′ =2 𝑟 𝐾 𝑡 (𝑥 ′ , 𝑥 2 ) -𝑟 𝐾 𝑡 (𝑥 1 , 𝑥 2 ),
where the tagged job is of type (𝑥

𝜓 𝐾 𝑡 (1, 𝑥 𝑏 ) = min(𝐾, 𝑥 𝑏 )𝑟 𝐾 𝑡 (1, 𝑥 𝑏 ) ( 26
)
𝜓 𝐾 𝑡 (𝑥 𝑎 , 𝑥 𝑏 ) = 𝐾𝑟 𝐾 𝑡 (1, 𝑥 𝑏 ) + 𝑥 𝑎 ∑ 𝑥 ′ =2 𝑟 𝐾 𝑡 (𝑥 ′ , 𝑥 𝑏 ). ( 27
)
Using this notation, the total rate at which buddies of the jobs other than the tagged job complete service can be stated as

𝜓 𝐾 𝑡 (1, 𝑥 2 ) -𝑟 𝐾 𝑡 (1, 𝑥 2 ) when 𝑥 2 ≤ 𝐾 and 𝜓 𝐾 𝑡 (𝑥 2 -𝐾 + 1, 𝑥 2 ) -𝑟 𝑡 (𝑥 1 , 𝑥 2 )
otherwise. This explains line 5 in (28).

When such a buddy completes service, 𝑥 2 always decreases by one. However the value of 𝑥 1 only decreases by one if the value of 𝑥 ′ is strictly less than 𝑥 1 (which can only occur when the tagged job is not in service). In other words, the total rate at which 𝑥 2 and 𝑥 1 both decrease by one is given by 𝜓 𝐾 𝑡 (𝑥 1 -1, 𝑥 2 ), yielding line 6 in (28). Finally, when 𝑥 1 = 1 or 𝑥 ′ > 𝑥 1 only 𝑥 2 decreases by one. For 𝑥 1 = 1 the total rate at which 𝑥 2 decreases by one due to a service completion of a buddy can be written as

𝜓 𝐾 𝑡 (1 + [𝑥 2 -𝐾] + , 𝑥 2 ) -𝑟 𝐾 𝑡 (1, 𝑥 2 ).
For 𝑥 1 > 1 only the buddies of the job after position 𝐾 + 𝑥 1 -1 decrease 𝑥 2 by one without decreasing 𝑥 1 , meaning we have a total rate given by 𝜓 𝐾 𝑡 (𝑥 2 -𝐾 + 1, 𝑥 2 ) -𝜓 𝐾 𝑡 (𝑥 1 , 𝑥 2 ). This yields the last four lines in (28).

5.2.2

The set of ODEs. The above rates lead to the following set of ODEs for 𝜇 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 ), where

𝜇 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 ) = 0 if one of its entries equals zero or 𝑥 1 > 𝑥 2 -𝐾 + 1 or 𝑦 1 > 𝑦 2 -𝐾 + 1: 𝑑 𝑑𝑡 𝜇 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 ) = 𝜆𝑞 𝑡 (𝑥 2 -1)𝑞 𝑡 (𝑦 2 -1)1[𝑥 1 = 1 + [𝑥 2 -𝐾] + , 𝑦 1 = 1 + [𝑦 2 -𝐾] + ] -4𝜆𝜇 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 ) + 2𝜆𝜇 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 -1, 𝑦 2 ) + 2𝜆𝜇 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 -1) -2𝜇 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 ) + 𝜇 𝑡 (𝑥 1 + 1, 𝑦 1 , 𝑥 2 + 1, 𝑦 2 ) + 𝜇 𝑡 (𝑥 1 , 𝑦 1 + 1, 𝑥 2 , 𝑦 2 + 1) + 1[𝑥 1 = 1]𝜇 𝑡 (1, 𝑦 1 , 𝑥 2 + 1, 𝑦 2 )𝑝 𝐾 1 (𝑥 2 + 1) + 1[𝑦 1 = 1]𝜇 𝑡 (𝑥 1 , 1, 𝑥 2 , 𝑦 2 + 1)𝑝 𝐾 1 (𝑦 2 + 1) -𝜇 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 ) 𝜓 𝐾 𝑡 (1 + [𝑥 2 -𝐾] + , 𝑥 2 ) -𝑟 𝐾 𝑡 (𝑥 1 , 𝑥 2 ) + 𝜓 𝐾 𝑡 (1 + [𝑦 2 -𝐾] + , 𝑦 2 ) -𝑟 𝐾 𝑡 (𝑦 1 , 𝑦 2 ) + 𝜇 𝑡 (𝑥 1 + 1, 𝑦 1 , 𝑥 2 + 1, 𝑦 2 )𝜓 𝐾 𝑡 (𝑥 1 , 𝑥 2 + 1) + +𝜇 𝑡 (𝑥 1 , 𝑦 1 + 1, 𝑥 2 , 𝑦 2 + 1)𝜓 𝐾 𝑡 (𝑦 1 , 𝑦 2 + 1) + 1[𝑥 1 = 1]𝜇 𝑡 (1, 𝑦 1 , 𝑥 2 + 1, 𝑦 2 ) (𝜓 𝐾 𝑡 (1 + [𝑥 2 -𝐾 + 1] + , 𝑥 2 + 1) -𝑟 𝐾 𝑡 (1, 𝑥 2 + 1)) + 1[𝑦 1 = 1]𝜇 𝑡 (𝑥 1 , 1, 𝑥 2 , 𝑦 2 + 1) (𝜓 𝐾 𝑡 (1 + [𝑦 2 -𝐾 + 1] + , 𝑦 2 + 1) -𝑟 𝐾 𝑡 (1, 𝑦 2 + 1)) + 1[𝑥 1 > 1]𝜇 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 + 1, 𝑦 2 ) 𝜓 𝐾 𝑡 (𝑥 2 -𝐾 + 2, 𝑥 2 + 1) -𝜓 𝐾 𝑡 (𝑥 1 , 𝑥 2 + 1) + 1[𝑥 1 > 1]𝜇 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 + 1) 𝜓 𝐾 𝑡 (𝑦 2 -𝐾 + 2, 𝑦 2 + 1) -𝜓 𝐾 𝑡 (𝑦 1 , 𝑦 2 + 1) . ( 28
)
As with the FCFS pair approximation (see Appendix E) it is possible to show that 𝑞(0) equals 1 -𝜆 in any fixed point and that this ODE collapses to (1) when using an independence assumption. Table 5. Accuracy of Mean Field and Pair Approximation for LPS(2) servers, arrival rate 𝜆 = 0.9.

Model Validation.

Tables 5, 14 and 15 correspond to Tables 3, 8 and9, where the PS servers are replaced by LPS(K) servers with 𝐾 = 2. These tables demonstrate that the pair approximation also works nicely for LPS(2) servers. We obtained similar results for larger 𝐾 values, that is, for 𝐾 = 3, 5 and 10 (not shown in the paper). These additional experiments confirm that as 𝐾 increases the queue length distribution of the pair approximation for LPS(𝐾) converges towards the distribution of the PS pair approximation.

Last-Come-First-Served (LCFS)

The last service discipline that we consider is last-come-first-served (LCFS).

5.3.1

Types of jobs and rates. The analysis for LCFS proceeds similarly to the one of FCFS,.

We now use the value 𝛾 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 ) that is equivalent to the value 𝛿 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 ) for FCFS except that position 1 now corresponds to the back of the queue. As for FCFS, we denote by

𝛾 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 ) = 𝑦 2 ≥𝑦 1 𝛾 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 ), 𝛾 𝑡 (𝑥 1 , 𝑥 2 ) = 𝑦 1 ≥1 𝛾 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 ), 𝛾 (𝑝𝑜𝑠 ) 𝑡 (𝑥 1 ) = 𝑥 2 𝛾 𝑡 (𝑥 1 , 𝑥 2 )
and by 𝛾 At rate 1 a job of type (1, 𝑦 1 , 𝑥 2 , 𝑦 2 ) or (𝑥 1 , 1, 𝑥 2 , 𝑦 2 ) is served, hence we have a death rate equal to 1 for these job types. The creation of jobs is different now, as when a job is created, this creates a new type (1, 1, 𝑥 2 , 𝑦 2 ) job at rate 𝜆𝑞 𝑡 (𝑥 2 -1)𝑞 𝑡 (𝑦 2 -1).

Jobs can also change type. Contrary to FCFS, a job type increases in all its entries when there is an arrival: a type (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 ) job becomes a type

(𝑥 1 + 1, 𝑦 1 , 𝑥 2 + 1, 𝑦 2 ) or (𝑥 1 , 𝑦 1 + 1, 𝑥 2 , 𝑦 2 + 1)
whenever an arrival occurs that places a replica at one of the servers of the tagged job. Each such event occurs at rate 2𝜆. The changes due to a service completion in one of the two servers of the tagged job are the same as in the FCFS case. The same holds for job type changes that occur when a buddy of another job present in the servers of the tagged job completes service.

5.3.2

The set of ODEs. Given the above discussion on the rates, we find that the set of ODEs given by ( 23) can be adapted to the following set of ODEs for where 𝜙 𝑡 (𝑥 𝑎 , 𝑥 𝑏 ) = 𝑥 𝑎 𝑥 ′ =1 𝛾 𝑡 (𝑥 ′ , 1, 𝑥 𝑏 )/𝛾 𝑡 (𝑥 ′ , 𝑥 𝑏 ) has the same form as 𝜅 𝑡 (𝑥 𝑎 , 𝑥 𝑏 ) for FCFS. By summing this over 𝑦 1 , 𝑦 2 , 𝑥 1 and 𝑥 2 we obtain the same ODE

𝛾 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 ): 𝑑 𝑑𝑡 𝛾 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 ) = 𝜆𝑞 𝑡 (𝑥 2 -1)𝑞 𝑡 (𝑦 2 -1)1[𝑥 1 = 1, 𝑦 1 = 1] -4𝜆𝛾 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 ) + 2𝛾 𝑡 (𝑥 1 -1, 𝑦 1 , 𝑥 2 -1, 𝑦 2 ) + 2𝜆𝛾 𝑡 (𝑥 1 , 𝑦 1 -1, 𝑥 2 , 𝑦 2 -1) -𝛾 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 ) 2 + 𝜙 𝑡 (𝑥 2 , 𝑥 2 ) - 𝛾 𝑡 (𝑥 1 , 1, 𝑥 2 ) 𝛾 𝑡 (𝑥 1 , 𝑥 2 ) + 𝜙 𝑡 (𝑦 2 , 𝑦 2 ) - 𝛾 𝑡 (𝑦 1 , 1, 𝑦 2 ) 𝛾 𝑡 (𝑦 1 , 𝑦 2 ) + 𝛾 𝑡 (𝑥 1 + 1, 𝑦 1 , 𝑥 2 + 1, 𝑦 2 ) [1 + 𝜙 𝑡 (𝑥 1 , 𝑥 2 + 1)] + 𝛾 𝑡 (𝑥 1 , 𝑦 1 + 1, 𝑥 2 , 𝑦 2 + 1) [1 + 𝜙 𝑡 (𝑦 1 , 𝑦 2 + 1)] + 𝛾 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 + 1, 𝑦 2 ) [𝜙 𝑡 (𝑥 2 + 1, 𝑥 2 + 1) -𝜙 𝑡 (𝑥 1 , 𝑥 2 + 1)] + 𝛾 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 + 1) [𝜙 𝑡 (𝑦 2 + 1, 𝑦 2 + 1) -𝜙 𝑡 (𝑦 1 , 𝑦 2 + 1)] , (29)
𝑑𝑞 𝑡 𝑑𝑡 = 2𝜆 -2(1 -𝑞 0 (𝑡))
for the mean queue length as in the FCFS model, while (1) can be recovered from (29) if we make a similar independence assumption

𝛾 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 ) ≈ 2𝛾 𝑡 (𝑥 ,𝑥 2 )𝛾 𝑡 (𝑦 1 ,𝑦 2 ) q𝑡
, as in the FCFS case.

Model Validation.

The pair approximation for LCFS servers is validated using Tables 6, 12 and 13. While the pair approximation clearly improves upon the mean field approximation, the accuracy in case of LCFS servers is lower than in the setting with PS, FCFS or LPS(𝐾) servers. This is somewhat expected as the correlation between the positions of two replicas of the same job is strong in case of a LCFS server as both replicas start in position one. This is in contrast to FCFS servers, where the positions are initially uncorrelated, or to PS servers, where the positions are irrelevant.

INFLUENCE OF THE SERVICE DISCIPLINES

In this section, we provide numerical results to compare the performance of the various scheduling disciplines. Unless specified otherwise, all reported numbers are obtained by computing the fixed points of the pair-approximations provided in Sections 4 and 5. These fixed points are computed by numerically integrating the corresponding systems of ODEs.

Influence on the queue length distribution

The previous sections show that our approximations provide accurate estimates of the queue length distributions and show that the service discipline has a true impact on the average queue length of the system. To push further the comparison between the various service disciplines, we show in Figure 3 the queue length distribution for the various service disciplines. These results show that when the load is not too high (𝜆 = 0.7), all policies behave similarly. This is because when 𝜆 is small, many jobs have at least one of their replicas that is alone in a server where the service discipline has no impact. As 𝜆 goes to 1, most servers have a large queue length, and the service discipline has a high impact. This figure shows that the queue length distribution is minimal for FCFS, and maximal for LCFS, with PS and LPS(2) being in the middle.

Impact on the average queue length

To study further this dependence on 𝜆, we plot in Figure 4, the average queue length as a function of 𝜆. In Figure 4(a), we compare the three policies PS, LCFS and FCFS. This figure confirms what is observed on Figure 3: FCFS always provides the smallest queue length and the difference is larger for larger loads. This panel does not show the numbers for LPS to improve readability. In Figure 4(b), we quantify this difference by showing the ratio between the average queue length of each of the four policies (PS, LPS(2), LPS(5) and LCFS) and the one of FCFS. All numbers are higher than 1 because FCFS has the smallest average queue length. As expected, LPS(2) has a behavior almost identical to FCFS (less than 5% of difference in terms of average queue length, even for 𝜆 = 0.95) whereas LCFS can lead to a queue length up to 25% higher when 𝜆 = 0.95.

To illustrate the accuracy of our approximations:

• In Figure 4(a), we also add simulation results for 𝜆 ∈ {0.3, 0.5, 0.7, 0.9} and 𝑛 = 10 6 servers, as well as the approximation of the average queue length provided in [START_REF] Gardner | Redundancy-d: The power of d choices for redundancy[END_REF]. These numbers are -qualitatively and quantitatively -close to our pair approximation. • In Figure 4(b), the value for FCFS that we use as a denominator is our pair-approximation for FCFS. We also report a curve that is the ratio of the approximation for FCFS provided in [START_REF] Gardner | Redundancy-d: The power of d choices for redundancy[END_REF] (that is asymptotically exact) to our pair-approximation. It shows that the difference between the two approximations is smaller than 1% for 𝜆 ≤ 0.95.

Note that the approximation provided in [START_REF] Gardner | Redundancy-d: The power of d choices for redundancy[END_REF] is only for the average queue length, and only for FCFS. This explains why we cannot make a similar comparison when looking at queue length distribution or at other service disciplines.

Correlations between the buddies of a job

If the pair approximation provides accurate estimates of the queue length distribution, it can also be used to study the correlations between the two buddies of a jobs. This would not be possible by using a mean field approximation that precisely acts as if replicas were independent. In Figure 5, we study the correlations between the two buddies of a job for the three scheduling policies PS, FCFS and LCFS. For each policy, we plot the rate at which the buddy replica disappears as a function of the state of the first replica: For PS, the 𝑥-axis corresponds to the queue length of the first replica and the curve corresponds to 𝑥 ↦ → ℎ(𝑥). For FCFS or LCFS, it corresponds either to the position 𝑥 1 or to the queue length 𝑥 2 , i.e., (Dashed) green curve:

𝑥 1 ↦ → 𝑥 2 ,𝑦 2 𝛿 (𝑥 1 , 1, 𝑥 2 , 𝑦 2 ) 𝑥,𝑥 2 ,𝑦 2 𝛿 (𝑥 1 , 𝑥, 𝑥 2 , 𝑦 2 ) ; Orange curve: 𝑥 2 ↦ → 𝑥 1 ,𝑦 2 𝛿 (𝑥 1 , 1, 𝑥 2 , 𝑦 2 ) 𝑥,𝑥 1 ,𝑦 2 𝛿 (𝑥 1 , 𝑥, 𝑥 2 , 𝑦 2 )
.

(or the same quantity with 𝛾 for LCFS).

We observe that for PS, the influence of the queue length is relatively limited (rates vary from 2.55 to 2.85), which explains why the performance of PS is close to the one of the independent model. FCFS is the only policy for which the rate at which the buddy disappears increases with the queue length of the first buddy. This could explain why FCFS helps reducing the queue length.

CONCLUSIONS AND FUTURE WORK

In this paper we presented the first approximation methods to study the impact of the service discipline on the queue length distribution in large queueing systems with redundancy. Although our models were shown to be highly accurate, they are not asymptotically exact. This work triggers two important lines of future work. First, from an application point of view, the next step is to use these models to study the impact of the token selection mechanism in Join-Idle-Queue load balancing with redundancy. From a more theoretical point of view, the dynamic random graph model introduced in Section 4 can be viewed as a dynamic version of the classical Erdös-Renyi graph where we add arrivals and departures. Our work provides some insight on how to study the structural properties of this graph for large 𝑛. list. Notice that several policies can be used to pick the server id from the list. As will become clear further on, this policy will correspond to the service discipline in our redundancy queue, for instance, we get a PS server if the id is selected at random. Servers that become idle when the traditional JIQ is used, select a single dispatcher at random and their id is added to the list of the selected dispatcher.

Clearly, under high loads there are very few idle servers and many dispatchers may have an idle list. When a new job arrives at a dispatcher with an idle list, the dispatcher assigns the job at random. In such case there are two flavors of JIQ: with and without withdrawals [START_REF] Van Houdt | On the performance evaluation of distributed join-idle-queue load balancing[END_REF][START_REF] Wang | Distributed join-the-idle-queue for low latency cloud services[END_REF]. Without withdrawals an idle server will not remove its id from the list of a dispatcher when it receives a job from another dispatcher. In this case it is shown in [START_REF] Mitzenmacher | Analyzing distributed join-idle-queue: A fluid limit approach[END_REF] that the policy used by the dispatcher to select a server id from its list impacts performance. When withdrawals are used, servers remove their id from the list when receiving a job form another dispatcher. This means that any server id that is on the list of a server necessarily corresponds to an idle server. In this case the policy used by the dispatcher to select a server id from its list has no impact on the performance [START_REF] Van Houdt | On the performance evaluation of distributed join-idle-queue load balancing[END_REF].

When the load is high a possible approach to improve the performance of JIQ is to use a threshold such that when a server has a queue length below the threshold, it adds its server id to the list of a randomly selected dispatcher [START_REF] Mitzenmacher | Analyzing distributed join-idle-queue: A fluid limit approach[END_REF]. Another possibility [START_REF] Harte | Token redundancy in distributed JIQ[END_REF] is that a server places its id at multiple, say 𝑑, randomly selected dispatchers when becoming idle. As soon as a server receives a job from any of these 𝑑 servers, it removes its id from all of the other 𝑑 -1 servers. This policy is called JIQ with redundancy, abbreviated as JIQ-Red(𝑑). It turns out that under JIQ-Red(𝑑) the order in which the server selects a server id from its list again impacts performance. It is however intuitively not clear which policy works best: random selection, FCFS, LCFS, etc?

To see how this JIQ-Red(𝑑) problem is related to the model considered in this paper, think of the dispatcher as the queues, and the lists of server ids as the jobs in the queue. Arrivals correspond to servers becoming idle. In such an event the server places its id at 𝑑 dispatchers. This corresponds to the redundancy 𝑑 aspect of the queueing system. The job arrivals at the dispatchers correspond to service completions, the manner in which the server id is selected to the service discipline and the removal by the server of its id from the 𝑑 -1 other servers corresponds to the cancellation-oncompletion. As incoming jobs in the JIQ-Red(𝑑) are assumed to correspond to a Poisson process, the corresponding service times are indeed exponential and different replicas have independent sizes as each dispatcher is subject to its own independent Poisson process.

There is however one difference between our queueing model and the JIQ-Red(𝑑) system. Under JIQ-Red(𝑑) a server can also receive a job from a dispatcher that has an empty server id list. In this case the server will remove its id from the 𝑑 dispatchers holding its id. Such an event can be incorporated in our model by adding exponential job abandonment. In fact it is not hard to include abandonment in our redundancy models, but we decided to exclude them the keep the presentation cleaner. We should also note that some of the rates in the JIQ-Red(𝑑) model are not known explicitly (such as the abandonment rate), but this is something that can be dealt with by solving a sequence of models with fixed input parameters (as in our model). In short, developing a means to analyze the impact of the service discipline in a redundancy model with exponential and independent replicas, should enable us to study the impact of the server selection id policy of the JIQ-Red(𝑑) load balancing policy.

We end this section by noting that [START_REF] Harte | Token redundancy in distributed JIQ[END_REF] presents a mean field model for JIQ-Red(𝑑). However, this model does not take the policy used by the dispatcher to select a server id into account. In fact if we think in terms of the corresponding redundany model as discussed above, the model in [START_REF] Harte | Token redundancy in distributed JIQ[END_REF] corresponds to our mean field model in Section 3 if we add job abandonment.

B PAIR APPROXIMATIONS FOR 𝑑 > 2 REPLICAS

The pair approximations presented in this paper for PS, FCFS, LCFS and LPS with 𝑑 = 2 can be generalized without much effort to a setting with 𝑑 > 2. The main downside of these generalizations is that determining a fixed point becomes computationally expensive as the set of ODEs has 𝑑 (for PS) or 2𝑑 (for FCFS, LCFS and LPS) dimensions. For the triplet approximation such a generalization seems less obvious. In this section, we construct the generalization of the pair approximation with PS servers and provide a numerical evaluation of this approximation.

B.1 Construction of the ODE

When the servers use PS we make use of the variables 𝜋 (𝑑 ) 𝑡 (𝑥 1 , . . . , 𝑥 𝑑 ), where the idea is that the 𝑖-th replica of a server is in a queue with length 𝑥 𝑖 . These variables are symmetric as in the case with 𝑑 = 2. We can then generalize [START_REF] Dean | The tail at scale[END_REF] to 𝜋 (𝑑 ) 𝑡 (𝑥 The queue length can then be expressed by generalizing [START_REF] Gardner | A better model for job redundancy: Decoupling server slowdown and job size[END_REF]:

𝑞 (𝑑 ) 𝑡 (𝑥) = 𝑑𝜋 (𝑑 ) 𝑡 (𝑥) 𝑥 .
Let ì 𝑥 = (𝑥 1 , . . . , 𝑥 𝑑 ) and 𝑒 𝑖 be equal to the 𝑖-th row of the order 𝑑 unity matrix. Using these notations and the above quantities the set of ODEs given by [START_REF] Harte | Token redundancy in distributed JIQ[END_REF] becomes

𝑑𝜋 (𝑑 ) 𝑡 ( ì 𝑥) 𝑑𝑡 = 𝜆 𝑑 𝑖=1 𝑞 (𝑑 ) 𝑡 (𝑥 𝑖 -1) + 𝑑𝜆 𝑑 ∑ 𝑖=1 𝜋 (𝑑 ) 𝑡 ( ì 𝑥 -𝑒 𝑖 ) -𝑑𝜋 (𝑑 ) 𝑡 ( ì 𝑥) + 𝑑 ∑ 𝑖=1 𝜋 (𝑑 ) 𝑡 ( ì 𝑥 + 𝑒 𝑖 ) ℎ (𝑑 ) 𝑡 (𝑥 𝑖 + 1) + 𝑥 𝑖 𝑥 𝑖 + 1 -𝜋 𝑡 ( ì 𝑥) 𝑑 + 𝑑 ∑ 𝑖=1 ℎ 𝑡 (𝑥 𝑖 ) ,
with the convention that 𝜋 (𝑑 ) 𝑡 ( ì 𝑥) = 0 if one of the entries of ì 𝑥 equals zero and where ℎ (𝑑 ) 𝑡 (𝑥) is given by

ℎ (𝑑 ) 𝑡 (𝑥) = (𝑥 -1) (𝑑 -1) ∑ 𝑦 ′ ≥1 𝜋 (𝑑 ) 𝑡 (𝑦 ′ |𝑥) 1 𝑦 ′ .

B.2 Numerical evaluation

Similarly to the case 𝑑 = 2, we used a numerical intergration of the ODE to compute the fixed point of the above ODE for the case 𝜆 = 0.9 and 𝑑 = 3. We truncated the queue length to 30 with gives an ODE of 30 3 variables (instead of 30 2 for 𝑑 = 2), which allows for a fast computation of the fixed point. In Table 7, we compare the values obtained by our pair approximation with values obtain by simulation and with the mean field approximation. This table illustrates that, as for 𝑑 = 2, the pair approximation for PS is very accurate.

C MORE ON THE PAIR APPROXIMATION FOR PS SERVERS

C.1 Analysis of 𝑞(0)

From ( 11), we can derive the evolution of 𝜋 𝑡 (𝑥), by summing over 𝑦 ≥ 1. This yields (for 𝑥 ≥ 1)

𝑑𝜋 𝑡 (𝑥) 𝑑𝑡 = 𝜆𝑞 𝑡 (𝑥 -1) + 2𝜆(𝜋 𝑡 (𝑥 -1) -𝜋 𝑡 (𝑥)) + 𝜋 𝑡 (𝑥 + 1) ℎ 𝑡 (𝑥 + 1) + 𝑥 𝑥 + 1 + ∑ 𝑦 ≥1 𝜋 𝑡 (𝑥, 𝑦 + 1) 𝑦 𝑦 + 1 -𝜋 𝑡 (𝑥) (2 + ℎ 𝑡 (𝑥)), (30)
where in the first equation we simplify the telescopic sum 𝑦 ≥1 𝜋 𝑡 (𝑥, 𝑦 +1)ℎ 𝑡 (𝑦 +1) -𝜋 𝑡 (𝑥, 𝑦)ℎ 𝑡 (𝑦) = -𝜋 𝑡 (𝑥, 1)ℎ 𝑡 (1) = 0 because ℎ 𝑡 (1) = 0 by definition [START_REF] Gardner | Reducing latency via redundant requests: Exact analysis[END_REF].

If we further sum (30) over 𝑥 ≥ 1, the terms 𝑥 ≥1 𝜋 𝑡 (𝑥 + 1)ℎ(𝑥 + 1) -𝜋 𝑡 (𝑥)ℎ 𝑡 (𝑥) = 0. This shows that ∑

𝑥 ≥1 𝑑𝜋 𝑡 (𝑥) 𝑑𝑡 = 𝜆 + ∑ 𝑥 ≥1 𝜋 𝑡 (𝑥 + 1) 𝑥 𝑥 + 1 + ∑ 𝑦 ≥1 𝜋 𝑡 (𝑦 + 1) 𝑦 𝑦 + 1 -2 ∑ 𝑥 ≥1 𝜋 𝑡 (𝑥) (31) = 𝜆 -2 ∑ 𝑥 ≥1 𝜋 𝑡 (𝑥) 𝑥 = 𝜆 -(1 -𝑞 𝑡 (0)), (32)
where the last line is due to [START_REF] Gardner | A better model for job redundancy: Decoupling server slowdown and job size[END_REF].

Let q𝑡 be the mean queue length at time 𝑡, then q𝑡 = 𝑥 𝑥𝑞 𝑡 (𝑥) = 2 𝑥 𝜋 𝑡 (𝑥) due to (8) and the above ODE (31) can be stated as

𝑑 q𝑡 𝑑𝑡 = 2𝜆 -2(1 -𝑞 𝑡 (0)), (33)
Hence, for any fixed point we have 𝑞(0) = 2 𝑥,𝑦 𝜋 (𝑥, 𝑦) = 1 -𝜆. This is consistent with the mean field approximation (and intuition) as the fraction of empty servers is expected to be 1 -𝜆.

C.2 Recovering the mean field model from the pair approximation

We noted earlier on that the pair approximation is more accurate than the mean field approximation.

Here, we show that the two approximation are closely linked. The ODE for (30) is written for the quantities 𝜋 𝑡 (𝑥) = 𝑥𝑞 𝑡 (𝑥)/2 while our original mean field approximation is written for the quantities 𝑞 𝑡 (𝑥). Multiplying the term (30) by 𝑥/2, the pair approximation ODE can be rewritten for 𝑞 𝑡 as follows:

𝑑𝑞 𝑡 (𝑥) 𝑑𝑡 = 2𝜆(𝑞 𝑡 (𝑥 -1) -𝑞 𝑡 (𝑥)) + 𝑞 𝑡 (𝑥 + 1) (𝑥 + 1) 𝑥 ℎ 𝑡 (𝑥 + 1) + 𝑥 𝑥 + 1 + ∑ 𝑦 ≥1 2 𝑥 𝜋 𝑡 (𝑥, 𝑦 + 1) 𝑦 𝑦 + 1 -𝑞 𝑡 (𝑥) (2 + ℎ 𝑡 (𝑥)), = 2𝜆(𝑞 𝑡 (𝑥 -1) -𝑞 𝑡 (𝑥)) + 𝑞 𝑡 (𝑥 + 1) -𝑞 𝑡 (𝑥) + 𝑞 𝑡 (𝑥 + 1) (𝑥 + 1)𝑔 𝑡 (𝑥) -𝑞 𝑡 (𝑥)𝑥𝑔 𝑡 (𝑥),
where 𝑔 𝑡 (𝑥) = 𝑦 ′ ≥1 𝜋 𝑡 (𝑦 ′ |𝑥) 1 𝑦 ′ , which is equal to ℎ 𝑡 (𝑥)/(𝑥 -1) except for 𝑥 = 1. This equation is almost the same as the mean field equation (1), except for the last two terms. Here, we show that we recover the mean field approximation if we make the approximation that 𝜋 𝑡 (𝑦|𝑥) does not depend on 𝑥, that is, if 𝜋 𝑡 (𝑦|𝑥) ≈ 𝜋 𝑡 (𝑦)/ 𝑧 𝜋 𝑡 (𝑧). Indeed, under such an approximation, we obtain that

𝑔 𝑡 (𝑥) = ∑ 𝑦 ′ ≥1 𝜋 𝑡 (𝑦 ′ |𝑥) 1 𝑦 ′ ≈ ∑ 𝑦 ′ ≥1 2𝜋 𝑡 (𝑦 ′ ) 𝑦 ′ q𝑡 = 1 q𝑡 ∑ 𝑦 ′ ≥1 𝑞 𝑡 (𝑦 ′ ) = 1 -𝑞 𝑡 (
-6𝜆𝑐 (𝑥, 𝑦, 𝑧) + 2𝜆𝑐 (𝑥 -1, 𝑦, 𝑧) + 2𝜆𝑐 (𝑥, 𝑦 -1, 𝑧) + 2𝜆𝑐 (𝑥, 𝑦, 𝑧 -1) -3𝑐 (𝑥, 𝑦, 𝑧) + 𝑐 (𝑥 + 1, 𝑦, 𝑧) 𝑥 𝑥 + 1 + 𝑐 (𝑥, 𝑦 + 1, 𝑧) 𝑦 -1 𝑦 + 1 + 𝑐 (𝑥, 𝑦, 𝑧 + 1) 𝑧 𝑧 + 1 -𝑐 (𝑥, 𝑦, 𝑧) (𝑘 (𝑦, 𝑥) + 𝑘 (𝑦, 𝑧) + ℓ (𝑥, 𝑦, 𝑧)) + 𝑐 (𝑥 + 1, 𝑦, 𝑧)𝑘 (𝑦, 𝑥 + 1) + 𝑐 (𝑥, 𝑦, 𝑧 + 1)𝑘 (𝑦, 𝑧 + 1) + 𝑐 (𝑥, 𝑦 + 1, 𝑧)ℓ (𝑥, 𝑦 + 1, 𝑧),
by just replacing the corresponding quantities by 𝑘 and ℓ.

Recall that 𝜋 (𝑥, 𝑦) = 𝑐 (𝑥, 𝑦)/(𝑦 -1) = 𝑧 𝑐 (𝑥, 𝑦, 𝑧)/(𝑦 -1) . Hence, to obtain an ODE for 𝜋, we sum the above equation over 𝑧, which shows that (for 𝑦 ≥ 2):

𝑑 𝑑𝑡 𝑐 (𝑥, 𝑦) = 𝜆𝑞(𝑥 -1)𝑞(𝑦 -1) (𝑦 -1) + 𝜆𝑞(𝑦 -1)𝑐 (𝑥 |𝑦 -1) (𝑦 -1) -6𝜆𝑐 (𝑥, 𝑦) + 2𝜆𝑐 (𝑥 -1, 𝑦) + 2𝜆𝑐 (𝑥, 𝑦 -1) + 2𝜆𝑐 (𝑥, 𝑦) -3𝑐 (𝑥, 𝑦) + 𝑐 (𝑥 + 1, 𝑦) 𝑥 𝑥 + 1 + 𝑐 (𝑥, 𝑦 + 1) 𝑦 -1 𝑦 + 1 + ∑ 𝑧 𝑐 (𝑥, 𝑦, 𝑧 + 1) 𝑧 𝑧 + 1 -𝑐 (𝑥, 𝑦)𝑘 (𝑦, 𝑥) - ∑ 𝑧 𝑐 (𝑥, 𝑦, 𝑧)𝑘 (𝑦, 𝑧) - ∑ 𝑧 𝑐 (𝑥, 𝑦, 𝑧)ℓ (𝑥, 𝑦, 𝑧) + 𝑐 (𝑥 + 1, 𝑦)𝑘 (𝑦, 𝑥 + 1) + ∑ 𝑧 𝑐 (𝑥, 𝑦, 𝑧 + 1)𝑘 (𝑦, 𝑧 + 1) + ∑ 𝑧 𝑐 (𝑥, 𝑦 + 1, 𝑧)ℓ (𝑥, 𝑦 + 1, 𝑧)
There are a few simplification to the above equation:

• The last term of the second line removes 2𝜆 of the 6𝜆 of the first term.

• On the third line, the third term is equal to 𝑐 (𝑥, 𝑦 + 1) -4𝜆𝜋 (𝑥, 𝑦) + 2𝜆𝜋 (𝑥 -1, 𝑦) + 2𝜆𝜋 (𝑥, 𝑦 -1)

𝑦-1 𝑦+1 = 𝑦-1 𝑦 𝑐 (𝑥, 𝑦 +
-2𝜋 (𝑥, 𝑦) + 𝜋 (𝑥 + 1, 𝑦) 𝑥 𝑥 + 1 + 𝜋 (𝑥, 𝑦 + 1) 𝑦 𝑦 + 1 - 1 𝑦 -1 ∑ 𝑧 𝑐 (𝑥, 𝑦, 𝑧) 1 𝑧 - 1 𝑦 -1 𝑐 (𝑥, 𝑦)𝑘 (𝑦, 𝑥) - 1 𝑦 -1 ∑ 𝑧 𝑐 (𝑥, 𝑦, 𝑧)ℓ (𝑥, 𝑦, 𝑧) + 1 𝑦 -1 𝑐 (𝑥 + 1, 𝑦)𝑘 (𝑦, 𝑥 + 1) + 1 𝑦 -1 ∑ 𝑧 𝑐 (𝑥, 𝑦 + 1, 𝑧)ℓ (𝑥, 𝑦 + 1, 𝑧) (34)
where the term (*) comes from the third term of the second line that can be rewritten as 2𝜆 times 𝑐 (𝑥, 𝑦 -1) = (𝑦 -2)𝜋 (𝑥, 𝑦 -1) = (𝑦 -1)𝜋 (𝑥, 𝑦 -1) -𝜋 (𝑥, 𝑦 -1). By reorganizing the terms, the above equation rewrites as:

𝑑 𝑑𝑡 𝜋 (𝑥, 𝑦) = 𝜆𝑞(𝑥 -1)𝑞(𝑦 -1) + 2𝜆[𝜋 (𝑥 -1, 𝑦) + 𝜋 (𝑥, 𝑦 -1) -2𝜋 (𝑥, 𝑦)] + 𝜋 (𝑥 + 1, 𝑦) [ 𝑥 𝑥 + 1 + 𝑘 (𝑦, 𝑥 + 1)] + 𝜋 (𝑥, 𝑦 + 1) 𝑦 𝑦 + 1 -𝜋 (𝑥, 𝑦) [2 + 𝑘 (𝑦, 𝑥)] + 1 𝑦 -1 ∑ 𝑧 𝑐 (𝑥, 𝑦 + 1, 𝑧)ℓ (𝑥, 𝑦 + 1, 𝑧) - 1 𝑦 -1 ∑ 𝑧 𝑐 (𝑥, 𝑦, 𝑧) 1 𝑧 - 1 𝑦 -1
The ODE (35) is close to the pair approximation equation but with two modifications:

• The quantity ℎ(𝑥) of the pair approximation is replaced by 𝑘 (𝑦, 𝑥) and the quantity ℎ(𝑦) is replaced by 𝑚(𝑥, 𝑦 + 1). • the last line does not exist for the pair approximation.

The pair approximation consists in assuming that when three servers are connected, their state only depends on the middle node (note that this only make sense when 𝑦 ≥ 2). Written in terms of 𝑐 𝑡 (𝑥, 𝑦, 𝑧), this means that for 𝑦 ≥ 2 we would have: 𝑐 𝑡 (𝑥, 𝑦, 𝑧) ≈ 𝑐 𝑡 (𝑥, 𝑦)𝑐 𝑡 (𝑧|𝑦) = (𝑦 -1)𝜋 𝑡 (𝑥, 𝑦) 𝜋 𝑡 (𝑦, 𝑧) 𝜋 𝑡 (𝑦)

, ( 36
)
where by construction 𝑐 𝑡 (𝑧|𝑦) = 𝜋 𝑡 (𝑧|𝑦) = 𝜋 𝑡 (𝑦, 𝑧)/𝜋 𝑡 (𝑦), see [START_REF] Gardner | Redundancy-d: The power of d choices for redundancy[END_REF]. A straightforward computation shows that if one assumes (36), then one has 𝑚(𝑥, 𝑦) = 𝑘 (𝑥, 𝑦) = ℎ(𝑦). In such a case, the ODE (35) corresponds exactly to the triplet approximation.

E
where the second equality is found by summing (21) over 𝑥.

Let q𝑡 be the mean queue length at time 𝑡, then q𝑡 = 𝑥 𝑥𝑞 𝑡 (𝑥) = 2 𝑥 1 ,𝑥 𝛿 𝑡 (𝑥 1 , 𝑥) due to (22) and the above ODE can be stated as

𝑑 q𝑡 𝑑𝑡 = 2𝜆 -2(1 -𝑞 𝑡 (0)), (39)
similar to the PS case. Hence, for any fixed point we have 𝑞(0) = 1 -𝜆.

E.2 Recovering the mean field model from the pair approximation

The independence assumption that we used in Section 3 to construct the mean field approximation consists in saying that the position of two replicas are independent, that is

𝛿 𝑡 (𝑥 1 , 𝑦
while 𝑞 𝑡 (0) = 1 -𝑥 ≥1 𝑞 𝑡 (𝑥), which is the same as the mean field approximation [START_REF] Ananthanarayanan | Effective straggler mitigation: Attack of the clones[END_REF]. This shows that, as for PS, the mean field ODE can be recovered from the pair approximation for FCFS if we assume independence. Note, however, that solving numerically (1), ( 11) and [START_REF] Visschers | A product form solution to a system with multi-type jobs and multi-type servers[END_REF] do not lead to the same fixed point. This implies that without the independent assumption, the PS and FCFS models do not yield the same performance.

F MORE MODEL VALIDATION NUMBERS

This section presents additional numerical results to assess the accuracy of the various approximations as a function of the number of servers. The tables presented here are the same as the ones presented in the main body of the paper but with other parameters values. In more details, the tables presented here are:

• Table 8 and Table 9 complement Table 3 and validate the accuracy of the pair and triplet approximations for 𝜆 = 0.5 and 𝜆 = 0.7. • Table 10 and Table 11 complement Table 4 and validate the accuracy of the pair approximation for FCFS for 𝜆 = 0.5 and 𝜆 = 0.7. • Table 12 and Table 13 do the same for LCFS.

• Table 14 and Table 15 do the same for LPS(2).

Finally, Figure 6 illustrates how our various approximation can serve to estimate the average queue length for FCFS, LCFS and LPS. It complements Figure 2 that focuses only on PS. This figure shows that the accuracy of the pair approximation for LPS and FCFS are very good even if not as precise as the one for PS. The accuracy of the pair approximation for LCFS is somehow less good because of the strong correlations between replicas. For FCFS, we also plot the numbers from [START_REF] Gardner | Redundancy-d: The power of d choices for redundancy[END_REF] that are shown to be asymptotically exact in [START_REF] Shneer | Large-scale parallel server system with multi-component jobs[END_REF]. This graph shows that our approximation for FCFS is very close to the one of [START_REF] Gardner | Redundancy-d: The power of d choices for redundancy[END_REF] while being different. We observe that all pair-approximations provide estimated queue lengths that are slightly optimistic compared to the values for finite 𝑁 . This is not the case for the mean field approximation that can provide optimistic or pessimistic estimates depending on the scheduling policies or the load.

  = 10 2 3.4449 1.3943e-01 1.6088e-01 1.5932e-01 1.0855e-01 9.1793e-03 𝑛 = 10 3 3.3947 1.4018e-01 1.6272e-01 1.6178e-01 1.0949e-01 7.9446e-03 𝑛 = 10 4 3.3890 1.4030e-01 1.6293e-01 1.6205e-01 1.0956e-01 7.8142e-03 𝑛 = 10 5 3.3890 1.4030e-01 1.6293e-01 1.6205e-01 1.0956e-01 7.8142e-03 Triplet Approx. 3.3894 1.4020e-01 1.6289e-01 1.6207e-01 1.0962e-01 7.8059e-03 Pair Approx. 3.3875 1.4032e-01 1.6300e-01 1.6215e-01 1.0960e-01 7.7756e-03 Mean field 3.3377 1.4177e-01 1.6578e-01 1.6496e-01 1.0950e-01 6.8438e-03

9 Fig. 2 .

 92 Fig.2. Average queue length as a function of the number of servers 𝑛: we compare the numbers obtained by simulation (for finite 𝑛) to the pair and triplet approximations.

  = 10 2 3.1793 1.4732e-01 1.7636e-01 1.7481e-01 1.0716e-01 4.4893e-03 𝑛 = 10 3 3.1227 1.4872e-01 1.7950e-01 1.7840e-01 1.0709e-01 3.4895e-03 𝑛 = 10 4 3.1171 1.4884e-01 1.7983e-01 1.7879e-01 1.0707e-01 3.3952e-03 𝑛 = 10 5 3.1171 1.4884e-01 1.7983e-01 1.7879e-01 1.0707e-01 3.3952e-03 2𝜆𝐸 [𝑇 ] [90965 1.4921e-01 1.8097e-01 1.8031e-01 1.0706e-01 3.0484e-03 Mean Field 3.3377 1.4177e-01 1.6578e-01 1.6496e-01 1.0950e-01 6.8438e-03Table 4. Accuracy of Mean Field and Pair Approximation for FCFS servers, arrival rate 𝜆 = 0.9.

  = 10 2 3.2880 1.4309e-01 1.6921e-01 1.6859e-01 1.0905e-01 6.0308e-03 𝑛 = 10 3 3.2256 1.4491e-01 1.7221e-01 1.7171e-01 1.0903e-01 4.8872e-03 𝑛 = 10 4 3.2243 1.4478e-01 1.7226e-01 1.7194e-01 1.0919e-01 4.8114e-03 𝑛 = 10 5 3.2243 1.4478e-01 1.7226e-01 1.7194e-01 1.0919e-01 4.8114e-03 Pair Approx. 3.2166 1.4484e-01 1.7258e-01 1.7248e-01 1.0932e-01 4.6412e-03 Mean Field 3.3377 1.4177e-01 1.6578e-01 1.6496e-01 1.0950e-01 6.8438e-03

2 )

 2 = 𝑥 1 𝛾 𝑡 (𝑥 1 , 𝑥 2 ). The queue length can be expressed as 𝑞 𝑡 (𝑥) = 2(𝛾 1)) or equivalently as 𝑞 𝑡 (𝑥) = 2𝛾 (𝑞𝑙 ) 𝑡 (𝑥)/𝑥 or 𝑞 𝑡 (𝑥) = 2𝛾 𝑡 (1, 𝑥).

  = 10 2 3.9944 1.2787e-01 1.3872e-01 1.3535e-01 1.0262e-01 2.0748e-02 𝑛 = 10 3 3.9484 1.2803e-01 1.3949e-01 1.3658e-01 1.0391e-01 1.9867e-02 𝑛 = 10 4 3.9415 1.2815e-01 1.3963e-01 1.3675e-01 1.0404e-01 1.9733e-02 𝑛 = 10 5 3.9415 1.2815e-01 1.3963e-01 1.3675e-01 1.0404e-01 1.9733e-02 Pair Approx. 3.6966 1.3135e-01 1.4699e-01 1.4635e-01 1.0916e-01 1.3939e-02 Mean Field 3.3377 1.4177e-01 1.6578e-01 1.6496e-01 1.0950e-01 6.8438e-03

9 Fig. 3 .

 93 Fig. 3. Queue length distributions of the various policies (computed by the pair approximations).

Fig. 4 .

 4 Fig.[START_REF] Anton | The stationary distribution of the redundancy-d model with random order of service[END_REF]. Average queue length as a function of 𝜆. Unless specified otherwise, all numbers are computed by using the pair approximations that we derive in the paper..

(Fig. 5 .

 5 Fig. 5. Rate at which the buddy replica disappears as a function of the state of the first job (as a function of the queue length for PS and of the position of the job or the queue length for LCFS or LCFS).

  0) q𝑡 .D RECOVERING THE PAIR APPROXIMATION FROM THE TRIPLET APPROXIMATIONHere, we show that one can recover the pair approximation from the triplet approximation when assuming an extra independence assumption (Equation (36) below).To show that, we introduce two new quantities 𝑘 (𝑦, 𝑥)= 𝑣 𝑐 (𝑣 |𝑦, 𝑥) 𝑥 -1 𝑣 = 𝑥 -1 𝑐 (𝑦,𝑥 ) 𝑣 𝑐 (𝑦,𝑥,𝑣) 𝑣 and ℓ (𝑥, 𝑦, 𝑧) = 𝑣 𝑐 (𝑣 |𝑥, 𝑦, 𝑧) 𝑦-2 𝑣 . By using these notations, the triplet ODE (20) can be writen as 𝑑 𝑑𝑡 𝑐 (𝑥, 𝑦, 𝑧) = 𝜆𝑞(𝑥 -1)𝑞(𝑦 -1)𝑐 (𝑧|𝑦 -1) (𝑦 -1) + 𝜆𝑞(𝑦 -1)𝑞(𝑧 -1)𝑐 (𝑥 |𝑦 -1) (𝑦 -1)

1 )

 1 𝜋 (𝑥, 𝑦 + 1) 𝑦 𝑦+1 and the last term is equal to 𝑧 𝑐 (𝑥, 𝑦, 𝑧 + 1) 𝑧 𝑧+1 = 𝑐 (𝑥, 𝑦) -𝑧 ≥1 𝑐 (𝑥, 𝑦, 𝑧) 1 𝑧 because the sum can starts at 𝑧 = 0 (as 𝑐 (., ., 0) = 0). • The last term of the fourth cancels with the second term of the fifth line because, as before, the sum can starts at 𝑧 = 0 or 𝑧 = 1 because as 𝑐 (., ., 0) = 0. By using that 𝜋 (𝑥, 𝑦) = 𝑐 (𝑥, 𝑦)/(𝑦 -1), this implies that 𝑑 𝑑𝑡 𝜋 (𝑥, 𝑦) = 𝜆𝑞(𝑥 -1)𝑞(𝑦 -1) + 𝜆𝑞(𝑦 -1)𝑐 (𝑥 |𝑦 -1) -2𝜆 𝑦 -1 𝜋 (𝑥, 𝑦 -1) (*) moved from second line. Cancels with previous term.

1 1 1 + 1 (

 111 ∑ 𝑧 𝑐 (𝑥, 𝑦, 𝑧)ℓ (𝑥, 𝑦, 𝑧) Let 𝑚(𝑥, 𝑦) = 1 𝑦-2 𝑧 𝑐 (𝑥, 𝑦, 𝑧)ℓ (𝑥, 𝑦, 𝑧)/𝜋 (𝑥, 𝑦) for 𝑦 ≥ 2 and 𝑚(𝑥, 2) = 0. The last line of the above equation is equal to 1 𝑦 -1𝜋 (𝑥, 𝑦) ∑ 𝑧 𝑐 (𝑥, 𝑦, 𝑧) 𝑧𝜋 (𝑥, 𝑦) -𝑦 -2 𝑦 -𝑦 -2 ∑ 𝑧 𝑐 (𝑥, 𝑦, 𝑧)ℓ (𝑥, 𝑦, 𝑧) = -1 𝑦 -1 𝜋 (𝑥, 𝑦)𝑘 (𝑥, 𝑦) -𝜋 (𝑥, 𝑦)𝑚(𝑥, 𝑦) + 1 𝑦 -1 𝜋 (𝑥, 𝑦)𝑚(𝑥, 𝑦).Hence, using that 𝑚(𝑥, 𝑦 + 1) = 1 𝑦-1 𝑧 𝑐 (𝑥, 𝑦 + 1, 𝑧)ℓ (𝑥, 𝑦 + 1, 𝑧)/𝜋 (𝑥, 𝑦 + 1), we can rewrite the total sum as 𝑑 𝑑𝑡 𝜋 (𝑥, 𝑦) = 𝜆𝑞(𝑥 -1)𝑞(𝑦 -1) + 2𝜆[𝜋 (𝑥 -1, 𝑦) + 𝜋 (𝑥, 𝑦 -1) -2𝜋 (𝑥, 𝑦)] + 𝜋 (𝑥 + 1, 𝑦) 𝑘 (𝑦, 𝑥 + 1) + 𝑥 𝑥 + 𝜋 (𝑥, 𝑦 + 1) 𝑚(𝑥, 𝑦 + 1) + 𝑦 𝑦 + 1 -𝜋 (𝑥, 𝑦) [2 + 𝑘 (𝑦, 𝑥) + 𝑚(𝑥, 𝑦)] + 𝜋 (𝑥, 𝑦) 𝑦 -𝑚(𝑥, 𝑦) -𝑘 (𝑥, 𝑦)) ,

9 Fig. 6 .

 96 Fig.6. Complement of Figure2with other values. Average queue length as a function of 𝑛: we compare the numbers obtained by simulation (for finite 𝑛) to the different approximations. Solid lines correspond to simulations whereas dashed lines correspond to pair approximation. We observe that all pair-approximations provide estimated queue lengths that are slightly optimistic compared to the values for finite 𝑁 . This is not the case for the mean field approximation that can provide optimistic or pessimistic estimates depending on the scheduling policies or the load.

Table

Table 1 .

 1 . This table shows that the two steady-state distribution are close, but distinct. To rule out numerical issues or effects due to the bounded value of 𝐾, we compare the theoretical values with simulations that show the exact same trend. Mean queue length and steady-state distribution of the queue lengths of servers for a redundancy-2 system with 𝑛 = 3, arrival rate 𝜆 = 0.5 and service rate 𝜇 = 1.

	Number of jobs	mean	1	2	3	4	5	6	7
	FCFS (exact [9]) 0.88889 0.27500 0.12875 0.05619 0.02365 0.00975 0.00397 0.00161
	FCFS (simu)	0.88892 0.27499 0.12875 0.05619 0.02365 0.00975 0.00397 0.00161
	PS (chain 𝐾=20) 0.89225 0.27423 0.12862 0.05641 0.02391 0.00994 0.00409 0.00167
	PS (simu)	0.89217 0.27422 0.12862 0.05642 0.02391 0.00994 0.00409 0.00167
	Number of jobs mean	1	2		3	5	10
	FCFS:	3.1171 1.4884e-01 1.7984e-01 1.7882e-01 1.0707e-01 3.3898e-03
	LPS(2):	3.2243 1.4480e-01 1.7229e-01 1.7197e-01 1.0919e-01 4.8019e-03
	LPS(5):	3.3483 1.4140e-01 1.6511e-01 1.6434e-01 1.0958e-01 7.0372e-03
	LPS(10):	3.3884 1.4030e-01 1.6296e-01 1.6211e-01 1.0959e-01 7.7873e-03
	PS:	3.3890 1.4029e-01 1.6293e-01 1.6207e-01 1.0959e-01 7.8041e-03
	LCFS:	3.9415 1.2816e-01 1.3965e-01 1.3677e-01 1.0405e-01 1.9717e-02

Table 2

 2

. Simulation results for number of jobs in a queue of a redundancy-2 system with 𝑛 = 100000 servers, arrival rate 𝜆 = 0.9 and service rate 𝜇 = 1.

  Fig. 1. Example of a dynamic random graph for a system with 𝑛 = 10 servers. The labels on the servers indicate degrees. A new edge is added between two nodes at rate 2𝜆. An edge connecting two nodes (𝑢, 𝑣) of degrees 𝑑 𝑡 (𝑢) and 𝑑 𝑡 (𝑣) disapears at rate 1/𝑑 𝑡 (𝑢) + 1/𝑑 𝑡 (𝑣).

				1) (3,1) (3,2)
		𝜋 (𝑥, 𝑦)	1 10	1 20	1 10	1 20
	(a) The multigraph model	(b) The (simple) graph	(c) Values 𝜋 (𝑥, 𝑦)

Table 3 .

 3 Accuracy of Mean Field, Pair and Triplet Approximation for PS servers, arrival rate 𝜆 = 0.9.

  𝑦, 𝑧) = 𝜆𝑞 𝑡 (𝑥 -1)𝑞 𝑡 (𝑦 -1)𝑐 𝑡 (𝑧|𝑦 -1) (𝑦 -1) + 𝜆𝑞 𝑡 (𝑦 -1)𝑞 𝑡 (𝑧 -1)𝑐 (𝑥 |𝑦 -1) (𝑦 -1) -6𝜆𝑐 𝑡 (𝑥, 𝑦, 𝑧) + 2𝜆𝑐 𝑡 (𝑥 -1, 𝑦, 𝑧) + 2𝜆𝑐 𝑡 (𝑥, 𝑦 -1, 𝑧) + 2𝜆𝑐 𝑡 (𝑥, 𝑦, 𝑧 -1)

	and
	𝑑	𝑐 𝑡 (𝑥,
	𝑑𝑡

-3𝑐 𝑡 (𝑥, 𝑦, 𝑧) + 𝑐 𝑡 (𝑥 + 1, 𝑦, 𝑧) 𝑥 𝑥 + 1 + 𝑐 𝑡 (𝑥, 𝑦 + 1, 𝑧) 𝑦 -1 𝑦 + 1 + 𝑐 𝑡 (𝑥, 𝑦, 𝑧 + 1) 𝑧 𝑧 + 1 -𝑐 𝑡 (𝑥, 𝑦, 𝑧) ∑ 𝑣 𝑐 𝑡 (𝑣 |𝑦, 𝑥) 𝑥 -1 𝑣 + ∑ 𝑣 𝑐 𝑡 (𝑣 |𝑦, 𝑧) 𝑧 -1 𝑣 + ∑ 𝑣 𝑐 𝑡 (𝑣 |𝑥, 𝑦, 𝑧) 𝑦 -2 𝑣 + 𝑐 𝑡 (𝑥 + 1, 𝑦, 𝑧) ∑ 𝑣 𝑐 𝑡 (𝑣 |𝑦, 𝑥 + 1) 𝑥 𝑣 + 𝑐 𝑡 (𝑥, 𝑦, 𝑧 + 1) ∑ 𝑣 𝑐 𝑡 (𝑣 |𝑦, 𝑧 + 1)

  5.1.1 Types of jobs. Each job is composed of two replicas that we call the first and the second replica. We denote by 2𝑛𝛿 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 ) the number of jobs that have their first replica in position 𝑥 1 in a queue with length 𝑥 2 and their second replica in position 𝑦 1 in a queue with length 𝑦 2 (or vice versa). Note that 𝑥 1 ≤ 𝑥 2 and 𝑦 1 ≤ 𝑦 2 . As before, the quantity 𝛿 𝑡 is symmetric (i.e., 𝛿 𝑡 (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 ) = 𝛿 𝑡 (𝑦 1 , 𝑥 1 , 𝑦 2 , 𝑥 2 ) for all 𝑥 1 , 𝑥 2 , 𝑦 1 , 𝑦 2 ≥ 1) and we denote by

  1 , 𝑦 1 , 𝑥 2 , 𝑦 2 ). Each job of type (1, 𝑦 1 , 𝑥 2 , 𝑦 2 ) or (𝑥 1 , 1, 𝑥 2 , 𝑦 2 ) is served at rate 1, hence we have a death rate of type (1, 𝑦 1 , 𝑥 2 , 𝑦 2 ) and (𝑥 1 , 1, 𝑥 2 , 𝑦 2 ) jobs equal to 1. A new type (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 ) job is created at rate 𝜆𝑞 𝑡 (𝑥 2 -1)𝑞 𝑡 (𝑦 2 -1)if 𝑥 1 = 𝑥 2 and 𝑦 1 = 𝑦 2 as any new job joins the back of the queue. This is the birth rate of type (𝑥 2 , 𝑦 2 , 𝑥 2 , 𝑦 2 ) jobs.

  1 , 𝑦 1 , 𝑥 2 , 𝑦 2 ). Similar to the 𝜅 𝑡 (𝑥 𝑎 , 𝑥 𝑏 ) values for the FCFS model, we now define the 𝜓 𝑡 (𝑥 𝑎 , 𝑥 𝑏 ) values, that is,

Table 6 .

 6 Accuracy of Mean Field and Pair Approximation for LCFS servers, arrival rate 𝜆 = 0.9.

Table 7 .

 7 Accuracy of Mean Field and Pair Approximation for PS servers, arrival rate 𝜆 = 0.8 and 𝑑 = 3.

	Number of jobs mean	1	2	3	5	10
	Simul 𝑛 = 10 2 1.9374 2.5592e-01 2.2734e-01 1.5648e-01 4.2942e-02 2.2749e-04
	𝑛 = 10 3 1.9072 2.5867e-01 2.3084e-01 1.5766e-01 4.0735e-02 1.3987e-04
	𝑛 = 10 4 1.9046 2.5891e-01 2.3117e-01 1.5780e-01 4.0532e-02 1.3236e-04
	𝑛 = 10 5 1.9033 2.5905e-01 2.3124e-01 1.5774e-01 4.0449e-02 1.3136e-04
	Pair Approx. 1.9033 2.5904e-01 2.3125e-01 1.5776e-01 4.0448e-02 1.3110e-04
	Mean Field 1.8947 2.6024e-01 2.3227e-01 1.5776e-01 3.9746e-02 1.1981e-04

  𝑡 (𝑥 1 , 𝑥 2 . . . , 𝑥 𝑑 ).

		1 ) =	∑	𝜋 (𝑑 ) 𝑡 (𝑥 1 , . . . , 𝑥 𝑑 ),
			𝑥 2 ,...,𝑥 𝑑
	and (9) to
	𝜋 (𝑑 ) 𝑡 (𝑥 2 |𝑥 1 ) =	1 𝑡 (𝑥 1 ) 𝑥 (𝑑 )	𝑥 3 ,...,𝑥 𝑑 ∑	𝜋 (𝑑 )

  MORE ON THE PAIR APPROXIMATION FOR FCFS SERVERS E.1 Analysis of 𝑞(0) Summing (23) 𝑦 1 and 𝑦 2 and simplifying yields𝑑𝛿 𝑡 (𝑥 1 , 𝑥 2 ) 𝑑𝑡 = 𝜆𝑞 𝑡 (𝑥 2 -1)1[𝑥 1 = 𝑥 2 ] -2𝜆𝛿 𝑡 (𝑥 1 , 𝑥 2 ) + 2𝜆𝛿 𝑡 (𝑥 1 , 𝑥 2 -1) -𝛿 𝑡 (𝑥 1 , 𝑥 2 ) + 𝛿 𝑡 (𝑥 1 + 1, 𝑥 2 + 1) -𝛿 𝑡 (𝑥 1 , 1, 𝑥 2 ) -𝛿 𝑡 (𝑥 1 , 𝑥 2 ) 𝜅 𝑡 (𝑥 2 , 𝑥 2 ) -𝛿 𝑡 (𝑥 1 , 1, 𝑥 2 ) 𝛿 𝑡 (𝑥 1 , 𝑥 2 ) + 𝛿 𝑡 (𝑥 1 + 1, 𝑥 2 + 1)𝜅 𝑡 (𝑥 1 , 𝑥 2 + 1) + 𝛿 𝑡 (𝑥 1 , 𝑥 2 + 1) [𝜅 𝑡 (𝑥 2 + 1, 𝑥 2 + 1) -𝜅 𝑡 (𝑥 1 , 𝑥 2 + 1)] .(37)If we further sum (37) over 𝑥 1 and 𝑥 2 , we find ∑ 𝑥 1 ,𝑥 2 𝑑𝛿 𝑡 (𝑥 1 , 𝑥 2 ) 𝑑𝑡

	= 𝜆 -2𝛿	(𝑝𝑜𝑠 ) 𝑡

(1, 𝑥 2 ) = 𝜆 -(1 -𝑞 𝑡 (0)),

  1 , 𝑥 2 , 𝑦 2 ) ≈ 𝛿 𝑡 (𝑥 1 , 𝑥 2 )𝛿 𝑡 (𝑦 1 , 𝑦 2 ) 𝑧 1 ,𝑧 2 𝛿 𝑡 (𝑧 1 , 𝑧 2 ) = 2𝛿 𝑡 (𝑥1 , 𝑥 2 )𝛿 𝑡 (𝑦 1 , 𝑦 2 ) q𝑡 , where q𝑡 = 𝑥 𝑥𝑞 𝑡 (𝑥) = 2 𝑥 1 ,𝑥 2 𝛿 𝑡 (𝑥 1 , 𝑥 2 ) due to (22) is the mean queue length. The independence assumption also implies that 𝜅 𝑡 (𝑥 𝑎 , 𝑥 𝑏 ) ≈ 2𝑥 𝑎 𝛿 𝑑𝑡 ≈ 𝜆𝑞 𝑡 (𝑥 2 -1) -2𝜆(𝛿 𝛿 𝑡 (𝑥 1 + 1, 𝑥 2 + 1) -𝛿 𝛿 𝑡 (𝑥 1 + 1, 𝑥 2 + 1)𝑥 1 𝛿 𝑡 (𝑥 1 , 𝑥 2 + 1) (𝑥 2 -𝑥 1 + 1) + 1) -𝛿 𝑡 (1, 𝑥 2 + 1) -Using (22) we can transform this into a set of ODEs for 𝑞 𝑡 (𝑥) for 𝑥 > 0 by noting that 𝑞 𝑡 (𝑥) = 2𝛿 𝑡 (1, 𝑥) and 2𝛿 𝑑𝑞 𝑡 (𝑥) 𝑑𝑡 = 𝑞 𝑡 (𝑥 + 1) -𝑞 𝑡 (𝑥) + 2𝜆 [𝑞 𝑡 (𝑥 -1) -𝑞 𝑡 (𝑥)] + (1 -𝑞 𝑡 (0)) ((𝑥 + 1)𝑞 𝑡 (𝑥 + 1) -𝑥𝑞 𝑡 (𝑥))

	over 𝑥 1 yields
	𝑑𝛿	(𝑞𝑙 ) 𝑡	(𝑥 2 )				(𝑞𝑙 ) 𝑡	(𝑥 2 ) -𝛿	(𝑞𝑙 ) 𝑡	(𝑥 2 -1)) -𝛿	(𝑞𝑙 ) 𝑡	(𝑥 2 )
			+	∑			(𝑞𝑙 ) 𝑡	(𝑥 2 )	2𝛿	(𝑝𝑜𝑠 ) 𝑡 q𝑡	(1)	-𝛿	(𝑞𝑙 ) 𝑡	(𝑥 2 ) (𝑥 2 -1)	2𝛿	(𝑝𝑜𝑠 ) 𝑡 q𝑡	(1)
				𝑥 1
			+	∑			2𝛿	(𝑝𝑜𝑠 ) 𝑡	(1)	+	∑	2𝛿	(𝑝𝑜𝑠 ) 𝑡	(1)
									q𝑡				q𝑡
				𝑥 1									𝑥 1
			= 𝜆𝑞 𝑡 (𝑥 2 -1) -2𝜆(𝛿	(𝑞𝑙 ) 𝑡	(𝑥 2 ) -𝛿	(𝑞𝑙 ) 𝑡	(𝑥 2 -1)) -𝛿	(𝑞𝑙 ) 𝑡	(𝑥 2 )
			+ 𝛿	(𝑞𝑙 ) 𝑡	(𝑥 2 2𝛿	(𝑝𝑜𝑠 ) 𝑡 q𝑡	(1)	𝛿	(𝑞𝑙 ) 𝑡	(𝑥 2 )𝑥 2 -𝛿	(𝑞𝑙 ) 𝑡	(𝑥 2 + 1)𝑥 2 .	(40)
			(𝑝𝑜𝑠 )
			𝑡
														,
														q𝑡
											(𝑝𝑜𝑠 ) 𝑡	(1)/ q𝑡 . Plugging this into (37) and summing

(1) = 1 -𝑞 𝑡 (0):

In Appendix A) we further indicate that the model that we study is also relevant in the context of Join-Idle-Queue load balancing[START_REF] Lu | Join-idle-queue: A novel load balancing algorithm for dynamically scalable web services[END_REF] with redundant tokens.

ACKNOWLEDGMENTS

This work is supported by the French National Research Agency (ANR) through REFINO Project under Grant ANR-19-CE23-0015 and by FWO (Fonds voor Wetenschappelijk Onderzoek).

A LINK WITH JOIN-IDLE-QUEUE LOAD BALANCING WITH REDUNDANCY

While we believe that studying redundancy systems with different service disciplines is important on its own, we provide additional motivation for the specific model with exponential job sizes and i.i.d. replicas in this section. More specifically, we argue that our redundancy models can be used to study the so-called Join-Idle-Queue (JIQ) load balancing policy with redundancy as explained below. In fact, this was the original problem that triggered us to look at these redundancy models.

Under the traditional JIQ policy [START_REF] Lu | Join-idle-queue: A novel load balancing algorithm for dynamically scalable web services[END_REF][START_REF] Stolyar | Pull-based load distribution in large-scale heterogeneous service systems[END_REF] each dispatcher maintains a list of servers ids that are considered to be idle. When a job arrives at a dispatcher and the list is non-empty, the dispatcher assigns the incoming job to one of the servers in the list and removes this server id from the