A Simple yet Exact Analysis of the MultiQueue

The MultiQueue, initially proposed by Rihani et al. [16] and improved upon by Williams et al. [21], emerged as the state-of-the art relaxed priority queue. Due to its high scalability and robust quality, the MultiQueue inspired a number of follow-up works [15, 23]. Its design uses the power-of-two-choices paradigm and is delightfully simple: We use $n$ (sequential) priority queues for some fixed $n\mathrm{\in }\mathrm{\mathbb{N}}$. Each insertion adds its element to a queue chosen uniformly at random and each deletion picks two queues uniformly at random and deletes from the one with the smaller minimum.

Figure 1 illustrates the MultiQueue with $n=6$ queues. We can generalize this design to pick any number $c>1$ of queues for deletions where even non-integer choices of $c$ make sense: We would then pick $\mathrm{\lfloor }c\mathrm{\rfloor }+1$ queues with probability $c-\mathrm{\lfloor }c\mathrm{\rfloor }$ and $\mathrm{\lfloor }c\mathrm{\rfloor }$ queues otherwise. In practice, the individual queues are protected by mutual exclusion locks, and $n$ is proportional to the number of processing elements to find unlocked queues in (expected) constant time.

Our theoretical understanding of the MultiQueue is still incomplete. One obstacle is that the order of operations matters: Intuitively, deletions can cause the distribution of elements to drift apart and increase the expected rank error, while insertions of small elements can mask accumulated differences. This suggests that the worst-case setting is when following the insertion of sufficiently many elements, only deletions occur. Like Alistarh et al. [2], we exclusively consider this setting. At first glance, this process seems closely related to the classical balls-into-bins process, where balls are placed one after the other into the least loaded of two randomly chosen bins. Famously, the difference between the highest load and the average load for $n$ bins is in $\mathrm{𝒪}(\log \log n)$ with high probability for any number of balls. Numerous variants of the balls-into-bins process have been proposed and studied [5, 12, 6, 14]. However, reducing the process to a balls-into-bins process imposes multiple difficulties. The state of the MultiQueue is not fully described by the number of elements in each queue but also involves information about the ranks of the elements. Moreover, deleting an element from a queue can affect the ranks of elements in other queues. Despite these challenges, Alistarh et al. [2] managed to transfer the potential argument from the balls-into-bins analysis by Peres et al. [14] to a MultiQueue analysis via an intermediate “exponential process” that avoids correlations between the elements in the queues. They prove that the expected rank error is in $\mathrm{𝒪}(n)$ and the expected worst-case rank error is in $\mathrm{𝒪}(n\log n)$ for any number of deletions and any $c\in (1,2]$, while the rank errors diverge with the number of deletions for $c=1$. In follow-up work, this technique is generalized to other relaxed concurrent data structures [1] and a process where each processing element has its own priority queue and “steals” elements from other processing elements with some probability [15].

In this paper, we present an analysis of the MultiQueue that, compared to the potential argument by Alistarh et al. [2], is simultaneously simpler and more precise. We characterise the exact long-term distribution of the rank error for any $c>1$ and any $n\mathrm{\in }\mathrm{\mathbb{N}}$. From this distribution we can derive, for instance, that the expected rank error for $c=2$ is $\frac{5}{6}n-1+\frac{1}{6n}$. In addition to covering any $c>1$, our analysis generalizes to all deletion schemes where the probability for a queue to be selected solely depends on the rank of the queue (when ordering the queues according to their smallest element).

We achieve this by modelling the deletion process as a Markov chain and observing that its stationary distribution can be described using a sequence of $n-1$ independent geometrically distributed random variables. In the full version of this paper [20] we also apply our techniques to the elegant exponential process by Alistarh et al. [2], which we believe to be of independent interest.

First, in Section 2, we introduce the formal model of a generalized MultiQueue and the setting in which we analyze it. We then state our main results, including Theorem 1 that characterizes the long-term distribution of the ranks of the top-elements in the MultiQueue. In Section 3, we present our analysis of the generalized MultiQueue, leading to the proof of Theorem 1. We apply Theorem 1 to compute the expected rank error for any $c>1$ and any $n\mathrm{\in }\mathrm{\mathbb{N}}$ in Section 4. Finally, in Section 5, we discuss implications and limitations of our results and outline possible future work.

A $\sigma$-MultiQueue consists of $n$ priority queues and a choice distribution $\sigma$ on $[n]$ that captures a generalised deletion strategy (as explained below). The $n$ queues are initially populated by randomly partitioning an infinite set of elements. ²²2Note that every queue receives an infinite number of elements with probability $1$. The queues, identified with the sets of elements they contain, are denoted by $Q\mathrm{₁},\mathrm{\dots },Qₙ$, indexed such that . The minima are also called top-elements. We then perform a sequence of deletions. Each time, we select an index $i\mathrm{\in }[n]$ according to $\sigma$ and delete the top-element of $Q_i$. ³³3We write $[n]$ as a shorthand for $\{1,\mathrm{\dots },n\}$. Then, we relabel the queues such that their top-elements appear in ascending order again. Let $(Q{\mathrm{₁}}^{(s)},\mathrm{\dots },Q{ₙ}^{(s)})$ be the sequence of queues after $s$ deletions and $r_i^{(s)}$ the rank of the top-element $\min Q_i^{(s)}$ among $Q{\mathrm{₁}}^{(s)}\mathrm{\cup }\mathrm{\dots }\mathrm{\cup }Q{ₙ}^{(s)}$, for any $s\mathrm{\in }\mathrm{\mathbb{N}}$ and $i\mathrm{\in }[n]$.

Intuitively, $\sigma$ should be biased towards smaller values of $i$, i.e., towards selecting queues with smaller top-elements, to ensure that the rank error does not diverge over time. Using the notation ${\sigma }_i:={\mathrm{Pr}}_{i^{\ast }\sim \sigma }[i^{\ast }=i]$ and ${\sigma }_{\le i}:={\mathrm{Pr}}_{i^{\ast }\sim \sigma }[i^{\ast }\mathrm{\le }i]$, the formal requirement for $\sigma$ turns out as:

If $\sigma$ does not satisfy $(\mathrm{☆})$, the MultiQueue deletes too frequently from “bad” queues (i.e., with large top-elements) and the gap between “good” and “bad” queues increases over time. We prove a corresponding formal claim in the full version of this paper [20].

One might think that the ranks are correlated in complex ways. While they are correlated, they effectively arise as the prefix sum of $n-1$ independent random variables. More precisely, our main theorem draws attention to the differences between the ranks of consecutive top-elements.

From the distribution of the ranks of the top-elements given by Theorem 1 it is straightforward to derive the rank error distribution.

For $c>1$ we define the $c$-MultiQueue to be the $\sigma$-MultiQueue where $\sigma$ is the distribution that corresponds to picking the best out of $c$ randomly selected queues as described in Section 1. For instance, the probability to select one of the first $i$ queues with $c=2$ is ${\sigma }_{\le i}=1-(1-\frac{i}{n})\mathrm{²}$. Note that ($\mathrm{☆}$) is satisfied (see Lemma 8). We can then derive several useful quantities from Theorem 1, including the expected rank error.

Figure 2 plots the expected asymptotic rank error per queue depending on $c$, and an approximation $\frac{1}{c-1}$. We also give concentration bounds for the rank error in Theorem 9.

As an intermediate step in their analysis, Alistarh et al. [2] introduce the “exponential process”, where new top-elements are not given by the current state but generated by adding an exponential random variable to the current top-element. We reformulate this process as the equivalent exponential-jump process (EJP) as follows. The EJP involves $n$ tokens on the real number line and a distribution $\sigma$ on $[n]$. In every step, we sample $i^{\ast }\sim \sigma$ and $X\sim \mathrm{Exp}(1)$. We then identify the $i^{\ast }$th token from the left and move it a distance of $X$ to the right. More formally, the state of the process is given by the sequence of positions of the tokens and the state transition can be described as

We provide an exact analysis, which we believe to be of independent interest, and explain the connection between the EJP and the MultiQueue in the full version of this paper [20]. With the same methods as before, we analyse the differences $(d\mathrm{₁},\mathrm{\dots },d_{n-1})$ with $d_i=t_{i+1}-t_i$.

In other words, the distances between neighbouring tokens are, in the long-run, mutually independent and exponentially distributed with parameters as given.

If $i=n$ then ${\overrightarrow{e}}_i=\overrightarrow{0}$ and ${\sigma }_{\le i}=1$ so the claim is trivial. Now assume . For any $\overrightarrow{d}\mathrm{\in }\mathrm{\mathbb{N}}{\mathrm{₀}}^{n-1}$ we have

Hence, $\pi (\overrightarrow{d}+{\overrightarrow{e}}_i)=\pi (\overrightarrow{d})\mathrm{·}(1-p_i)$ and the claim follows. $◀$ The following auxiliary lemma captures the main insight required in the proof of Theorem 5.

We prove $\nu (\overrightarrow{d},i)=\pi (\overrightarrow{d})\mathrm{·}{\sigma }_{\le i}$ by induction. In the induction step we may assume that $\nu ({\overrightarrow{d}}^{\prime },i^{\prime })=\pi ({\overrightarrow{d}}^{\prime })\mathrm{·}{\sigma }_{\le i^{\prime }}$ holds whenever or when $i=i^{\prime }$ and . In general, there are three ways in which a transitional state $(\overrightarrow{d},i)$ might be reached:

1. (i)

   The transition started with $\overrightarrow{d}={\overrightarrow{d}}_{\mathrm{start}}$ and ball $i$ was activated.

2. (ii)

   Ball $i$ has skipped a dot and we thus reached $(\overrightarrow{d},i)$ from $(\overrightarrow{d}-{\overrightarrow{e}}_{i-1}+{\overrightarrow{e}}_i,i)$.

3. (iii)

   Ball $i$ has just overtaken another ball and we thus reached $(\overrightarrow{d},i)$ from $(\overrightarrow{d},i-1)$.

For $i=1$, consider a transitional state $(\overrightarrow{d},1)$ where the first ball is active. Here, only (i) is possible since the first ball never skips a dot (transition ends with probability $1$ in rule 2.1) and there is no ball to its left. The probability for $(\overrightarrow{d},1)$ to occur is thus

For $i>1$, there are two cases depending on whether $d_{i-1}>0$, i.e., whether there is a dot in between ball $i-1$ and ball $i$. If $d_{i-1}>0$, then only (i) and (ii) are possible, so

If $d_{i-1}=0$, then only (i) and (iii) are possible, so

$◀$ With Lemma 7 in place, we can now prove Theorem 5.

Given a state ${\overrightarrow{d}}_{\mathrm{start}}\sim \pi$, we transition to a new state ${\overrightarrow{d}}_{\mathrm{end}}$ according to the transition probabilities $P$. To end in ${\overrightarrow{d}}_{\mathrm{end}}$, we first need to reach the transitional state $({\overrightarrow{d}}_{\mathrm{end}}+{\overrightarrow{e}}_i,i)$ for some $i\in [n]$ and then decide to end the transition there. Note that we need $({\overrightarrow{d}}_{\mathrm{end}}+{\overrightarrow{e}}_i,i)$ rather than $({\overrightarrow{d}}_{\mathrm{end}},i)$, since ending the transition (rule 2.1) reduces $d_i$ by one. The probability to end in ${\overrightarrow{d}}_{\mathrm{end}}$ is therefore

It follows that ${\overrightarrow{d}}_{\mathrm{end}}$ is again distributed according to $\pi$ and $\pi$ is a stationary distribution. $◀$ Finally, we prove Theorem 1 and Corollary 2.

Let ${\overrightarrow{d}}^{(s)}=(d{\mathrm{₁}}^{(s)},\mathrm{\dots },d_{n-1}^{(s)})$ with $d_i^{(s)}=r_{i+1}^{(s)}-r_i^{(s)}-1$. Then, ${({\overrightarrow{d}}^{(s)})}_{s\mathrm{\in }\mathrm{\mathbb{N}}}$ is a Markov chain with transition probabilities $P$. Since we can reach $(0,\mathrm{\dots },0)$ from any state and vice versa, the Markov chain is irreducible. The Markov chain is aperiodic since $(0,\mathrm{\dots },0)$ can transition into itself (if ball $n$ is activated and immediately stops). This implies that the stationary distribution $\pi$ that we found is unique and that ${\overrightarrow{d}}^{(s)}$ converges in distribution to $d\sim \pi$ (see [13, Theorem 1.8.3]). Let ${\overrightarrow{\delta }}^{(s)}=(\delta {\mathrm{₁}}^{(s)},\mathrm{\dots },{\delta }_{n-1}^{(s)})$ with ${\delta }_i^{(s)}=d_i^{(s)}+1$. Clearly, ${({\overrightarrow{\delta }}^{(s)})}_{s\mathrm{\in }\mathrm{\mathbb{N}}}$ converges in the same way, except that the geometric random variables are shifted. By definition, we have $r_i^{(s)}=1+{\sum }_{j=1}^{i-1}{\delta }_j^{(s)}$ so the claimed distributional limit $(r\mathrm{₁},\mathrm{\dots },rₙ)$ of $(r{\mathrm{₁}}^{(s)},\mathrm{\dots },r{ₙ}^{(s)})$ follows. $◀$

Theorem 1 states the ranks of the top-elements converge in distribution to $(r_1,\mathrm{\dots },r_n)$. The distribution for $R$ follows from the fact that we select the queue to delete from according to $\sigma$ and deleting an element with rank $r$ yields a rank error of $r-1$. Using the fact that ${𝔼}_{X\sim {\mathrm{Geom}}_1(p)}[X]=1/p$, we have for the expected rank error

$◀$

Recall that we sample $\mathrm{\lfloor }c\mathrm{\rfloor }$ queues with probability $1-\epsilon$ and $\mathrm{\lfloor }c\mathrm{\rfloor }+1$ queues otherwise. We fail to select one of the first $i$ queues only if none of them were sampled. Hence for :

The inequality uses that we have $\mathrm{\lfloor }c\mathrm{\rfloor }\mathrm{\ge }2$, or $\epsilon >0$, or both. $◀$

We now prove Theorem 3, restated here for easier reference. See 3

We have just checked in Lemma 8 that $\sigma$ satisfies $(\mathrm{☆})$ and computed ${\sigma }_{\le i}=1-{(1-\frac{i}{n})}^{\mathrm{\lfloor }c\mathrm{\rfloor }}(1-\epsilon \frac{i}{n})$. We can therefore specialise the formula for the expected rank error from Corollary 2 by plugging in $\sigma$ and simplifying, which yields

We are now ready to prove claim (i). Using that $f\mathrm{₂}(x)=x\mathrm{·}\frac{1-x\mathrm{²}}{1-x}=x\mathrm{·}(1+x)=x+x\mathrm{²}$, we have

Similarly, we can prove (ii). First, we simplify $f_c(x)$ for $c=1+\epsilon$ with $\epsilon \mathrm{\in }(0,1)$:

We then get (omitting a simple calculation):

We now turn our attention to general $c>1$ again. Our goal is to approximate the sum by an integral. To bound the approximation error effectively, we will first show that $f_c$ is monotonic. For this let us examine the fractional term $g_c(x)$ occurring in $f_c(x)$:

From (1) we can see that $g_c(x)$ does not have a singularity at $x=1$ and by setting $g_c(1)=f_c(1)=1+\frac{1}{c-1}=\frac{c}{c-1}$ both functions are continuous on $[0,1]$. We also see from (1) that $g_c(x)$ is increasing in $x$ and decreasing in $c$ (recall that $c$ determines $\epsilon =c-\mathrm{\lfloor }c\mathrm{\rfloor }$). Because the other factor $x^{\mathrm{\lfloor }c\mathrm{\rfloor }-1}(1-\epsilon +\epsilon x)$ of $f_c(x)$ is also increasing in $x$ and decreasing in $c$, we conclude that $f_c(x)$ as a whole is increasing in $x$ and decreasing in $c$. This makes the upper and lower sums bounding the integral of $f_c$ particularly simple:

By rearranging we obtain (iii). We now turn to the cruder bound (iv). We begin with $c\mathrm{\in }\mathrm{\mathbb{N}}\setminus \{1\}$. In this case we have $f_c(x)=x^{c-1}\mathrm{·}{g}_c(x)$ where $1\mathrm{\le }{g}_c(x)\mathrm{\le }\frac{c}{c-1}$ for all $x\mathrm{\in }[0,1]$. This gives:

Combining this with (iii) gives $\frac{n}{c}-\frac{c}{c-1}\mathrm{\le }\mathrm{𝔼}[R]\mathrm{\le }\frac{n}{c-1}$ when $c\mathrm{\in }\mathrm{\mathbb{N}}\setminus \{1\}$. When $c\mathrm{\notin }\mathrm{\mathbb{N}}$ we can use that $f_c(x)$ is decreasing in $c$ and round conservatively to obtain the claimed result. $◀$

We will use a tail bound by Janson [9, Theorem 2.1] on the sum of geometrically distributed random variables from. It reads

where $X$ is a sum of geometrically distributed random variables (with possibly differing success probabilities), $p_{\ast }$ is the smallest success probability and $\mu =\mathrm{𝔼}[X]$.

We apply this bound to $X=rₙ-1$, which has the required form by Theorem 1. It is easy to check that $p_{\ast }={\delta }_{n-1}=\frac{1}{n+1}=\mathrm{\Theta }(\frac{1}{n})$ and

Since the rank error $R$ clearly satisfies $R\mathrm{\le }rₙ-1=X$ we have for $k$ large enough

By a union bound, the probability that we observe a rank error exceeding $k\mathrm{·}n\log n$ at some point during $n^c$ deletions is at most $n^c\mathrm{·}{n}^{-\mathrm{\Theta }(k)}$. For large enough $k$, this probability is still small. $◀$

To give some intuition for how quickly the $2$-MultiQueue converges to its stable state and for how close the observed ranks of top-elements are to their expectation we provide experimental data in Figure 5.