The Power of Choice in Priority Scheduling

arXiv:1706.04178v1 [] 13 Jun 2017

Dan Alistarh
IST Austria & ETH Zurich
dan.alistarh@inf.ethz.ch

Justin Kopinsky
Massachusetts Institute of Technology
jkopin@mit.edu

Jerry Li
Massachusetts Institute of Technology
jerryzli@mit.edu

Giorgi Nadiradze
ETH Zurich
giorgi.nadiradze@inf.ethz.ch

June 14, 2017
Abstract
Consider the following random process: we are given n queues, into which elements of increasing labels are
inserted uniformly at random. To remove an element, we pick two queues at random, and remove the element of
lower label (higher priority) among the two. The cost of a removal is the rank of the label removed, among labels still
present in any of the queues, that is, the distance from the optimal choice at each step. Variants of this strategy are
prevalent in state-of-the-art concurrent priority queue implementations. Nonetheless, it is not known whether such
implementations provide any rank guarantees, even in a sequential model.
We answer this question, showing that this strategy provides surprisingly strong guarantees: Although the singlechoice process, where we always insert and remove from a single randomly chosen queue, has degrading cost, going
to infinity as we increase the number of steps, in the two choice process, the expected rank of a removed element is
O(n) while the expected worst-case cost is O(n log n). These bounds are tight, and hold irrespective of the number
of steps for which we run the process. The argument is based on a new technical connection between “heavily
loaded” balls-into-bins processes and priority scheduling. Our analytic results inspire a new concurrent priority
queue implementation, which improves upon the state of the art in terms of practical performance.

1

Introduction

The last two decades have seen tremendous progress in the area of concurrent data structures, to the point where
scalable versions of many classic data structures are now known, including lists [4, 16], skip-lists [13, 18, 21], hashtables [19,22,25,34], or search trees [1,9,23]. In this context, significant research attention has been given to concurrent
producer-consumer data structures, such as queues, stacks, or priority queues, which are critical in concurrent systems.
On the one hand, several elegant designs, e.g. [11, 12, 27, 28], have pushed the these data structures to the limits of
scalability on current processor architectures. On the other, impossibility results [2, 10] show that such data structures
providing strong ordering semantics also have inherent sequential bottlenecks which limit their scalability.
A popular approach for circumventing these impossibility results is to relax data structure semantics [35]. The first
instance of this strategy is probably the relaxed PRAM priority queue structure of Karp and Zhang [20], designed for
efficient parallel execution of branch-and-bound programs. A flurry of subsequent work, e.g. [3, 6, 15, 24, 29, 32, 33,
36, 38], has shown that relaxed semantics can yield extremely good practical results, and that it can be very useful in
the context of higher-level constructs, such as concurrent graph algorithms [29].1
Notably, the current state-of-the-art concurrent priority queue is obtained by the following MultiQueue strategy [14,
32]. We start from n queues, each protected by a lock. To insert an element, a processor picks one of the n queues
uniformly at random, locks it, and inserts into it. To remove an element, the processor picks two queues uniformly at
1 In practice, it is often possible to offset the cost of priority inversions by performing additional work. For instance, in Dijkstra’s single-source
shortest-paths algorithm, priority inversions can be offset by nodes being relaxed multiple times.

1

random, locks them, and removes the element of higher priority among their two top elements. Extensive testing [14,
32] has shown that this natural strategy can provide state-of-the-art throughput, and that the average number of priority
inversions is relatively low. Further variants of this strategy are used to implement general priority schedulers [29] and
relaxed concurrent queues [15].
Despite their significant practical success, randomized relaxed concurrent data structures still lack a theoretical
foundation: it is not known whether distributed strategies such as the MultiQueue can provide any guarantees in terms
of their inversion cost, or whether their performance can still be improved.
Contribution. In this paper, we take a first step towards addressing this challenge. We focus on the analysis of the
following sequential process, inspired by the MultiQueue strategy: we are given n queues, into which a large number
of consecutively labeled elements are inserted initially, uniformly at random. To remove an element, we pick two
queues at random, and remove the element of lower label on top of either queue. We are interested in the cost of
removals, defined as the rank of the removed label among labels still present in any of the queues, i.e., the “distance”
from the optimal choice at each step, which would be the top element among all queues.
Our main technical contribution is showing that this process provides surprisingly strong rank guarantees: for
any time t ≥ 0 in the execution of the process, the expected rank of an element removed at time t is O(n), while
the expected worst-case rank removed at a step is O(n log n). These bounds are asymptotically tight, and hold for
arbitrarily large t. Our analysis generalizes to a (1 + β) extension of the process, where the algorithm deletes from
the higher priority among two random queues with probability 0 < β < 1, and from a single randomly chosen queue
with probability (1 − β). It also extends to show that the process is robust to bias in the insertion distribution towards
some bins by a constant factor γ ∈ (0, 1). By contrast, we show that the strategy which always removes
from
 a
√
single randomly chosen queue diverges, in the sense that its average rank guarantee evolves as Ω tn log n , for
time t ≥ n log n. The (1 + β) strategy can be extended to an efficient implementation, which improves upon the
state-of-the-art in terms of practical performance.
Technical Overview. A tempting first approach at analysis is to reduce to classic “power of two choices” processes,
e.g. [5, 30], in which balls are always inserted into the least loaded of two randomly chosen bins. A simple reduction
between these two processes exists for the case where labels are inserted into the queues in round-robin fashion (please
see Section A for details). However, this reduction breaks if elements are inserted uniformly at random, as is the case
in real systems. Another important difference from the classic process is that elements are labelled, and so the state of
the system at a given step is highly correlated with previous steps. For instance, given a queue Q whose top element
has label `, if we wish to characterize the probability that the next label on top of Q is a specific value `0 > `, we
need to know whether the history of elements examined by the algorithm (in other queues) contains element `0 . Such
correlations make a standard step-by-step analysis extremely challenging.
We circumvent these issues by relating the original labelled process to a continuous exponential process, which
reduces correlations by replacing integer labels with real-valued labels. In this process, on every “insertion,” we insert a
new label whose value equals that of the latest inserted label in that bin (or 0 for the first insertion), plus an exponential
random variable of mean n. Intuitively, we wish to simulate the integer label insertion process with the same mean n,
while removing correlations but using continuous label values to prevent label clashes and reduce correlations. Once
this insertion process has ended, we replace each (real-valued) label with its rank among all (real-valued) labels.
We relate these two processes by the following key claim: the rank distributions for the original process and for
the exponential process are identical. More precisely, for any queue i and rank j, the event that, after insertion, the
label with rank j is located in queue i has the same probability in the original process and in the exponential process
(and all such events are independent in both processes).
Given this fact, we can couple the two processes as follows. We first couple the insertion steps such that each bin
contains the same sequence of ranks in both processes. We then couple the removal steps so that they make exactly
the same sequence of random choices. Under this coupling, the two processes will pay the same rank cost. Thus, it
will suffice to characterize the rank cost of the exponential process under our removal scheme.
This is achieved via two steps. The first is a potential argument which carefully characterizes the average value of
labels on top of the queues, and the maximum deviation from the average by a queue, at any time t > 0. This part
of the proof is very technical, and generalizes an analytic approach developed for weighted balls-into-bins processes
by Peres, Talwar and Wieder [30]. Specifically, if we let xi (t) be the difference between the label on top of queue
i at time t and the mean top label across all queues, then the total potential of the system at time t is defined as

2

Pn

[exp(αxi /n) + exp(−αxi /n)].
The key claim in the argument is showing that the expected value of this potential is bounded by O(n) for any
step t. This is done by a careful technical analysis of the expected change in potential at a step, which proves that
the potential has supermartingale-like behavior: that is, it tends to decrease in expectation once it surpasses the O(n)
threshold. It is interesting to note that neither of the two exponential factors in the definition of the potential satisfies
this bounded increase property in isolation, yet their sum can be bounded in this way.
The O(n) bound on the total potential provides a strong handle on the maximum deviation from the mean in the
exponential process. The last step of our argument builds on this characterization to show that, since label values
cannot stray too far either above or below the mean, the ranks of these values among all values on top of queues
cannot be too large. In particular, the average rank of elements on top of queues must be O(n), and the maximum rank
is O(n log n). The rank equivalence theorem implies our main claim.
The analytic framework we sketched above is quite general. It can be extended to showing that this implementation
strategy is robust to insertion bias, i.e. that it guarantees similar rank bounds even if the insertion process is biased
(within some constant γ  1) towards some of the bins. Further, it also applies to the (1 + β) variant of the process,
where each removal considers two randomly chosen queues with probability β < 1, and a single queue otherwise.
Formally, the expected cost at a step is O(n/β 2 ), and the expected maximum cost at a step is O(n log n/β).
Applications. The process considered above is sequential, and has FIFO semantics, since we are inserting labels in
strictly increasing order, and assumes that all labels are inserted initially. We relax each of these assumptions, and
discuss sufficient conditions for extending the analysis to concurrent and general priority insertions. To validate the
practicality of our results, we implemented a variant of the (1 + β) priority queue in C++. Empirical results, given
in Section 5, show that it improves upon the state-of-the-art implementation of Rihani et al. [32] by 20% in terms of
throughput, while providing similar rank guarantees. Moreover, when used in Dijkstra’s algorithm, (1 + β) priority
queue reduces running time by 10% over the original MultiQueue, and by 40% over a deterministic implementation [38]. This suggests that the decrease in rank guarantees is well compensated by improved scalability.
i=1

2

Related Work

The first instance of a distributed data structure implementation using a similar approach to the one we consider is
probably the parallel branch-and-bound framework by Karp and Zhang [20]. In their construction, each processor
is assigned a queue, and elements are inserted randomly into one of the queues. Each processor removes from its
own queue. This critically relies on the synchronicity of PRAM processors to achieve bounds on average rank and
maximum rank difference. It is easy to see that processor delays can cause the rank difference to become unbounded.
Quantitative relaxations of concurrent data structures have been previously formalized by Henzinger et al. [17], but
only for deterministic relaxations.
The MultiQueue. The strategy we consider is based on the MultiQueue data structure of Rihani et al. [32]. They
start from n sequential priority queues, each of which is protected by a lock. To insert an element, each processor
repeatedly picks a queue at random, and tries to lock it. When successful, the processor inserts the element into the
queue, and unlocks it. Otherwise, the process re-tries with a new randomly chosen lock.
To delete an element, the algorithm samples two queues uniformly, and reads the top element from both. It then
locks the queue whose top element had higher priority, removes that element, and returns it. If the algorithm failed to
obtain the lock on the chosen queue, then it restarts the whole process. (They also consider variations of this strategy,
which are essentially equivalent from the point of view of the sequential version.)
In the paper, the authors show via a basic balls-into-bins argument that, initially, before any elements are removed,
the expected rank cost is O(n), and the max cost is O(n log n) with high probability. Our argument applies to a
sequential version of the concurrent process described above. The argument is significantly more general, since it
applies to any time in the execution of the process. Variants of this approach have also been considered in other
contexts, for instance for relaxed queues [15] and priority schedulers [29]. Designing efficient concurrent priority
queues is a very active research area, see e.g. [3, 6, 36, 38] for recent examples, and [3] for a survey.
Balls-into-bins Processes. In the classic two-choice balanced allocation process, at each step, one new ball is to be
inserted into one of n bins; the ball is inserted into the less loaded among two random choices [5, 26]. In this setting,

3

it is known that the most loaded bin is at most O(log log n) above the average. The literature studying extensions
of this process is extremely vast; we direct the reader to [31] for a survey. Considerable effort has been dedicated to
understanding guarantees in the “heavily-loaded” case, where the number of insertion steps is unbounded [7, 30], and
in the “weighted” case, in which ball weights come from a probability distribution [8, 37]. In a tour-de-force, Peres,
Talwar, and Wieder [30] gave a potential argument characterizing a general form of the heavily-loaded, weighted
process on graphs. The second step in our proof, which characterizes the deviation of weights from the mean in the
exponential process, builds on their approach. Specifically, we use a similar potential function, and the parts of the
analysis are similar. However, we generalize their approach to the case of biased insert distributions, and our argument
diverges in several technical points: in particular, the potential analysis under unbalanced conditions is different. The
first and third steps of our argument are completely new, as we consider a more complex labelled allocation process.

3

Process Definition

We are given with n priority queues, labeled
Pn 1, . . . , n. To insert, we choose queue i with probability πi ∈ (0, 1), and
insert into that queue. We assume that i=1 πi = 1, and that the bias is bounded, i.e. there exists a constant γ ∈ (0, 1)
1
≤ 1 + γ. To remove, with probability 0 < β ≤ 1, we pick two queues u.a.r.,
such that, for any queue i, 1 − γ ≤ nπ
i
and remove the element of minimum label among the two choices, and with probability (1 − β) remove from a random
queue. We call such a process a (1 + β)-sequential process. When omit β when unimportant or clear from context.
At any point in the execution, we define the rank of any element to be the number of elements currently in the
system which have lower label than it (including itself), so the minimal rank is 1. Our goal is to show that the ranks of
the elements returned by the random process are small, throughout the entire execution. We will restrict our attention to
executions which never inspect empty queues, and no priority inversions on inserts are visible to the removal process.
Formally:
Definition 1. An execution of the sequential process is prefixed if except with negligible probability (i.e. probability
less than n−ω(1) ), the sequential process never inspects an empty queue in a remove, and no remove sees an insert
with lower priority than one that is inserted later in the same queue.
There are many natural types of executions which are prefixed. For instance, a common strategy in practice is to
insert a large enough “buffer” of elements initially, so as to minimize the likelihood of examining empty queues. More
formally, since in each iteration we touch a queue with probability at most n2 + O( n12 ) and only remove one element
p
at a time, by Bernstein’s inequality, any execution of length T whose first T /2 + n · ω(log n) operations are inserts,
and which contains no inserts after this time, or which only inserts larger labels after this point, will be prefixed.
For the rest of the paper, we will tacitly assume that no remove inspects any empty queue in the sequential process,
and that no priority inversions are visible to the removal process, and condition on the event that this does not happen.
By Markov’s inequality, as long as we only consider prefixed executions, then for any sequence of operations of length
poly(n), this will change the max rank or average rank of the operations by at most a subconstant factor.

4

Analysis of the Sequential Process

The goal of this section is to prove the following theorem:
Theorem 1 (see Corollary 1 and Corollary 2). Fix a bias bound γ. In any prefixed (1 + β) sequential process, for
β = Ω(γ), and for any time t > 0, the max rank of any element on top of a queue at time t is at most O( β1 (n log n +
n log β1 )), and the average rank at time t is at most O(n/β 2 ).
The Exponential Process. For the purposes of analysis, it is useful to consider an alternative process, which we
will call the exponential process, in which each bin independently generates real-valued labels by starting from 0, and
adding an exponentially-distributed random variable with parameter λi = 1/πi to its previous label. More precisely,
if wi (t) is the label present on top of bin i at time t, then the value of the next label is wi (t + 1) = wi (t) + exp(1/πi ).
Once we have enqueued all the items we wanted to enqueue, we proceed to remove items by the two-choice rule: we
4

always pick the element of minimum rank (label value) among two random choices. At any step, and for any v ∈ R,
we define rank(v) to be the number of elements currently in the system with label at most v. At each step, we pay a
cost equal to the rank of the element we just removed.
Proof Strategy. The argument proceeds in three steps. First, we show that, perhaps surprisingly, after all insertion
steps have been performed, the rank distribution of the exponential process is the same as the rank distribution of the
original process (Section 4.1). With this in place, we will perform the following coupling between the two processes:
Given an arbitrary number M of balls to be inserted into the n bins, we first generate M total weights across the
n queues in the exponential process, so that each bin has exactly the same number of elements in both processes. We
then replace each (real-valued) generated weight with its rank among all weights in the system. As we will see, for
any rank j and queue i, the probability that the ball with rank j is in bin i is exactly the same as in the simple process,
where queue i has probability of insertion πi . More precisely, if we fix an increasing sequence of ranks r1 , r2 , . . ., the
probability that bin i contains this exact sequence of ranks is the same across the two processes. Hence, we can couple
the two processes to generate the same sequence of ranks in each bin.
For the removal step, we couple the two processes such that, in every step, they generate exactly the same β values
and random choice indices. Since the ranks are the same, and the choices are the same, the two processes will remove
from exactly the same bins at each step, and will pay the same rank cost in every step.
Hence, it will suffice to bound the expected rank cost paid at a step in the exponential process. Since this is difficult
to do directly, we will first aim to characterize the concentration of the difference between the weight (value) on top of
each bin and the average weight on top of bins, via a potential argument (Section 4.2). This will show that relatively
few values can stray far from the mean. In turn, this will imply a bound on the average rank removed (Section 4.4).
In the following, we use the terms “queue” and “bin” interchangeably.

4.1

Equivalence between Rank Distributions

Let πi be the probability that a ball is inserted into bin i. This section will be dedicated to showing that the distribution
of ranks in the exponential process where bin i gets weights exponentially distributed with mean 1/πi is identical to
the distribution of labels in the original process, where the ith bin is chosen for insertion with probability πi .
Theorem 2. Let Ij←i be the event that the label with rank i is located in bin j, in either process. Let Pre [Ij←i ]
be its probability in the exponential process, and Pro [Ij←i ] be its probability in the original process. Then for both
processes Ij←i is independent from Ij 0 ←i0 for all i 6= i0 and
Pr[Ij←i ] = Pr[Ij←i ] = πj .
e

o

Proof. That Pro [Ij←i ] = πj and that Ij←i , Ij 0 ←i0 are independent for i 6= i0 in the original process both follow
immediately by the construction of the sequential process.
We now require some notation. Let `(i) be the label with rank i in the exponential process, and let b(i) be the bin
containing `(i). We will employ the following memoryless property of exponential random variables:
Fact 1. Let X ∼ Exp(r). Then, for all s, t ≥ 0, we have Pr[X > s + t] = Pr[X > s] Pr[X > t].
Fix an arbitrary i ≥ 1, and let L = `(i − 1) be the label of the (i − 1)th element. For each bin i, we isolate the
two consecutive weights between which L can be placed. More precisely, for each bin 1 ≤ j ≤ n, denote the smallest
label larger than L in bin j by `j,>L and let the largest label in Bj smaller than L be `j,<L . By construction of the
exponential process, `j,>L = `j,<L + Xj where Xj is an exponentially distributed random variable with mean 1/πj .
Furthermore, by assumption we have that `j,>L > L, so Xj > L − `j,<L . Then by memoryless-ness,
Pr[`j,>L > `j,<L + s|`j,>L > L]

=

Pr[Xj > s|Xj > (L − `j,<L )]

=

Pr[Xj > (L − `j,<L ) + (`j,>L − L)|Xj > (L − `j,<L )]

=

Pr[Xj > `j,>L − L]

Let ∆j = `j,>L − L, observing by the above that ∆j is distributed exponentially with mean πi . Furthermore, since
the Xj are independent, the ∆j are independent as well. Consider the event that `j,>L is the smallest label larger than
5

L in the system; that is `(i) = `j,>L and b(i) = j. This occurs if ∆j < ∆0j for all j 0 6= j, i.e. if ∆j is the smallest
such value among all bins. In turn, this occurs with probability
Z

∞

Z
Pr[∆j = t]Πk6=j Pr[∆k > t]dt

0

∞

=

πj exp (−tπj ) Πk6=j exp (−tπk ) dt
!
Z ∞
n
X
= πj
exp −t
πk dt = πj .
0

0

4.2

k=1

Analysis of the Exponential Process

In the previous section, we have shown that the rank distributions are the same at the end of the insert process. The
coupling described in Section 4, by which we inspect the same queues in each removal steps, implies that two processes
will produce the same cost in terms of average rank removed. Hence, we focus on bounding the rank of the labels
removed from the exponential process at each step t. Our strategy will be to first bound the deviation of the weight on
top of each queue from the average, at every step t, and then re-interpret the deviation in terms of rank cost.
Notation. From this point on, we will assume for simplicity that, at the beginning of each step, queues are always
ranked in increasing order of their top label. If pi is the probability that we pick the ith ranked bin for a removal, and
β is the two-choice probability, then it is easy to see that the (1 + β) process guarantees that
 


1
2
i−1
1
pi = (1 − β) + β
1−
− 2 .
n
n
n
n
Further, notice that, for any 1 ≤ m ≤ n, we have, ignoring the negligible O(1/n2 ) factor, that
m
X

pi '

i=1

m 
m
1+β− β .
n
n

For any bin j andP
time t, let wj (t) be the label on top of bin j at time t, and let xj (t) = wj (t)/n be the normalized
n
label. Let µ(t) = j=1 xj (t)/n be the average normalized label at time t over the bins. Let yi (t) = xi (t) − µ(t), and
let α < 1 be a parameter we will fix later. Define
Φ(t) =

n
X

exp (αyi (t)) , and Ψ(t) =

n
X

exp (−αyi (t)) .

j=1

j=1

Finally, define the potential function
Γ(t) = Φ(t) + Ψ(t).
β
Parameters and Constants. Define  = 16
. Recall that the parameter γ > 0 is such that, for every 1 ≤ i ≤ n,
1
∈
[1
−
γ,
1
+
γ].
Next,
let
c
≥
2
be
a
constant,
and δ be a parameter such that
nπi

1+δ =

1 + γ + cα (1 + γ)
1 − γ − cα (1 + γ)

2
2.

(1)

In the following, we assume that the parameters α, β, and γ satisfy the inequality
β
=  ≥ δ.
16
We assume that the insertion bias γ ≤ 1/2 is small, and hence this is satisfied by setting β = Ω(γ) and α = Θ(β).
The rest of this section is dedicated to the proof of the following claim:
6

(2)

Theorem 3. Let p~ = (p1 , p2 , . . . , pn ) be the vector of probabilities, sorted in increasing order. Let  = β/16, and
c ≥ 2 be a small constant. Let α, β, γ, δ be parameters as given above, such that  ≥ δ. Then there exists a constant
C() = poly( 1 ) such that, for any time t ≥ 0, we have E[Γ(t)] ≤ C()n.
Potential Argument Overview. The argument proceeds as follows. We will begin by bounding the change of each
potential function Ψ and Φ, at each queue in a step (Lemmas 1 and 6). We then use these bounds to show that, if not
too many queues have weights above or below the mean (yn/4 ≤ 0 and y3n/4 ≥ 0), then Φ and Ψ respectively decrease
in expectation (Lemmas 7 and 8). Unfortunately, this does not necessarily hold in general configurations. However,
we are able to show the following claim: if the configuration is unbalanced (e.g. yn/4 > 0 ) and Φ does not decrease
in expectation at a step, then either the symmetric potential Ψ is large, and will decrease on average, or the global
potential function Γ must be in O(n) (Lemma 9). We will prove a similar claim for Ψ. Putting everything together,
we get that the global potential function Γ always decreases in expectation once it exceeds the O(n) threshold, which
implies Theorem 3.
Potential Change at Each Step. We begin by analyzing the expected change in potential for each queue from step to
step. We first look at the change in the weight vector ~y = (y1 , y2 , . . . , yn ). (Recall that we always re-order the queues
in increasing order of weight at the beginning of each step.) Below, let κj be the cost increase if the bin of rank j is
chosen, which is an exponential random variable with mean 1/πj . We have that, for every rank i,
(
yi (t) + κi (1 − 1/n) , with probability pi ; i.e., the queue of rank i is picked, and
yi (t + 1) =
κ
yi (t) − nj , if some other bin j 6= i is chosen.
The Change in Φ at a Step. We prove the following bound on the expected increase in Φ at a step.
Lemma 1. For any bin rank i,
E [∆Φ | y(t)] ≤



n
X
1
α̂ (1 + δ)pi −
exp (αyi (t)) .
n
i=1

Proof. Let Φi (t) = exp (αyi (t)). We have two cases. If the bin is chosen for removal, then the change is:


1
α
∆Φi := Φi (t + 1) − Φi (t) = exp α
n (yi (t) + κi 1 − n ) − exp n yi (t)



1
=
exp α
exp α
−1 .
n yi (t)
n κi 1 − n
Taking expectations with respect to the random choices made on insertion, that is, the value of κj , we have




1
α
(a)
=
1−
E exp κi
n
n
i

πi −(

πi
α
1
n (1− n )

)

=

(b)

1
1− παn
i

(

1
1− n

)

≤ 1+

α
πi n

1−

1
n



+c



α
πi n

1−

1
n

 2

,

for some constant c > 1. Step (a) follows from the observation that the expectation we wish to compute is the moment1
generating function of the exponential distribution at α
n (1 − n ), while (b) follows from the Taylor expansion. (We
slightly abused notation in step (a) by denoting with πi the insert probability for the ith ranked queue, according to the
ranking in this step.)
The second step if if some other bin j 6= i is chosen for removal, then the change is:




ακ 
1
α
α
exp − n2j − 1 .
∆Φi = exp α
n (yi (t) − κj n ) − exp n yi (t) = exp n yi (t)
Again taking expectations with respect to the random choices made on insertion, i.e. the value of κj , we have
h

α i
=
E exp −κj 2
n
i

πj
πj + nα2

=

1

1+ π αn2
j

≤1−

α
π j n2

7

+



α
π j n2

2

− ... ≤ 1 −

α
πj n2

+



α
π j n2

2

.

Therefore, we have that

2 !




2 !
X
α
1
α
1
α
+
1−
+c
1−
pj − 1
pi +
1−
n
πi n
n
πj n2
πj n2
j6=i

2 !

2 !
n
X
α
α
α
α
−c
+c
pj
pi −
πi n
πi n
πj n 2
πj n 2
j=1

α
1+
πi n

E [∆Φi ] /Φi (t) ≤
≤

≤



2

1 + γ + cα (1 + γ)



n

αpi −


α X
2
1 − γ − cα (1 + γ) pj .
n j=1

If we denote for convenience
2


1 + γ + cα (1 + γ)
2
α̂ = α 1 − γ − cα (1 + γ) , and recall that δ :=
2 − 1,
1 − γ − cα (1 + γ)

then we can rewrite this as


n
X
1
α̂ pi (1 + δ) −
Φi (t).
E [∆Φ | y(t)] ≤
n
i=1

The Change in Ψ. Using a symmetric argument, we can prove the following about the expected change in Ψ.
Lemma 6.
E [∆Ψ | y(t)] ≤



n
X
1
α̂ (1 + δ) − pi exp (−αyi (t)) .
n
i=1

Bounds under Balanced Conditions. Let us briefly stop to examine the bounds in the above Lemmas. The terms
pi (1 + δ) − n1 are decreasing in i, and in fact become negative as i increases. (The exact index where this occurs
is controlled by β and δ.) The exp (αyi (t)) terms are increasing in i. Bins whose weight is below the mean (i.e.,
yi (t) ≤ 0) have a negligible effect on Φ, since each of their contributions is at most 1. At the same time, notice that
the contribution of bins of large index i will be negative. Hence, we can show that, if at least n/4 bins have weights
below average, then the value of Φ tends to decrease on average.
Lemma 7. If yn/4 ≤ 0, then we have that

E [Φ(t + 1) | y(t)] ≤

1−

α̂
3n


Φ(t) + 1.

A similar claim holds for Ψ, under the condition that there are at least n/4 bins with weight larger than average.
Lemma 8. If y3n/4 ≥ 0, then we have that
E [Ψ(t + 1) | y(t)] ≤

1−

α̂
3n



Ψ + 1.

Bounds under Unbalanced Conditions. We now analyze unbalanced configurations, where there are either many
bins whose weights are above average (e.g., yn/4 > 0), or below average (y3n/4 < 0). The rationale we used to bound
each potential function independently no longer applies. In particular, as shown in [30], we can have unbalanced
settings where for example Φ does not decrease in expectation. However, we can show that, one of two things must
hold: either the other potential Ψ is larger and does decrease in expectation, or the global potential Γ is in O(n).
α̂
Φ(t). Then either Φ < 4 Ψ or Γ = O(n).
Lemma 9. Given  as above, assume that yn/4 (t) > 0, and E[∆Φ] ≥ − 3n

8

Proof. Fix λ = 2/3 − 1/54 for the rest of the proof. We can split the inequality in Lemma 1 as follows:




λn
n
X
X
1
1
exp (αyi (t)) +
exp (αyi (t)) .
α̂ (1 + δ)pi −
α̂ (1 + δ)pi −
E [∆Φ | y(t)] ≤
n
n
i=1

(3)

i=λn+1

We bound each term separately. Since the probability terms are non-increasing and the exponential terms are nondecreasing, the first term is maximized when all pi terms are equal. Since these probabilities are at most 1, we have




λn
X
α̂
1
1
exp (αyi (t)) ≤
(1 + δ) − 1 Φ≤λn .
α̂ (1 + δ)pi −
n
n
λ
i=1

(4)

The second term is maximized by noticing that the pi factors are non-increasing, and are thus dominated by their value
at λn. Noticing that we carefully picked λ such that
pλn ≤

4
1
− ,
n
n

we obtain, using the assumed inequality δ ≤ , that


n
X
Φ>λn
3α̂
1
exp (αyi (t)) ≤ α̂ (δ − 4)
≤−
Φ>λn .
α̂ (1 + δ)pi −
n
n
n

(5)

i=λn+1

α̂
By the case assumption, we know that E [∆Φ | y(t)] ≥ − 3n
Φ(t). Combining the bounds (18), (19), and (20), this
yields:


α̂
3α̂
α̂
1
Φ>λn ≥ − Φ(t).
(1 + δ) − 1 Φ≤λn −
n
λ
n
3n

Substituting Φ>λn = Φ − Φ≤λn yields:

(3 − /3) Φ ≤
For simplicity, we fix C() =

1
(1+δ) λ
−1+3
3−/3

=O

(1 + δ)
1





1
− 1 + 3 Φ≤λn .
λ

, to obtain

Φ ≤ C()Φ≤λn .
Let B =

P

yi >0

(6)

P
yi . Since we are normalizing by the mean, it also holds that B = yi <0 (−yi ). Notice that


yi incr.
yi incr.
αB
.
Φ≤λn ≤ λn exp (αyλn ) ≤ λn exp
(1 − λ)n

(7)

We put inequalities (21) and (22) together and get
Φ(t) ≤ λnC() exp



αB
(1−λ)n



,

(8)

Let us now lower bound the value of Ψ under these conditions. Since yn/4 > 0, all the costs below average must be in
the first quarter of y. We can apply Jensen’s inequality to the first n/4 terms of Ψ to get that
Pn/4 !
n/4
X
yi
n
Ψ≥
exp (−αyi ) ≥ exp −α i=1
.
4
n/4
i=1
Pn/4
We now split the sum i=1 yi into its positive part and its negative part. We know that the negative part is summing
up to exactly −B, as it contains all the negative yi ’s and the total sum is 0. The positive part can be of size at most
9

B/4, since it is maximized when there are exactly n − 1 positive costs and they are all equal. Hence the sum of the
first n/4 elements is at least −3B/4, which implies that the following bound holds:




n
−3B/4
n
3B
Ψ ≥ exp −α
≥ exp α
.
(9)
4
n/4
4
n
If Φ < 4 Ψ, then there is nothing to prove. Otherwise, if Φ ≥ 4 Ψ, we get from (24) and (23) that




n
3B

αB
,
exp α
≤ Ψ ≤ Φ(t) ≤ λnC() exp (1−λ)n
44
n
4
Therefore, we get that:


B
exp α
n
Using the mundane fact that 3 −

1
1−λ



1
3−
1−λ



4λ
≤
C() = O




1
2


.

= 3/19, we get that

 

1
αB
≤ O 14 .
exp
n


To conclude, notice that (25) implies we can upper bound Γ in this case as:


 4+
4+
αB
1
Γ = Φ + Ψ ≤ 4+
Φ
≤
λnC()
exp


(1−λ)n ≤ O 14/(1−λ)
 C()λn = O(poly

(10)

1




n).

We can prove a symmetric claim for Ψ by a slightly different argument.
α̂
Lemma 10. Given  as above, assume that y 3n
< 0, and that E[∆Ψ] ≥ − 3n
Ψ. Then either Ψ < 4 Φ or Γ = O(n).
4

Endgame. We now finally have the required machinery to prove that Γ satisfies a supermartingale property:
Lemma 2. There exists a constant  such that


 

1
α̂
Γ(t) + C, where C is a constant in O poly
.
E[Γ(t + 1)|y(t)] ≤ 1 −
4n

Proof. Case 1: If yn/4 ≤ 0 and y3n/4 ≥ 0, then the property follows by putting together Lemmas 7 and 8.
Case 2: If y3n/4 ≥ yn/4 ≥ 0. This means that the weight vector is unbalanced, in particular that there are few bins
of low cost, and many bins of high cost. However, we can show that the expected decrease in Ψ can compensate
this decrease, and the inequality still holds. Notice that Lemmas 1 and 6 imply that E[∆Φ] ≤ α̂δ
n Φ(t) and E[∆Ψ] ≤
α̂δ
Ψ(t),
respectively.
n
α̂
If E[∆Φ] ≤ − 4n
Φ(t), then the claim simply follows by putting this bound together with Lemma 8. Otherwise, if
α̂
E[∆Φ] ≥ − 4n
Φ(t), we obtain from Lemma 9 that either Φ < 4 Ψ or Γ = O(n). In the first sub-case, we have that
α̂δ
n Φ(t)

E[∆Γ] = E[∆Φ] + E[∆Ψ] ≤
≤

α̂
− 3n
1−

3δ
4



+1−

α̂
3n Ψ(t)

α̂
Ψ(t) + 1 ≤ − 3n

α̂
α̂
≤ − 3n
Ψ(t) + 1 + δ
4n Ψ(t)
−1

α̂
1 + 4
1 − 3δ
4 Γ(t) ≤ − 4n Γ(t), as claimed.

In the second sub-case, we know that Γ ≤ Cn, for some constant C. Hence, we can get that
(a)

α̂δ Γ=O(n)
Γ ≤ 2C α̂,
n
where in step (a) we used the upper bounds in Lemmas 1 and 6, respectively. On the other hand,


α̂
α̂
α̂
C−
Γ(t) ≥ C −
Cn = C 1 −
≥ 3C α̂ ≥ E[∆Γ].
4n
4n
4
E[∆Γ] = E[∆Φ] + E[∆Ψ] ≤

Case 3: If yn/4 ≤ y3n/4 < 0. This case is symmetric to the one above.
10

The intuition behind the above bound is that Γ will always tend to decrease once it surpasses the Θ(n) threshold. This
implies a bound on the expected value of Γ, which completes the proof of Theorem 3.
Lemma 3. For any t ≥ 0, E[Γ(t)] ≤

4C
α̂ n.

Proof. By induction. This holds for t = 0 by a direct computation: see Lemma 2 for the argument. Then, we have





α̂
4C
α̂
4C
E[Γ(t + 1)] = E[E[Γ(t + 1)|Γ(t)]] ≤ E 1 −
Γ(t) + C ≤
n 1−
+C ≤
n.
4n
α̂
4n
α̂

4.3

Guarantees on Max Rank

We can use the characterization of the exponential process to prove the following:
Lemma 4. If wmax (t) is the maximum bin weight at time t and wmin (t) is the minimum, then


1
[w
(t)
−
w
(t)]
=
O
n(log
n
+
log
C)
.
E max
min
α

(11)

Proof. Let xmax (t) = wmax (t)/n and xmin (t) = wmin (t)/n. By definition, we have exp(α(xmax (t) − µ(t))) ≤ Γ(t)
and exp(α(µ(t) − xmin (t))) ≤ Γ(t). Therefore α(xmax (t) − xmin (t)) ≤ 2 log Γ(t). Thus, we have
(a)

(b)

E[α(xmax (t) − xmin (t))] ≤ 2 E[log Γ(t)] ≤ 2 log(E[Γ(t)]) = O(log n + log C) ,
where (a) follows from Jensen’s inequality and (b) follows from Theorem 3. Simplifying yields the desired claim.
In Appendix E we show that this implies the following theorem:
Theorem 4. For all t ≥ 0, we have E[max rank(t)] = O

1
α n(log n


+ log C) .

By plugging in constants as in (1) and (2), we get:
Corollary 1. For all t ≥ 0, and any β = Ω(γ), we have E[max rank(t)] = O

4.4



1
β n(log n


+ log 1/β) .

Guarantees on Average Rank

We now focus on at the rank cost paid in a step by the algorithm. Let A = log C/α. For real values s ≥ 0, we “stripe”
the bins according to their top value, denoting by b>s (t) the number of bins with wj (t) ≥ (s + A)n + µ at time t,
and let b<−s (t) be the number of bins with wj (t) ≤ µ − (s + A)n at time t. For any bin j and interval I, we also let
`j,I (t) be the number of elements in j at time t with label in I. Finally, let pj,µ denote the PDF of wj (t) given µt .
We discuss the proof strategy at a high level here, deferring the full proofs to Appendix F. First, we use the bounds
on Γ to obtain the following bounds on the quantities defined previously:
Lemma 5. For any time t, we have that E[b>s ] ≤ n exp(−αs) and that E[b<−s ] ≤ n exp(−αs).
Pn
Proof. Recall that Φ(t) = i=1 exp (α (xi (t) − µ)) and that E [Φ(t)] ≤ Cn. By linearity of expectation, we have
E[Φ(t)] ≥ E[b>s exp(α(s + A))] = C exp(αs) · E[b>s ],
which implies the claim. The converse claim follows from the bound on Ψ(t).
This lemma gives us strong bounds on the tail behavior of the wj . We show that this implies a bound on the average
rank. We will need the following technical result.
Lemma 11. For any interval I = [a, b] which may depend on µ, we have E[rank(b) − rank(a)|µ] ≤ n(b − a + 1).
11

We then show a bound on the rank of µ:

Lemma 12. For all t, we have E[rank(µ(t))] ≤ O (A + 1/α2 )n .
The proof of this lemma, deferred to Appendix F, works as follows. We divide up the interval (−∞, µ] into
infinitely many intervals of constant length. We will count the number of wj (t) within each interval separately. Within
each such interval, we can give a crude upper bound the number of weights that could have ever been in that interval
at any point in the execution. We then use Lemma 5 to show that at the current time in the execution, the number of
bins with elements in each interval decays exponentially as we take intervals which are further and further away from
µ. Summing these values up gives the desired bound. Finally, this implies:


 Pn
Theorem 5. For all t, we have E n1 i=1 rankj (t) = O A + α12 n.
Proof. By Lemma 12 and Lemma 11, we have that

2
E[rankj (t)|wj (t) ≤ µ(t) + An] ≤ O (A + 1/α )n + (A + 1)n

= O (A + 1/α2 )n .
Thus, we have

" n
#
X
rankj (t) = E 
E
i=1


X

X

E[rankj (t)|µ] +

wj (t)≤µ+An


X

= E

n
X

E[rankj (t)|µ] +

(a)

1
A+ 2
α



1
A+ 2
α



≤ O


(b)

≤O

=O

1
α2



≤O
(c)

≤O

A+


+

n
X

n2


+

n
X

n2


+

n2

+n

E[`j,(µ,wj (t)) |µ, wj (t)]

wj (t)>µ+An




X

E

(wj (t) − µ + 1)

wj (t)>µ+An

∞
n X
X




X

E

j=1 k=0

1
A+ 2
α

E[rankj (µ + An) + `j,(µ,wj (t)) |µ, wj (t)]



j=1

1
A+ 2
α



n2



j=1




X

j=1 wj (t)>µ+An

wj (t)≤µ+An



E[rankj (t)|µ]

wj (t)>µ+An

∞
X


E


X

(wj (t) − µ + 1)

wj (t)∈[µ+(A+k)n,µ+(A+k+1)n]

(A + k + 2)n E [b>k ]

k=0


n

2




+O


1 2
n .
α2

where (a) follows by Lemma 12, (b) follows by Lemma 11, and (c) follows from Lemma 5. Thus
" n
#


1X
1
rankj (t) = O A + 2 n
E
n i=1
α
as claimed.
We now show how these imply bounds for our removal processes. The actual rank choice at time t is always better
than a uniform choice in expectation, since it uses power of two choices. If we consider an (1 + β) process, where we
only do two choices with probability β = Ω(γ), we obtain the following, by setting parameters as in (1) and (2) :
Corollary 2. For all t, if we let β = Ω(γ), and we let r(t) denote the rank of the removed element at time t, then

 
 
log C
1
n
+ 2 n =O
.
E[r(t)] = O
α
α
β2
12

Figure 1: Throughput comparison for the (1 + β) priority
queue with β = 0.5 and 0.75, versus the original
MultiQueues, the Linden-Jonsson implementation, and
kLSM. Higher is better.

5

Figure 2: Mean rank returned (log scale) for the (1 + β)
priority queue, for various values of β on 8 queues and 8
threads. Lower is better.

Experimental Results

Setup and Methodology. We implemented a (1+β) priority queue based on the MultiQueue implementation from the
priority queue benchmark framework of [14], and benchmarked it against the original MultiQueue (β = 1), the LindenJonsson [24] skiplist-based implementation, and the kLSM deterministic-relaxed data structure [38], with a relaxation
factor of 256, which has been found to perform best. The MultiQueue uses efficient sequential priority queues from
the boost library. Tests were performed on a recent Intel(R) Xeon(R) CPU E7-8890 (Haswell architecture), with 18
hardware threads, each running at 2.5GHz. The tests for mean rank returned use coherent timestamps to record the
times when elements are returned at each thread. We use these in a post-processing step to count rank inversions.
This methodology might not be 100% accurate, since the use of timestamps might change the schedule; however, we
believe results should be reasonably close to the true values.
For the throughput experiments, we consider executions consisting of alternating insert and deleteMin operations,
for 10 seconds. Experiment outputs are averaged over 10 trials. Removals on empty queues do not count towards
throughput. Since we are interested in the regime where queues are never empty, we insert 10 million elements initially.
Threads are pinned to cores, and memory allocation is affinitized. The single-source shortest paths benchmark is a
version of Dijkstra’s algorithm, running on a weighted, directed California road network graph.
Results. Figure 1 illustrates the throughput differential between the various implementations, As previously stated,
the MultiQueue variants are superior to other implementations (except at very low thread counts). Of note, the variants
with β < 1 improve on the standard implementation by up to 20%. Since throughput figures are not conclusive in
isolation, we also benchmarked the average rank cost in Figure 2. (The y axis is logarithmic.) Note that the increase in
average cost due to the further β relaxation is relatively limited. Results are conformant with our analysis for β ≥ 0.5.
The apparent inflection point at around β = 0.5 could be explained by the  ≥ δ bias assumptions breaking down after
this point, or by non-trivial correlations in the actual execution which mean that our analysis no longer applies.
Finally, Figure 3 gives a running times for a single-source shortest path benchmark, using a parallel version of
Dijkstra’s algorithm. We note that the relaxed versions with β < 1 can be superior in terms of running time to the
version with β = 1, by up to 10%. The version with β = 0 (not shown) is the fastest at low thread counts, but then
loses performance at thread counts ≥ 8, probably because of excessive relaxation.

13

Figure 3: Running times for single-source shortest path benchmark, using various versions of the priority queue, and kLSM.
Lower is better.

6

Discussion and Future Work

We have provided tight rank guarantees for a practically-inspired randomized priority scheduling process. Moreover,
we showed that this strategy is robust in terms of its bias and randomness requirements. Intuitively, our results show
that, given biased random insertions into the queues, the preference towards lower ranks provided by the two-choice
process is enough to give strong linear bounds on the average rank removed. We extended our analysis to a practical
algorithm which improves on the state-of-the-art MultiQueues in Section 5.
Tightness. The bounds we provide for the two-choice process are asymptotically tight. To see that the O(n) bound
is tight, it suffices to notice that, even in a best-case scenario, the rank of the kth least expensive queue is at least k.
Hence, the process has to have expected rank cost Ω(n). The tightness argument for Θ(n log n) expected worst-case
cost is more complex. In particular, it is known [30, Example 2] that the gap between the most loaded and average bin
load in a weighted balls-into-bins process with weights coming from an exponential distribution of mean 1 is Θ(log n)
in expectation. That is, there exists a queue j from which we have removed Θ(log n) fewer times than the average.
We can extend the argument in Section 4.4 to prove that there exist Θ(n) queues which have Θ(log n) elements of
higher label than the top element of queue j. This implies that the rank cost of queue j is Θ(n log n), as claimed. We
conjecture that the dependency in β for the expected rank bound on the (1 + β) process can be improved to linear.
Relation to Concurrent Processes. An important question is whether we can show that the practical concurrent
implementations provide similar bounds. This claim holds if we assume that, in the concurrent implementation, the
steps comparing the two top elements of the randomly chosen queues and removing the better top element are all
performed atomically, e.g. through hardware transactional memory. In this case, we can show that the probability
distributions of ranks returned by the concurrent and sequential processes are identical, and hence our guarantees
apply. We formalize the required property, called distributional linearizability, in Appendix C.
This property does not appear to hold in general for fine-grained lock-based or lock-free implementations. Appendix C provides a detailed discussion of the difficulties and limitations of extending this approach to a concurrent
setting. In particular, due to complex correlations implied by concurrent execution, our bounds might not hold for
some locking strategies for subtle reasons, and it appears highly non-trivial to rigorously extend them to any particular
fine-grained strategy.
In future work, we plan to examine whether exist relaxations of distributional linearizability satisfied by real
implementations, which would allow our bounds to be extended to concurrent implementations without additional
assumptions. The results in Section 5 suggest that existing implementations do satisfy strong rank guarantees.
Future Work. An extremely intriguing question regards the impact of using such relaxed priority queue structures in
the context of existing parallel algorithms, e.g. for shortest-paths computation. In particular, it would be interesting to
14

bound the amount of extra work caused by relaxation versus the benefits of parallelism.
Another interesting question in terms of future work is whether our results can also be extended to processes on
graphs. More precisely, imagine we are given a strongly connected, undirected graph with n vertices. Insertions of
increasing integer labels are performed at uniformly random nodes. In every removal step, we pick a random edge,
remove the higher priority label among its endpoints, and pay the rank of this label among all labels. It is not hard to
see that, for graph families with good expansion, our analytic framework can be extended to this process as well. We
plan to explore tight bounds for such graphical processes in future work.

References
[1] Yehuda Afek, Haim Kaplan, Boris Korenfeld, Adam Morrison, and Robert E. Tarjan. Cbtree: A practical concurrent self-adjusting search tree. In Proceedings of the 26th International Conference on Distributed Computing,
DISC’12, pages 1–15, Berlin, Heidelberg, 2012. Springer-Verlag.
[2] Dan Alistarh, James Aspnes, Keren Censor-Hillel, Seth Gilbert, and Rachid Guerraoui. Tight bounds for asynchronous renaming. J. ACM, 61(3):18:1–18:51, June 2014.
[3] Dan Alistarh, Justin Kopinsky, Jerry Li, and Nir Shavit. The spraylist: A scalable relaxed priority queue. In 20th
ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2015, San Francisco,
CA, USA, 2015. ACM.
[4] Hillel Avni, Nir Shavit, and Adi Suissa. Leaplist: Lessons learned in designing tm-supported range queries. In
Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, PODC ’13, pages 299–308,
New York, NY, USA, 2013. ACM.
[5] Yossi Azar, Andrei Z Broder, Anna R Karlin, and Eli Upfal. Balanced allocations. SIAM journal on computing,
29(1):180–200, 1999.
[6] Dmitry Basin, Rui Fan, Idit Keidar, Ofer Kiselov, and Dmitri Perelman. CafÉ: Scalable task pools with adjustable fairness and contention. In Proceedings of the 25th International Conference on Distributed Computing,
DISC’11, pages 475–488, Berlin, Heidelberg, 2011. Springer-Verlag.
[7] Petra Berenbrink, Artur Czumaj, Angelika Steger, and Berthold Vöcking. Balanced allocations: The heavily
loaded case. In Proceedings of the Thirty-second Annual ACM Symposium on Theory of Computing, STOC ’00,
pages 745–754, New York, NY, USA, 2000. ACM.
[8] Petra Berenbrink, Tom Friedetzky, Zengjian Hu, and Russell Martin. On weighted balls-into-bins games. Theor.
Comput. Sci., 409(3):511–520, December 2008.
[9] Trevor Brown, Faith Ellen, and Eric Ruppert. A general technique for non-blocking trees. SIGPLAN Not.,
49(8):329–342, February 2014.
[10] Faith Ellen, Danny Hendler, and Nir Shavit. On the inherent sequentiality of concurrent objects. SIAM J.
Comput., 41(3):519–536, 2012.
[11] Panagiota Fatourou and Nikolaos D. Kallimanis. Revisiting the combining synchronization technique. SIGPLAN
Not., 47(8):257–266, February 2012.
[12] Panagiota Fatourou and Nikolaos D. Kallimanis. Highly-efficient wait-free synchronization. Theory Comput.
Syst., 55(3):475–520, 2014.
[13] Mikhail Fomitchev and Eric Ruppert. Lock-free linked lists and skip lists. In Proceedings of the 23rd annual
ACM symposium on Principles of Distributed Computing (PODC’ 04), pages 50–59, New York, NY, USA, 2004.
ACM Press.

15

[14] Jakob Gruber, Jesper Larsson Träff, and Martin Wimmer. Brief announcement: Benchmarking concurrent priority queues. In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA
’16, pages 361–362, New York, NY, USA, 2016. ACM.
[15] Andreas Haas, Michael Lippautz, Thomas A. Henzinger, Hannes Payer, Ana Sokolova, Christoph M. Kirsch, and
Ali Sezgin. Distributed queues in shared memory: multicore performance and scalability through quantitative
relaxation. In Computing Frontiers Conference, CF’13, Ischia, Italy, May 14 - 16, 2013, pages 17:1–17:9, 2013.
[16] Tim L. Harris. A pragmatic implementation of non-blocking linked-lists. In Proceedings of the International
Conference on Distributed Computing (DISC), pages 300–314, 2001.
[17] Thomas A. Henzinger, Christoph M. Kirsch, Hannes Payer, Ali Sezgin, and Ana Sokolova. Quantitative relaxation of concurrent data structures. SIGPLAN Not., 48(1):317–328, January 2013.
[18] Maurice Herlihy, Yossi Lev, Victor Luchangco, and Nir Shavit. A simple optimistic skiplist algorithm.
In Proceedings of the 14th international conference on Structural information and communication complexity, SIROCCO’07, pages 124–138, Berlin, Heidelberg, 2007. Springer-Verlag. http://dl.acm.org/
citation.cfm?id=1760631.1760646.
[19] Maurice Herlihy, Nir Shavit, and Moran Tzafrir. Hopscotch hashing. In Proceedings of the 22nd international
symposium on Distributed Computing, DISC ’08, pages 350–364, Berlin, Heidelberg, 2008. Springer-Verlag.
http://dl.acm.org/citation.cfm?id=1432316.
[20] R. M. Karp and Y. Zhang. Parallel algorithms for backtrack search and branch-and-bound. Journal of the ACM,
40(3):765–789, 1993.
[21] Doug Lea, 2007.
http://java.sun.com/javase/6/docs/api/java/util/concurrent/
ConcurrentSkipListMap.html.
[22] Doug Lea, 2007. http://g.oswego.edu/dl/jsr166/dist/docs/java/util/concurrent/
ConcurrentHashMap.html.
[23] Justin J Levandoski, David B Lomet, and Sudipta Sengupta. The bw-tree: A b-tree for new hardware platforms.
In Data Engineering (ICDE), 2013 IEEE 29th International Conference on, pages 302–313. IEEE, 2013.
[24] Jonatan Lindén and Bengt Jonsson. A skiplist-based concurrent priority queue with minimal memory contention.
In International Conference On Principles Of Distributed Systems, pages 206–220. Springer, 2013.
[25] Maged M Michael. High performance dynamic lock-free hash tables and list-based sets. In Proceedings of the
fourteenth annual ACM symposium on Parallel algorithms and architectures, pages 73–82. ACM, 2002.
[26] Michael Mitzenmacher. The power of two choices in randomized load balancing. IEEE Transactions on Parallel
and Distributed Systems, 12(10):1094–1104, 2001.
[27] Adam Morrison. Scaling synchronization in multicore programs. Commun. ACM, 59(11):44–51, October 2016.
[28] Adam Morrison and Yehuda Afek. Fast concurrent queues for x86 processors. SIGPLAN Not., 48(8):103–112,
February 2013.
[29] Donald Nguyen, Andrew Lenharth, and Keshav Pingali. A lightweight infrastructure for graph analytics. In
Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, SOSP ’13, pages 456–
471, New York, NY, USA, 2013. ACM.
[30] Yuval Peres, Kunal Talwar, and Udi Wieder. Graphical balanced allocations and the 1 + beta-choice process.
Random Struct. Algorithms, 47(4):760–775, December 2015.
[31] Andrea W Richa, M Mitzenmacher, and R Sitaraman. The power of two random choices: A survey of techniques
and results. Combinatorial Optimization, 9:255–304, 2001.
16

[32] Hamza Rihani, Peter Sanders, and Roman Dementiev. Brief announcement: Multiqueues: Simple relaxed concurrent priority queues. In Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’15, pages 80–82, New York, NY, USA, 2015. ACM.
[33] P. Sanders. Randomized priority queues for fast parallel access. Journal Parallel and Distributed Computing,
Special Issue on Parallel and Distributed Data Structures, 49:86–97, 1998.
[34] Ori Shalev and Nir Shavit. Split-ordered lists: Lock-free extensible hash tables. J. ACM, 53:379–405, May 2006.
http://doi.acm.org/10.1145/1147954.1147958.
[35] Nir Shavit. Data structures in the multicore age. Commun. ACM, 54(3):76–84, 2011.
[36] Nir Shavit and Itay Lotan. Skiplist-based concurrent priority queues. In Parallel and Distributed Processing
Symposium, 2000. IPDPS 2000. Proceedings. 14th International, pages 263–268. IEEE, 2000.
[37] Kunal Talwar and Udi Wieder. Balanced allocations: The weighted case. In Proceedings of the Thirty-ninth
Annual ACM Symposium on Theory of Computing, STOC ’07, pages 256–265, New York, NY, USA, 2007.
ACM.
[38] Martin Wimmer, Jakob Gruber, Jesper Larsson Träff, and Philippas Tsigas. The lock-free k-lsm relaxed priority
queue. In ACM SIGPLAN Notices, volume 50, pages 277–278. ACM, 2015.

Appendix
The Appendix proceeds as follows. We give a reduction between classic power-of-two-choices processes and our
sequential process, under round-robin insertions, in Section A. We prove that the single random choice process diverges
in terms of rank cost in Section B. We cover the definition of distributional linearizability and relation to concurrent
processes in Section C. We give complete proofs in Sections D, E, and F.

A

Reduction to Two-Choices Process for Round-Robin Insertions

Process Description. For clarity, we re-define the process for round-robin insertions: we are given n queues, into
which consecutively labeled elements are inserted in round-robin order: at the tth insertion step, we insert the element
with label t into bin t (mod n). To remove an element, we pick two queues at random, and remove the element of
lower label on top of either queue. We again measure the cost of a removal as the rank of the removed label among
labels still present in any of the queues.
Reduction. We will associate a “virtual” bin Vi with each queue i. Whenever an element is removed from the queue
i, it gets immediately placed into the corresponding virtual bin. Notice that in every step we are removing the element
of minimum label, which, by round-robin insertion, corresponds to the queue having been removed from less times
than the other choice. Alternatively, we are inserting the removed element into the less loaded virtual bin, out of two
random choices (implicitly breaking ties by bin ID). This is the classic definition of the two-choices process [5], which
has been analyzed for the long-lived case in e.g. [7]. One can prove bounds on the rank of elements removed using the
existing analyses of this process, e.g. [7, 30].
The Reduction Breaks for Random Insertions. Notice that the critical step in the above argument is the fact that,
out of two random choices i and j, the less loaded virtual bin corresponds to the queue which has lower label on
top. This does not hold in the random insertion case; for instance, it is possible for a bin to get two elements with
consecutive labels, which breaks the above property. Upon closer examination, we can observe that in the random
insertion case, the correlation between the event that queue i has lower label than queue j and the event that queue i
has been removed from less times than queue j exists, but is too weak to allow a direct reduction.

17

B

The Single Choice Process Diverges

In this section, we prove the following claim.
Theorem 6. The expected maximum rank
√ guarantee of the process which inserts and removes from uniform random
queues in each time step t evolves as Ω( tn log n), for t = Ω(n log n).
Proof. First, notice that we can apply the reduction in Section A to obtain that the maximum number of elements
removed from a queue is the same as the maximum load of a bin in the classic long-lived random-removal process.
(This holds irrespective of the insertion process, since
 we areqperforming
 uniform random removals.) The maximum
load of a bin in the classic process is known to be Θ t/n +

t
n

log n , with high probability, for t > n log n [30].

Let the queue with the most removals up to time t be Q. For any other queue Qi with less removals, let `(Qi )
be the difference between the number of elements removed from Q and the number of elements removed from Qi .
Notice that the expected number of elements removed from a queue up to t is t/n. Hence, it is easy to prove that, with
probability at least 1/2, there
t/n elements removed. Hence, for any
q are at least n/4 queues whichPhave had at most
√
t
such queue Qi , `(Qi ) ≥ n log n. Hence, in expectation, i `(Qi ) = Ω( tn log n).
We say that an element is light if its
Plabel is smaller than the label of the the top element of Q. By symmetry,
we know that each element counted
in
i `(Qi ) is light with probability ≥ 1/2. Putting everything together, we get
√
that, in expectation, we have Ω( tn log n)
√ elements which are light, i.e. of smaller label than the top label of Q. This
implies that the expected rank of Q is Ω( tn log n), as claimed.

C

Relationship to Concurrent Processes

On first glance, it might seem that a simple lock-based strategy should be linearizable to the sequential process we
define in Section 3. For example, we could lock both queues that are to be examined (locking in order of their index
to avoid deadlock and restarting the operation on failure) and declare the linearization point to be the point at which
the second lock is grabbed. While this does linearize to some relaxed sequential process, it turns out that our upper
bounds fail to hold for subtle reasons when concurrency is introduced.
Consider the extreme execution in which process 0 grabs the locks on some two queues, say Qi , Qj , and then hangs
for a long time. Meanwhile, all the other processes complete many operations while process 0 holds these locks, and
all operations will have to retry if they try to grab locks on Qi or Qj . In this case, many delete operations will be
performed, none of which can delete from Qi or Qj . Such an execution could produce arbitrarily bad rank errors. We
can formalize the property we would like a correct concurrent strategy to have as distributional linearizability:
Definition 2 (Distributional Linearizability). A randomized data structure Q is distributionally linearizable to a sequential data structure S if for any parallel asynchronous execution, there exists a linearization of the operations of
Q to operations of S so that the outputs of each operation of Q are distributionally equivalent to those S.
The simple locking strategy fails to be distributionally linearizable due to, e.g., the counter-example execution
above. We would like to ask if there is a distributionally linearizable strategy, yet there appears to be an inherent
limitation. Consider three processes i, j, k performing DELETE M IN operations in lock-step. No matter what strategy
is used, if some two processes, say i, j, try to delete from the same queue Q, at least one, say j, will necessarily be
delayed. As a result i and k will finish their operations while j takes longer, causing i and k to be linearized before
j (this can be forced by e.g. an insertion to Q while j is delayed). As a result, an additional constraint has been
introduced which requires that the first two DELETE M IN operations to complete in this execution cannot have deleted
from the same queue, a constraint which is not present for the sequential process.
In this way, the distribution of outputs of any concurrent process is affected by subtle timing issues in ways which
seem hard to circumvent. We conjecture that there is no concurrent algorithm which is distributionally linearizable to
the sequential process. That said, it may be possible that one can produce a simple strategy satisfying a weaker condition than distributional linearizability such as an analogous variant of sequential consistency or quiescent consistency.

18

D

Omitted Proofs from Section 4.2

Here, we give a complete version of the potential argument.
Lemma 6.



n
X
1
α̂ (1 + δ) − pi exp (−αyi (t)) .
E [∆Ψ | y(t)] ≤
n
i=1

Proof. Case 1: If the bin is chosen, then the change is:


∆Ψi



 α

α
1
= Ψi (t + 1) − Ψi (t) = exp − (yi (t) + ∆i 1 −
) − exp − yi (t)
n
n
n





 α
α
1
exp − ∆i 1 −
−1
= exp − yi (t)
n
n
n

Taking expectations with respect to the random choices made on insertion, we have




α
1
1

1−
=
E exp −∆i
n
n
i
1 + παi n 1 − n1

 

α
1
α
= 1−
1−
+
1−
πi n
n
πi n

 

1
α
α
1−
+
1−
≤ 1−
πi n
n
πi n

1
n

2

1
n

2

− ...
.

Case 2: If some other bin j 6= i is chosen, then the change is:
∆Ψi =
=



α
1
exp − α
n (yi (t) − ∆j n ) − exp − n yi (t) =




α∆j
exp − α
y
(t)
−
1
.
exp
2
i
n
n

Again taking expectations with respect to the random choices made on insertion, we have
h
 α i

2

2
π
= πj −j α = 1− 1 α = 1 + πjαn2 + πjαn2 + . . . ≤ 1 + πjαn2 + c πjαn2 .
E exp ∆i 2
n
n2
πj n 2
i
Therefore, we have that

E [∆Ψi ] ≤
≤
≤
≤

2 !


 
2 !
X
α
α
1
α
1
(1 − )
pi − 1 +
1+ 2 +c
1−
+
pj
n
nπi
n
n πj
n 2 πj
j6=i

2 !

2 !
n
X
α
α
α
α
+c
pi +
+c
pj
−
nπi
nπi
n 2 πj
n 2 πj
i=1


α
−αpi 1 − γ − cα(1 + γ)2 pi +
1 + γ + αc(1 + γ)2
n


1
α̂ (1 + δ) − pi .
n
α
1−
nπi

Lemma 7. If yn/4 ≤ 0, then we have that

E [Φ(t + 1) | y(t)] ≤

α̂
1−
3n

19


Φ(t) + 1.

Proof. We start from the inequality
E [∆Φ | y(t)] ≤



n
n
X
X
1
α̂
exp (αyi (t)) ≤ α̂(1 + δ)
α̂ (1 + δ)pi −
pi exp (αyi (t)) − Φ(t).
n
n
i=1
i=1

(12)

We will now focus on bounding the first term (without the constants). We can rewrite it as:
n
X

n/4−1

pi exp (αyi (t)) =

i=1

X

pi exp (αyi (t)) +

i=1

n
X

pi exp (αyi (t)) .

(13)

i=n/4

Since yn/4 ≤ 0, the first term is upper bounded by 1. For the second term, notice that
3n/4

n
X

pi exp (αyi (t)) =

X

pn−j+1 exp (αyn−j+1 (t)).

(14)

j=1

i=n/4

The p terms are non-decreasing in j, while the y terms are non-increasing in j. Further, note that
3n/4

X

exp (αyn−j+1 (t)) ≤ Φ.

(15)

j=1

The whole sum is maximized when these non-increasing terms are equal. We therefore are looking to bound
n
X

pi exp (αyi (t)) ≤

n
4Φ X
pi .
3n

(16)

i=n/4

i=n/4

Notice that
n
X

n/4−1

pi = 1 −

X


pi ≤ 1 −

i=1

i=n/4

1
+
4


=

3
− .
4

Hence we have that
"

E [∆Φ | y(t)]

≤
≤
≤
=
≤

#
1
α̂ (1 + δ)
pi exp (αyi (t)) − Φ(t)
n
i=1




4Φ 3
1
α̂ (1 + δ)
−  − Φ(t) + (1 + δ)
3n 4
n




1+δ
4
1
α̂
1−
Φ(t) − Φ(t) + (1 + δ)
n
3
n





Φ(t)
4
α̂
1−
(1 + δ) − 1 + (1 + δ)
n
3


4
Φ(t)
 Φ(t)
−α̂
(1 + δ) − δ
+ 1 ≤ −α̂(1 + δ)
+ 1,
3
n
3 n
n
X

where in the last step we have used the fact that δ ≤ . Hence, we get that


α̂
Φ(t) + 1.
E [Φ(t + 1) | y(t)] ≤ 1 −
3n

20

(17)

Lemma 8. If y3n/4 ≥ 0, then we have that
E [Ψ(t + 1) | y(t)] ≤

1−

α̂
3n



Ψ + 1,

Proof. We start from the inequality
E [∆Ψ | y(t)] ≤
≤

Pn


α̂ (1 + δ) n1 − pi exp (−αyi (t))


Pn
P3n/4
1
1
i=3n/4+1 α̂ (1 + δ) n − pi exp (−αyi (t)) .
i=1 α̂ (1 + δ) n − pi exp (−αyi (t)) +
i=1

The second term is upper bounded as
n
X
i=3n/4+1



1
α̂ (1 + δ) − pi ≤ α̂(1 + δ)/4 − α̂
n

n
X

pi ≤ 1.

i=3n/4+1

We therefore now want to bound
3n/4

X
i=1



1
α̂ (1 + δ) − pi exp (−αyi (t)) .
n

We again notice that the first factor is non-decreasing, whereas the second one is non-increasing. Hence, the sum is
maximized when the non-decreasing terms are equal. At the same time, we have that
3n/4

X

exp (−αyi (t)) ≤ Ψ.

i=1

Hence, it holds that
3n/4

X
i=1




3n/4 
3n/4
1
1
4Ψ X
4Ψ X
1+δ
α̂ (1 + δ) − pi exp (−αyi (t)) ≤
α̂ (1 + δ) − pi = α̂
Ψ − α̂
pi
n
3n i=1
n
n
3n i=1





1+δ
1
4
α̂
4
α̂ 
= α̂
Ψ − α̂ Ψ 1 +
= Ψ (1 + δ) − 1 +
≤−
Ψ,
n
n
3
n
3
n3

where in the last step we have used the fact that δ ≤ . Therefore, we get that

α̂
Ψ + 1,
E [Ψ(t + 1) | y(t)] ≤ 1 − 3n
as claimed.
α̂
Lemma 9. Given  ∈ (0, 1) as defined, assume that yn/4 > 0 at t, and that E[∆Φ] ≥ − 3n
Φ(t). Then either Φ < 4 Ψ,
or Γ = O(n).

Proof. Fix λ = 2/3 − 1/54 for the rest of the proof. We can split the inequality in Lemma 1 as follows:




λn
n
X
X
1
1
α̂ (1 + δ)pi −
exp (αyi (t)) +
α̂ (1 + δ)pi −
exp (αyi (t)) .
E [∆Φ | y(t)] ≤
n
n
i=1

(18)

i=λn+1

We bound each term separately. Since the probability terms are non-increasing and the exponential terms are nondecreasing, the first term is maximized when all pi terms are equal. Since these probabilities are at most 1, we have




λn
X
1
α̂
1
α̂ (1 + δ)pi −
exp (αyi (t)) ≤
(1 + δ) − 1 Φ≤λn .
n
n
λ
i=1
21

(19)

The second term is maximized by noticing that the pi factors are non-increasing, and are thus dominated by their value
at λn. Noticing that we carefully picked λ such that
pλn ≤

1
4
− ,
n
n

we obtain, using the assumed inequality δ ≤ , that
n
X
i=λn+1



Φ>λn
3α̂
1
exp (αyi (t)) ≤ α̂ (δ − 4)
≤−
Φ>λn .
α̂ (1 + δ)pi −
n
n
n

(20)

α̂
By the case assumption, we know that E [∆Φ | y(t)] ≥ − 3n
Φ(t). Combining the bounds (18), (19), and (20), this
yields:


1
3α̂
α̂
α̂
(1 + δ) − 1 Φ≤λn −
Φ>λn ≥ − Φ(t).
n
λ
n
3n

Substituting Φ>λn = Φ − Φ≤λn yields:

(3 − /3) Φ ≤
For simplicity, we fix C() =

1
(1+δ) λ
−1+3
3−/3

=O

(1 + δ)
1





1
− 1 + 3 Φ≤λn .
λ

, to obtain

Φ ≤ C()Φ≤λn .
Let B =

P

yi >0

(21)

yi . Since we are normalizing by the mean, it also holds that B =
yi incr.



yi incr.

Φ≤λn ≤ λn exp (αyλn ) ≤ λn exp

P

yi <0 (−yi ).


αB
.
(1 − λ)n

Notice that
(22)

We put inequalities (21) and (22) together and get
Φ(t) ≤ λnC() exp



αB
(1−λ)n



,

(23)

Let us now lower bound the value of Ψ under these conditions. Since yn/4 > 0, all the costs below average must be in
the first quarter of y. We can apply Jensen’s inequality to the first n/4 terms of Ψ to get that
n/4
X

n
Ψ≥
exp (−αyi ) ≥ exp −α
4
i=1

Pn/4
i=1

n/4

yi

!
.

Pn/4
We now split the sum i=1 yi into its positive part and its negative part. We know that the negative part is summing
up to exactly −B, as it contains all the negative yi ’s and the total sum is 0. The positive part can be of size at most
B/4, since it is maximized when there are exactly n − 1 positive costs and they are all equal. Hence the sum of the
first n/4 elements is at least −3B/4, which implies that the following bound holds:




n
−3B/4
n
3B
Ψ ≥ exp −α
≥ exp α
.
(24)
4
n/4
4
n
If Φ < 4 Ψ, then there is nothing to prove. Otherwise, if Φ ≥ 4 Ψ, we get from (24) and (23) that




n
3B

αB
exp α
≤ Ψ ≤ Φ(t) ≤ λnC() exp (1−λ)n
,
44
n
4
22

Therefore, we get that:


B
exp α
n
Using the mundane fact that 3 −

1
1−λ



1
3−
1−λ



4λ
≤
C() = O




1
2


.

= 3/19, we get that

exp

αB
n




≤O

1
14


.

(25)

To conclude, notice that (25) implies we can upper bound Γ in this case as:


 4+
4+
αB
1
Γ = Φ + Ψ ≤ 4+
 Φ ≤  λnC() exp (1−λ)n ≤ O 14/(1−λ)
 C()λn = O(poly

1




n).

α
Lemma 10. Given  as above, assume that y 3n
< 0, and that E[∆Ψ] ≥ − 3n
Ψ. Then either Ψ > 4 Φ or Γ = O(n).
4

Proof. Fix λ = λ2 = 1/3 + 1/54. We start from the general bound on ∆Ψ from Lemma 6. We had that


n
X
1
α̂ (1 + δ) − pi exp (−αyi (t))
n
i=1



λn−1
n
X 
X
1
1
=
α̂ (1 + δ) − pi exp (−αyi (t)) +
α̂ (1 + δ) − pi exp (−αyi (t))
n
n
i=1

E [∆Ψ | y(t)] ≤

i=λn

≤
≤

α̂
α̂
((1 + δ) − (1 + 4)) Ψ<λn + (1 + δ) Ψ≥λn
n
n
ˆ
3α
α̂
−
Ψ<λn + (1 + δ) Ψ≥λn .
n
n

Using the assumption, we have that
−

α̂
3α̂
α̂
Ψ ≤ E [∆Ψ | y(t)] ≤ −
(Ψ − Ψ≥λn ) + (1 + δ) Ψ≥λn .
3n
n
n

We can re-write this as
Ψ ≤ Ψ≥λn

1 + δ + 3
= C()Ψ≥λn .
3 − /3

However, we also have that

Ψ≥λn ≤ (1 − λ)n exp (−αyλn ) ≤ (1 − λ)n exp


αB
.
nλ

At the same time, since y3n/4 < 0, we have that
Φ≥

n
exp
4




3αB
.
n

If Ψ < 4 Φ, we can conclude. Let us examine the case where Ψ ≥ 4 Φ. Putting everything together, we get
n
exp
44



3αB
n


≤


Φ ≤ Ψ ≤ C()Ψ≥λn ≤ (1 − λ) nC() exp
4
23



αB
nλ


.

Alternatively,

exp

αB
n



 
1
16
16
1 + δ + 3
1
3−
≤
C()(1 − λ) =
(1 − λ)
=O 2 .
λ


3 − /3


Therefore,

exp

αB
n




≤O

1
13


.

To complete the argument, we bound:

Γ=Ψ+Φ≤

E

4
1+





Ψ ≤ (1 − λ) C() exp

αB
nλ


n≤O

 n 
.
22

Proof of Theorem 4

Before we prove Theorem 4 we need the following fact about exponential disitributions:
P
Fact 2. Let X1 , X2 , . . . be independent and Xi ∼ Exp(λ) for all i. Let Yi = k≤i Xk . Fix any interval I ⊆ [0, ∞)
of length m. Then, #{i : Yi ∈ I} ∼ Poi(mλ).
Proof of Theorem 4. Let I(t) = [wmin (t), wmax (t)], and let Lj (t) be the number of elements in bin j in I(t) at time
t. Then, by memorylessness and Fact 2, for all bins j except the bin jmax containing wmax (t), the number of labels
in I(t) in bin j before any deletions occur is distributed as Poi(|I|/n). In particular, the expected number of elements
after t rounds is bounded by EX∼Poi(|I|/n) [X] = |I|/n. Moreover, for the bin containing wmax (t), by definition, at
time t it contains exactly one element in I, namely, wmax (t). Hence, we have
 

n
X
Lj (t) I(t)
E[max rank(t)] ≤ E E 
I(t)

j=1

≤ E [1 + (n − 1)|I|/n]
I(t)


1
=O
n(log n + log C) ,
α
by Lemma 4.

F

Omitted Proofs from Section 4.4

We first require the following technical lemma:
Lemma 11. For any interval I = [a, b] which may depend on µ, we have E[rank(b) − rank(a)|µ] ≤ n(b − a + 1).
Proof. We first show that if I does not depend on µ, then E[rank(b) − rank(a)|µ] ≤ n(b − a). By Fact 2 we have


n
X
`j,[a,b] µ
E[rank(b) − rank(a)|µ] ≤ E 
j=1


n
X
= E
j=1



= n(b − a) .
24

E

X∼Poi(b−a)

[X] µ

To conclude the proof, we now observe that µ depends on at most n elements, namely, those on top of the queues, and
that if we remove those elements, then the remaining elements behave just as above. Thus, by conditioning on µ, we
increase the rank by at most an additional factor of n.

Lemma 12. For all t, we have E[rank(µ(t))] ≤ O (A + 1/α2 )n .
Proof. For any bin j, we have
Z

µ

E[`j,(−∞,µ] (t)|µ] =

−∞
Z µ
(a)

E[`j,[x,µ] |µ, wj (t) = x] · pj,µ (x)dx

≤

E

Z

[1 + X|µ, wj (t) = x] · pj,µ (x)dx

−∞ X∼Poi(µ−x)/n
µ

1
1
(1 + µ − x) · pj,µ (x)dx = E[(1 + µ − wj (t))1wj (t)≤µ |µ]
n
n

1
≤
1 + E[(µ − wj (t))1wj (t)≤µ |µ] .
n
=

−∞

where (a) follows because after we’ve conditioned on the value of wj (t), the values of the remaining labels in bin j is
independent of µ and we can apply Fact 2. Therefore, we have


n
X
(a)
E[`j,(−∞,µ−An](t) |µ] + (A + 1)n
E[rank(µ)] ≤ E[rank(µ − An)] + (A + 1)n = E 
j=1



n
X
= E
E[`j,(wj (t),µ−An](t) |µ, wj (t)] + (A + 1)n
j=1



n
1 X
≤ 1+ E
(µ − wj (t))1wj (t)≤µ−An  + (A + 1)n
n µ j=1


∞
X
(c)
1X 
≤ 1+
(µ − wj (t) + 1) + (A + 1)n
E
n
µ

(b)

k=1

wj (t)∈[µ−(k+1+A)n,µ−(k+A)n]

∞
∞
X
(d)
1X
≤1+
(k + 2)n E [b<−i ] + (A + 1)n ≤ 1 +
(k + 2)n exp(−αk) + (A + 1)n
n
µ
k=1
α

k=1

e
n + (A + 1)n ,
≤1+ α
(e − 1)2
where (a) follows from Lemma 11, (b) follows from Fact 2, (c) follows from Lemma 11, and (d) follows from Lemma
α
5. Notice that for α small we have (eαe−1)2 = O(1/α2 ). Simplifying the above then yields the claimed bound.

F.1

Other Proofs

Lemma 13. We have that Γ(0) = O(n).
Proof. In the initial state, the values xi (0) are independent exponentially distributed random variables with mean

25

1/(nπi ). Now,
E[Φ(0)]

=
=

=

=


 
wi (0)
− µ(0)
exp α
E
n




X
1X
xj
E exp α xi (0) −
n




 Y


X
1
α
exp − xj (0) 
E exp αxi (0) 1 −
n
n
j6=i







Y
X 
1
α
E exp αxi (0) 1 −
E  exp − xj (0)  ,
n
n
X

j6=i

where the last line follows from the (pairwise) independence of the xi . All terms in the right hand side are now
exactly moment generating functions of the wi evaluated at some point. Since the moment generating function of an
exponential with parameter λ evaluated at t is well known to be λ/(λ − t), we can compute:
E[Φ(0)]

=

X

≤

X

1
nπi
1
nπi

− α(1 − n1 ) j6=i
1+γ Y
1

1−γ−α

j6=i

≈

+


X
1+γ 
1−
απj 
1−γ−α
j6=i

=

1
nπj

1 + απj



X

1
nπj

Y

O(n).

The argument for Ψ(0) is symmetric, replacing α with −α.

26

α
n

