How Asymmetry Helps Buffer Management: Achieving Optimal Tail Size in Cup Games

Much of the work on cup games has focused on bounding the backlog of the system, which is defined to be the amount of water in the fullest cup.

Research on bounding backlog has spanned five decades [7, 23, 8, 32, 30, 36, 6, 26, 33, 34, 19, 11, 28, 1, 18, 31]. Much of the early work focused on the fixed-rate version of the game, in which the filler places a fixed amount of water $f_{j}$ into each cup $j$ on every step [7, 23, 8, 32, 30, 36, 6, 26, 33, 34]; in this case constant backlog is achievable [33, 7]. For the full version of the game, without fixed rates, constant backlog is not possible. In this case, the optimal deterministic emptying algorithm is known to be the greedy emptying algorithm, which always empties from the fullest cup, and which achieves backlog $O(\log n)$ [1, 18]. If the emptier is permitted to use a randomized algorithm, then it can do much better, achieving an asymptotically optimal backlog of $O(\log\log n)$ for $\operatorname{poly}n$ steps with high probability [19, 11, 28].

The tail size of a cup game at each step is the number of cups containing at least some constant $c$ amount of water. For the guarantees in this paper, $c$ will be taken to be $2$.

A guarantee of small tail size is particularly appealing for scheduling applications, where cups represent tasks and water represents work that arrives to the tasks over time. Whereas a bound of $b$ on backlog guarantees that the furthest behind worker is only behind by at most $b$, it says nothing about the number of workers that are behind by $b$. In contrast, a small bound on tail size ensures that almost no workers are behind by more than $O(1)$.

The main result in this paper is a randomized emptying algorithm that achieves tail size
$O(\log n\log\log n)$. The algorithm also simultaneously optimizes backlog, keeping the maximum height at $O(\log\log n)$. As a result the total amount of water above height $2$ in the system is $\tilde{O}(\log n)$ with high probability. In constrast, the best possible deterministic emptying algorithm allows for up to $n^{1-\varepsilon}$ cups to all have fills $\Omega(\log n)$ at once (see the lower-bound constructions discussed in [19] and [12]).

The problems of optimizing tail size and backlog are closely related to the problem of optimizing the $c$-shifted $\ell_{p}$ norm of the cup game. Formally, the $c$-shifted $\ell_{p}$ norm is given by

where $f_{i}$ is the fill of cup $i$. ¹¹1When $p\neq\infty$, in order for the $c$-shifted $\ell_{p}$ norm to be interesting, it is necessary to require that $c\geq\Omega(1)$, since trivial filling strategies can achieve fill $\Omega(1)$ in $\Theta(n)$ cups deterministically. The problem of bounding backlog corresponds to the problem of optimizing the $\ell_{\infty}$ norm of the cup game, and the problem of bounding tail size corresponds to bounding the $2$-shifted $\ell_{1}$ norm. By optimizing both metrics simultaneously our algorithm has the desirable property that it also achieves a bound of $\tilde{O}(\log n)$ for the $2$-shifted $\ell_{p}$ norm for any $p\in O(1)$, which is optimal up to doubly logarithmic factors.

To approach the combinatorial difficulty of analyzing cup games, past works have often turned to various forms of beyond worst-case analysis (e.g., smoothed analysis [11], semi-clairvoyance [31], resource augmentation [11, 31, 19, 18]). The most successful of these approaches has arguably been resource augmentation. In the cup game with $\varepsilon$ resource augmentation, the filler is permitted to distribute at most $1-\varepsilon$ water into cups at each step (rather than $1$ full unit), giving the emptier a small advantage. Resource augmentation can also be studied in a more extreme form by allowing the emptier to fully empty a cup on each step, rather than simply removing a single unit [19, 18]. Resource augmentation significantly simplifies the task of analyzing cup games — for example, there was nearly a 30 year gap between the first randomized bounds on backlog with resource augmentation [19] versus the first bounds without resource augmentation [28].

Currently, the best known guarantees with resource augmentation are achieved by the algorithm of [11] which, using $\varepsilon=1/\operatorname{polylog}n$, limits backlog to $O(\log\log n)$ and tail size to $\operatorname{polylog}n$ (with high probability).

The algorithm, which is called the smoothed greedy algorithm, begins by randomly perturbing the starting state of the system, and then following a variant of the deterministic greedy emptying algorithm. Roughly speaking, the random perturbations at the beginning of the game allow for the number of cups $X_{t}$ containing more than $1$ unit of water after each step $t$ to be modeled by a biased random walk $X_{1},X_{2},\ldots$, where $\Pr[X_{i}=X_{i-1}+1]=1/2-\varepsilon$ and $\Pr[X_{i}=\max(X_{i-1}-1,0)]=1/2+\varepsilon$. This is where the resource augmentation plays a critical role, since it introduces a bias to the random walk which pushes the walk near $0$ at all times. In contrast, without resource augmentation, the random walk is unbiased.

Subsequent work [28] showed that the algorithm’s guarantees on backlog continue to hold without resource augmentation (at least, for a polynomial number of steps). More generally, the analysis bounds the number of cups at a given height $\alpha$ by roughly $n^{1/2^{\Omega(\alpha)}}$, which in turn implies an arbitrarily small polynomial tail size. Whether or not a subpolynomial tail size can be achieved without resource augmentation has remained open.

We show that resource augmentation is not needed to bound tail size. We present a randomized emptying algorithm (called the asymmetric smoothed greedy algorithm) that achieves tail size $\tilde{O}(\log n)$ with high probability in $n$ after each of the first $\operatorname{poly}n$ steps of a cup game. We prove that the algorithm is nearly optimal, in that any emptying algorithm must allow for a tail size of $\tilde{\Omega}(\log n)$ with probability at least $\frac{1}{\operatorname{poly}n}$.

The analysis of the algorithm takes an indirect approach to bounding tail size. Rather than examining tail size directly, we instead prove that the use of randomness by the algorithm makes the state of the cups at each step “difficult” for the filler to accurately predict. We call this the unpredictability guarantee. We then show that any greedy-like algorithm that satisfies the unpredictability guarantee is guaranteed to have tail size $\tilde{O}(\log n)$ and backlog $O(\log\log n)$.

Algorithmically, the key to achieving the unpredictability guarantee is to add a small amount of asymmetry to the smoothed greedy emptying algorithm. When choosing between cups that have 2 or more units of water, the emptier follows the standard smoothed greedy algorithm; but when choosing between cups whose fills are between 1 and 2, the emptier ignores the specifics of how much water is in each cup, and instead chooses between the cups based on random priorities that are assigned to the cups at the beginning of the game.

Intuitively, the asymmetric treatment of cups ensures that there is a large collection (of size roughly $n/2$) of randomly selected cups that are “almost always” empty. The fact that the emptier doesn’t know which cups these are then implies the unpredictability guarantee. Proving this intuition remains highly nontrivial, however, and requires several new combinatorial ideas.

The cup game captures a scheduling problem in which a single processor must pick one of $n$ tasks to make progress on in each time step. The multi-processor version of this scheduling problem is captured by the $p$-processor cup game [11, 28, 31, 1, 7, 33]. In each step of the $p$-processor cup game, the filler distributes $p$ units of water among cups, and the emptier removes $1$ unit of water from (up to) $p$ different cups. Because the emptier can remove at most $1$ unit of water from each cup at each step, an analogous constraint is also placed on the filler, requiring that it places at most $1$ unit of water into each cup at each step.

A key feature of the $p$-processor cup game is that the emptier is required to remove water from $p$ distinct cups in each step, even if the vast majority of water is contained in fewer than $p$ cups.

Until recently, establishing any nontrivial bounds on backlog in the multi-processor cup game remained an open problem, even with the help of resource augmentation. Recent work by Bender et al. [11] (using resource augmentation) and then by Kuszmaul [28] (without resource augmentation) established bounds on backlog closely matching those for the single-processor game.

By extending our techniques to the multi-processor setting, we construct a randomized emptying algorithm achieves tail size $\tilde{O}(\log n+p)$ with high probability in $n$ after each of the first $\operatorname{poly}n$ steps of a $p$-processor cup game. Moreover, we show that the dependence on $p$ is near optimal for any backlog-bounded algorithm (i.e., any algorithm that achieves backlog $\operatorname{poly}n$ or smaller).

In the presence of resource augmentation $\varepsilon=1/\operatorname{polylog}n$, the smoothed greedy emptying algorithm is known to provide an unending guarantee [11], meaning that the high-probability bounds on backlog and tail size continue to hold even for arbitrarily large steps $t$.

A natural question is whether unending guarantees can also be achieved without the use of resource augmentation. It was previously shown that, when $p\geq 2$, the smoothed greedy algorithm does not offer unending guarantees [28]. Analyzing the single-processor game has remained an open question, however.

We give a lower bound construction showing that neither the smoothed greedy algorithm nor the asymmetric smoothed greedy algorithm offer unending guarantees for the single-processor cup game without the use of resource augmentation. Even though resource augmentation $\varepsilon>0$ is needed for the algorithms to achieve unending guarantees, we show that the amount of resource augmentation required is very small. Namely, $\varepsilon=1/2^{\operatorname{polylog}n}$ is both sufficient and necessary for the asymmetric smoothed greedy algorithm to offer unending guarantees on both tail size and backlog.

We generalize our lower-bound construction to work against any emptying algorithm that is both monotone and memoryless, including emptying algorithms that are equipped with a clock. We show that no such emptying algorithm can offer an unending guarantee of $o(\log n)$ backlog in the single-processor cup game, and that any unending guarantee of $\operatorname{polylog}n$ tail size must come of the cost of polynomial backlog.

We call the filling strategy in our lower bound construction the fuzzing algorithm. The fuzzing algorithm takes a very simple approach: it randomly places water into a pool of cups, and shrinks that pool of cups very slowly over time. The fact that gradually shrinking random noise represents a worst-case workload for cup games suggests that real-world applications of cup games (e.g., processor scheduling, network-switch buffer management, etc.) may be at risk of experiencing “aging” over time, with the performance of the system degrading due to the impossibility of strong unending guarantees.

Extensive work has also been performed on other variants of the cup game. Bar-Noy et al. [5] studied the backlog for a variant of the single-processor cup game in which the filler can place arbitrarily large integer amounts of water into cups at each step. Rather than directly bounding the backlog, which would be impossible, they show that the greedy emptying algorithm achieves competitive ratio $O(\log n)$, and that this is optimal for both deterministic and randomized online emptying algorithms. Subsequent work has also considered weaker adversaries [21, 17].

Several papers have also explored variants of cup games in which cups are connected by edges in a graph, and in which the emptier is constrained by the structure of the graph [13, 12, 14, 15]. This setting models multi-processor scheduling with conflicts between tasks [14, 15] and some problems in sensor radio networks [12].

Another recent line of work is that by Kuszmaul and Westover [29], which considers a variant of the $p$-processor cup game in which the filler is permitted to change the value of $p$ over time. Remarkably, the optimal backlog in this game is significantly worse than in the standard game, and is $\Theta(n)$ for an (adaptive) filler.

Cup games have also been used to model memory-access heuristics in databases  [9]. Here, the emptier is allowed to completely empty a cup at each step, but the water from that cup is then “recycled” among the cups according to some probability distribution. The emptier’s goal is achieve a large recycling rate, which is the average amount of water recycled in each step.

Closely related to the study of cup games is the problem of load balancing, in which one must assign balls to bins in order to minimize the number of balls in the fullest bin. In the classic load balancing problem, $n$ balls arrive over time, and each ball comes with a selection of $d$ random bins (out of $n$ bins) in which it can potentially be placed. The load balancing algorithm gets to select which of the $d$ bins to place the ball in, and can, for example, always select the bin with the fewest balls. But what should the algorithm do when choosing between bins that have the same number of balls? In this case, Vöcking famously showed that the algorthm should always break ties in the same direction [40], and that this actually results in an asymptotically better bound on load than if one breaks ties arbitrarily. Interestingly, one can think of the asymmetry used in Vöcking’s algorithm for load balancing as being analogous to the asymmetry used in our algorithm for the cup game: in both cases, the algorithm always breaks ties in the same random direction, although in our result, the way that one should define a “tie” is slightly nonobvious. In the case of Vöcking’s result, the asymmetry is known to be necessary in order to get an optimal algorithm [40]; it remains an open question whether the same is true for the problem of bounding tail size in cup games.

Bounds on backlog have been used extensively in data-structure deamortization [2, 19, 18, 3, 37, 25, 20, 27], where the scheduling decisions by the emptier are used to decide how a data structure should distribute its work.

Until recently, the applications focused primarily on in-memory data structures, since external-memory data structures often cannot afford the cost of a buffer overflowing by an $\omega(1)$ factor. Recent work shows how to use bounds in tail-size in order to solve this problem, and presents a new technique for applying cup games to external-memory data structures [10]. A key insight is that if a cup game has small tail size, then the water in “overflowed cups” (i.e., cups with fill more than $O(1)$) can be stored in a small in-memory cache. The result is that every cup consumes exactly $\Theta(1)$ blocks in external memory, meaning that each cup can be read/modified by the data structure in $O(1)$ I/Os. This insight was recently applied to external-memory dictionaries in order to eliminate flushing cascades in write optimized data structures [10].

The paper is structured as follows. Section 2 describes a new randomized algorithm that achieves small tail size without resource augmentation. Section 3 gives a technical overview of the algorithm’s analysis and of the other results in this paper. Section 4 then presents the full analysis of the algorithm and Section 5 presents (nearly) matching lower bounds. Finally, Section 6 gives lower bounds against unending guarantees and analyzes the amount of resource augmentation needed for such guarantees.

Although in principle an arbitrary constraint height $c$ can be used to determine which cups contribute to the tail size, all of the algorithms in this paper work with $c=2$. Thus, throughout the rest of the paper, we define the tail size to be the number of cups with height $2$ or greater.

As a convention, we say that an event occurs with high probability in $n$, if the event occurs with probability at least $1-\frac{1}{n^{c}}$ for an arbitrarily large constant $c$ of our choice. The constant $c$ is allowed to affect other constants in the statement. For example, an algorithm that achieves tail size $c\log n$ with probability $\frac{1}{n^{c}}$ is said to achieve tail size $O(\log n)$ with high probability in $n$.

At the beginning of the game, the emptier selects random offsets $r_{j}\in[0,1)$ independently and uniformly at random for each cup $j$. Prior to the game beginning, $r_{j}$ units of water are placed in each cup $j$. This water is for “bookkeeping” purposes only, and need not physically exist. During initialization, the emptier also assigns a random priority $p_{j}\in[0,1)$ independently and uniformly at random to each cup $j$.

After each step $t$, the emptier selects (up to) $p$ different cups to remove $1$ unit of water from as follows. If there are $p$ or more cups containing $2$ or more units of water, then the emptier selects the $p$ fullest such cups. Otherwise, the emptier selects all of the cups containing $2$ or more units of water, and then resorts to cups containing fill in $[1,2)$, choosing between these cups based on their priorities $p_{j}$ (i.e., choosing cups with larger priorities over those with smaller priorities). The emptier never removes water from any cup containing less than $1$ unit of water.

When discussing the algorithm, several additional definitions and conventions are useful. We say that threshold $(j,i)$ is crossed if cup $j$ contains at least $i$ units of water for positive integer $i$. When $i=1$, the threshold $(j,i)$ is called a light threshold, and otherwise $(j,i)$ is called a heavy threshold. One interpretation of the emptying algorithm is that there is a queue $Q$ of thresholds $(j,i)$ that are currently crossed. Whenever the filler places water into cups, this may add thresholds $(j,i)$ to the queue. And whenever the emptier removes water from some cup $j$, this removes some threshold $(j,i)$ from the queue. When selecting thresholds to remove from the queue, the emptier prioritizes heavy thresholds over light ones. Within the heavy thresholds, the emptier prioritizes based on cup height, and within the light thresholds the emptier prioritizes based on cup priorities $p_{j}$.

As a convention, we say that a cup $j$ is queued if $(j,1)$ is in $Q$ (or, equivalently, if $(j,i)$ is in the queue for any $i$). The emptier is said to dequeue cup $j$ whenever threshold $(j,1)$ is removed from the queue. The size of the queue $Q$ refers to the number of thresholds in the queue (rather than the number of cups).

At the heart of the analysis is what we call the unpredictability guarantee, which, roughly speaking, establishes that the filler cannot predict large sets of cups that will all be over-full at the same time as one-another. We show that if an algorithm satisfies a certain version of the unpredictability guarantee, along with certain natural “greedy-like” properties, then the algorithm is guaranteed to exhibit a small tail size.

Formally, we say that an emptying algorithm satisfies $R$-unpredictability at a step $t$ if for any oblivious filling algorithm, and for any set of cups $S$ whose size is a sufficiently large constant multiple of $R$, there is high probability in $n$ that at least one cup in $S$ has fill less than $1$ after step $t$. In other words, for any polynomial $f(n)$, there exists a constant $c$ such that: for each set $S\subseteq[n]$ of $cR$ cups, the probability that every cup in $S$ has height $1$ or greater at step $t$ is at most $1/f(n)$.

Rather than proving that $R$-unpredictability causes the tail size to stay small, we instead show the contrapositive. Namely, we show that if there is a filling strategy that achieves a large tail size, the strategy can be adapted to instead violate $R$-unpredictability.

Suppose that the filler is able to achieve tail size $cR$ at some step $t$, where $c$ is a large constant. Then during each of the next $cR$ steps, the emptier will remove water from cups containing fill $2$ or more (here, we use the crucial fact that the emptier always prioritizes cups with fills $2$ or greater over cups with fills smaller than $2$). This means that, during steps $t+1,\ldots,t+cR$, the set of cups with fill $1$ or greater is monotonically increasing. During these steps the filler can place $1$ unit of water into each of the cups $1,2,\ldots,cR$ in order to ensure that these cups all contain fill $1$ or greater after step $t+cR$. Thus the filler can transform the initial tail size of $cR$ into a large set of cups $S=\{1,2,\ldots,cR\}$ that all have fill $1$ or greater. In other words, any filling strategy for achieving large tail size (at some step $t$) can be harnessed to violate $R$-unpredictability (at some later step $t+cR$).

The directness of the argument above may seem to suggest that in order to prove the $R$-unpredictability, one must first (at least implicitly) prove a bound on tail size. A key insight in this paper is that the use of priorities in the asymmetric smoothed greedy algorithm allows for $R$-unpredictability to be analyzed as its own entity.

Our algorithm analysis establishes $\log n\log\log n$-unpredictability for the first $\operatorname{poly}n$ steps of any cup game, with high probability in $n$. This, in turn, implies a bound of $O(\log n\log\log n)$ on tail size.

We prove that, out of the roughly $n/2$ cups $j$ with priorities $p_{j}\geq 1/2$, at most $O(\log n\log\log n)$ of them are queued (i.e., contain fill $1$ or greater) at a time, with high probability in $n$. Recall that the cups with priority $p_{j}\geq 1/2$ are prioritized by the asymmetric smoothed greedy algorithm when the algorithm is choosing between cups with fills in the interval $[1,2)$. This preferential treatment does not extend the case where there are cups containing fill $\geq 2$, however. Remarkably, the limited preferential treatment exhibited by the algorithm is enough to ensure that the number of queued high-priority cups never exceeds $O(\log n\log\log n)$.

The bound of $O(\log n\log\log n)$ on the number of queued cups with priorities $\geq 1/2$ implies $\log n\log\log n$-unpredictability as follows. For any fixed set $S$ of cups, the number of cups $j$ in $S$ with priority $p_{j}\geq 1/2$ will be roughly $|S|/2$ with high probability in $n$. If $|S|/2$ is at least a sufficiently large constant multiple of $\log n\log\log n$, then the number of cups with $p_{j}\geq 1/2$ in $S$ exceeds the total number of cups with $p_{j}\geq 1/2$ that are queued. Thus $S$ must contain at least one non-queued cup, as required for the unpredictability guarantee.

In order to bound the number of queued cups with priority $p_{j}\geq 1/2$ by $O(\log n\log\log n)$, we partition the cups into $\Theta(\log\log n)$ priority levels based on their priorities $p_{j}$. Let $q$ be a sufficiently large constant multiple of $\log\log n$. The priority level of a cup $j$ is given by $\lfloor p_{j}\cdot q\rfloor+1$. (Note that the priority levels are only needed in the analysis, and the algorithm does not have to know $q$.) We show that with high probability in $n$, there are never more than $O(\log n\log\log n)$ queued cups with priority level $\geq q/2$. Note that, although we only care about bounding the number of queued whose priority-levels are in the top fifty percentile, our analysis will take advantage of the fact that the priorities $p_{j}$ are defined at a high granularity (rather than, for example, being boolean).

Bounding the number of queued cups with priority level greater than $\ell$ directly is difficult for the following reason: Over the course of a sequence of steps, the filler may cross many light thresholds cups with priority level greater than $\ell$, while the emptier only removes heavy thresholds from $Q$ (i.e., the emptier empties exclusively from cups of height $2$ or greater). This means that, in a given sequence of steps, the number of queued cups with priority level greater than $\ell$ could increase substantially. We call this the stalled emptier problem. Note that the stalled emptier problem is precisely what enables the connection between tail size and $R$-unpredictability above, allowing the filler to transform large tail size into a violation of $R$-unpredictability. As a result, any analysis that directly considers the stalled emptier problem must also first bound tail-size, bringing us back to where we started.

Rather than bounding the number of queued cups with priority level greater than $\ell$, we instead compare the number of queued cups at priority level greater than $\ell$ to the number at priority level $\ell$. The idea is that, if the stalled-emptier problem allows for the number of queued priority-level greater than $\ell$ to grow large, then it will allow for the number of queued priority-level-$\ell$ cups to grow even larger. That is, without proving any absolute bound on the number of cups at a given priority level, we can still say something about the ratio of high-priority cups to low-priority cups in the queue.

To be precise, we prove that, whenever there are $k$ queued cups at some priority level $\ell$, there are at most $O(\sqrt{qk\log n}+\log n)$ queued cups at priority level $>\ell$ (recall that $q=\Theta(\log\log n)$ is the number of priority levels). Since the number of cups with priority level at least $1$ is deterministically anchored at $n$, this allows for us to inductively bound the number of queued cups with large priority levels $\ell$. In particular, the number of queued cups at priority level $q/2$ or greater never exceeds $O(\log n\log\log n)$.

Suppose that after some step $t$, there are some large number $k$ of queued cups with priority level $\geq\ell$. We wish to show that almost all of these $k$ cups have priority level exactly $\ell$.

Before describing our approach in detail (which we do in the following two subheaders), we give an informal description of the approach. Let $k_{1}$ be number of priority-level-$\ell$ queued cups, and let $k_{2}$ be the number of priority-level-greater-than-$\ell$ queued cups. The only way that there can be a large number $k_{2}$ of priority-level-greater-than-$\ell$ cups queued is if they have all entered the queue since the last time that a level-$\ell$ cup was dequeued. This means that the size of $Q$ has increased by at least $k_{2}$ since the last time that a priority-level-$\ell$ cup was dequeued. On the other hand, we show that priority-level-$\ell$ cups accumulate in $Q$ at a much faster rate than the size of $Q$ varies. In particular, we show that both the rate at which priority-level $\ell$ cups accumulate in $Q$ and the rate at which $Q$’s size varies are controlled by what we call the “influence” of a time-interval, and that the former is always much larger than the latter. This ensures that $k_{1}\gg k_{2}$.

Note that the analysis avoids arguing directly the number of queued high-priority cups small, which could be difficult due to the stalled emptier problem. Intuitively, the analysis instead shows that low priority cups do a good job “pushing” the high priority cups out of the queue, ensuring that the ratio of low-priority cups (i.e., cups with priority level $\ell$) to high-priority cups (i.e. cups with priority level $>\ell$) is always very large.

Let $t_{0}$ be the most recent step $t_{0}\leq t$ such that at least $k+1$ distinct cups $C$ with priority level $\ell$ cross thresholds during steps $t_{0},\ldots,t$. (Recall that $k$ is the number of queued cups with priority level $\geq\ell$ after step $t$.) One can think of the steps $t_{0},\ldots,t$ as representing a long period of time in which many cups with priority level $\ell$ have the opportunity to accumulate in $Q$. We will now show that the use of priorities in the asymmetric smoothed greedy algorithm causes the following property to hold: The number of queued cups with priority level $>\ell$ after step $t$ is bounded above by the amount that $|Q|$ varies during steps $t_{0},\ldots,t$.

Because $Q$ contains only $k$ queued cups with priority level $\geq\ell$ after step $t$, at least one cup from $C$ must be dequeued during steps $t_{0},\ldots,t$ (otherwise, $Q$ would contain at least $|C|=k+1$ level-$\ell$ cups after step $t$). Let $t^{*}$ be the final step in $t_{0},\ldots,t$ out of those that dequeue a cup with priority level $\leq\ell$, and let $Q_{t^{*}}$ and $Q_{t}$ denote the queue after steps $t^{*}$ and $t$, respectively.

By design, the only way that the asymmetric smoothed greedy algorithm can dequeue a cup with priority level $\leq\ell$ at step $t^{*}$ is if the queue $Q_{t^{*}}$ consists exclusively of light thresholds (i.e., thresholds of the form $(j,1)$) for cups $j$ with priority level $\leq\ell$. Moreover, the thresholds in $Q_{t^{*}}$ must remain present in $Q_{t}$, since by the definition of $t^{*}$ no cups with priority level $\leq\ell$ are dequeued during steps $t^{*}+1,\ldots,t$.

Since $Q_{t^{*}}\subseteq Q_{t}$ and $Q_{t^{*}}$ contains only thresholds for cups with priority level $\leq\ell$, the total number of thresholds in $Q_{t}$ for cups with priority level $>\ell$ is at most $|Q_{t}|-|Q_{t^{*}}|$. In other words, the only way that a large number of cups with priority level $>\ell$ can be queued after step $t$ is if the size of $Q$ varies by a large amount during steps $t_{0},\ldots,t$.

Although $t-t_{0}$ may be very large compared to $k$ (e.g. $\operatorname{poly}n$) we show that the amount by which $|Q|$ varies during steps $t_{0},\ldots,t$ is guaranteed to be small as a function of $k$, bounded above by $O(\sqrt{kq\log n})$. This means that, out of the $k$ cups with priority level $\geq\ell$ in $Q_{t}$, at most $O(\sqrt{kq\log n})$ of them can have priority level $\ell+1$ or larger.

The main tool in order to analyze the rate at which $Q$’s size varies is to analyze sequences of steps based on their influence. For sequence of steps $I$, the influence of $I$ is defined to be $\sum_{j=1}^{n}\min(1,c_{j}(I))$, where $c_{j}(I)$ is the amount of water poured into each cup $j$ during interval $I$. We show that, for any priority level $\ell$ and for any step interval $I$ with influence $2rq$ for some $r$, either $r=O(\log n)$, or two important properties are guaranteed to hold with high probability:

• •

  Step interval $I$ crosses thresholds in at least $r$ cups with priority level $\ell$. This is true of any interval $I$ with influence at least $2qr$ by a simple concentration-bound argument.

• •

  The size of $Q$ varies by at most $O(\sqrt{qr\log n})$ during step interval $I$

  The key here is to show that, during each subinterval $I^{\prime}\subseteq I$, the number of thresholds crossed by the filler is within $O(\sqrt{qr\log n})$ of $|I^{\prime}|$. In order to do this, we take advantage of the initial random offsets $r_{j}$ that are placed into each cup by the algorithm. If the filler puts some number $c_{j}(I^{\prime})$ of units of water into a cup $j$ during $I^{\prime}$, then the cup $j$ will deterministically cross $\lfloor c_{j}(I^{\prime})\rfloor$ thresholds, and with probability $c_{j}(I^{\prime})-\lfloor c_{j}(I^{\prime})\rfloor$ will cross one additional threshold (with the outcome depending on the random value $r_{j}$). Since the influence of $I^{\prime}$ is at most $2rq$, we know that $\sum_{j}(c_{j}(I^{\prime})-\lfloor c_{j}(I^{\prime})\rfloor)\leq 2rq$. That is, if we consider only the threshold crossings that are not certain, then the number of them is a sum of independent 0-1 random variables with mean at most $2rq$. By a Chernoff bound, this number varies from its mean by at most $O(\sqrt{qr\log n})$, with high probability in $n$.

Combined, we call these the influence property. By a union bound, the influence property holds with high probability on all sub-sequences of steps during the cup game, and for all values $r$.

The influence property creates a link between the number of cups with priority level $\ell$ that cross thresholds during a sequence of steps $I$, and the amount by which $|Q|$ varies during steps $I$. Applying this link with $r=k+1$ to steps $t_{0},\ldots,t$, as defined above, implies that $|Q|$ varies by at most $O(\sqrt{qk\log n})$ during steps $t_{0},\ldots,t$. This, in turn, bounds the number of queued cups with priority level $\ell+1$ or larger by $O(\sqrt{qk\log n})$ after step $t$, completing the analysis.

The primary difficulty in analyzing the multi-processor cup game (i.e., when $p>1$) is that the emptier must remove water from $p$ different cups, even if almost all of the water in the system resides in fewer than $p$ cups. For example, the emptier may dequeue a cup $j$ even though there are up to $p-1$ other higher-priority cups that are still queued; furthermore, each of these higher-priority cups may contribute a large number of heavy thresholds to the queue $Q$.

We solve this issue by leveraging recent bounds on backlog for the $p$-processor cup game [28], which prove that the deterministic greedy emptying algorithm achieves backlog $O(\log n)$. This can be used to ensure that, for any $p-1$ cups that are queued, each of them can only contribute a relatively small number of thresholds to the queue $Q$. These “miss-behaving” thresholds can then be absorbed into the algorithm analysis.

Our lower-bound constructions extend the techniques used in past works for backlog [28, 11, 19] in order to apply similar ideas to tail size. One of the surprising features of our lower bounds is that they continue to be nearly tight even in the multi-processor case — the same is not known to be true for backlog. We defer further discussion of the lower bounds to Section 5.

Finally, we consider the question of whether the analysis of the asymmetric smoothed greedy algorithm can be extended to offer an unending guarantee, i.e., a guarantee that for any step $t$, no matter how large, there a high probability at step $t$ that the backlog and tail size are small.

We show that, without the use of resource augmentation, unending guarantees are not possible for the asymmetric smoothed greedy algorithm, or, more generally, for any monotone memoryless emptying algorithm. Lower bounds against unending guarantees have previously been shown for the multi-processor cup game [28], but remained open for the single-processor cup game.

The filling strategy, which we call the fuzzing algorithm, has a very simple structure: the filler spends a large number (i.e., $n^{\tilde{\Theta}(n)}$) of steps randomly placing water in multiples of $1/2$ into cups $1,2,\ldots,n$. The filler then disregards a random cup, which for convenience we will denote by $n$, and spends a large number of steps randomly placing water into the remaining cups $1,2,\ldots,n-1$. The filler then disregards another random cup, which we will call cup $n-1$ ,and spends a large number of steps randomly placing water into cups $1,2,\ldots,n-2$, and so on. We call the portion of the algorithm during which the filler is focusing on cups $1,2,\ldots,i$ the $i$-cup phase.

Rather than describe the analysis of the fuzzing algorithm (which is somewhat complicated), we instead give an intuition for why the algorithm works. For simplicity, suppose the emptier follows the (standard) smoothed greedy emptying algorithm.

Between the $i$-cup phase and the $(i-1)$-cup phase, the filler disregards a random cup (that we subsequently call cup $i$). Intuitively, at the time that cup $i$ is discarded, there is a roughly $50\%$ chance that cup $i$ has more fill than the average of cups $1,2,\ldots,i$. Then, during the $(i-1)$-cup phase, there is a reasonably high probability that the filler at some point manages to make all of cups $1,2,\ldots,i-1$ have almost equal fills to one-another. At this point, the emptier will choose to empty out of cup $i$ instead of cups $1,2,\ldots,i-1$. The fact that the emptier neglects cups $1,2,\ldots,i-1$ during the step, even though the filler places $1$ unit of water into them, causes their average fill to increase by $1/(i-1)$. Since this happens with constant probability in every phase, the result is that, by the beginning of the $\sqrt{n}$-cup phase there are $\sqrt{n}$ cups each with expected fill roughly

Formalizing this argument leads to several interesting technical problems. Most notably, the cups $1,2,\ldots,i-1$ having almost equal fills (rather than exactly equal fills) may not be enough for cup $i$ to receive the emptier’s attention. Moreover, if we wish to analyze the asymmetric smoothed greedy algorithm or, more generally, the class of monotone memoryless algorithms, then cups are not necessarily judged by the emptying algorithm based on their fill heights, and may instead be selected based on an essentially arbitrary objective function that need not treat cups symmetrically. These issues are handled in Section 6 by replacing the notion of cups $1,2,\ldots,i-1$ having almost equal fills as each other with the notion of cups $1,\ldots,i-1$ reaching a certain type of specially designed equilibrium state that interacts well with the emptier.