We study comparison sorting in the evolving data model, introduced by Anagnostopoulos, Kumar, Mah-dian and Upfal (2011), where the true total order changes while the sorting algorithm is processing the input. More precisely, each comparison operation of the algorithm is followed by a sequence of evolution steps, where an evolution step perturbs the rank of a random item by a “small” random value. The goal is to maintain an ordering that remains close to the true order over time. Previous works have analyzed adaptations of classic sorting algorithms, assuming that an evolution step changes the rank of an item by just one, and that a fixed constant number$b$of evolution steps take place between two comparisons. In fact, the only previous result achieving optimal linear total deviation, by Besa Vial, Devanny, Eppstein, Goodrich and Johnson (2018a), applies just for$b=1$. We analyze a very simple sorting algorithm suggested by Mahdian (2014), which samples a random pair of adjacent items in each step and swaps them if they are out of order. We show that the algorithm achieves and maintains, with high probability, optimal total deviation,$O(n)$, and optimal maximum deviation,$O(\log n)$, under very general model settings. Namely, the perturbation introduced by each evolution step is sampled from a general distribution of bounded moment generating function, and we just require that the average number of evolution steps between two sorting steps be bounded by an (arbitrary) constant, where the average is over a linear number of steps. The key ingredients of our proof are a novel potential function argument that inserts “gaps” in the list of items, and a general analysis framework which separates the analysis of sorting from that of the evolution steps, and is applicable to a variety of settings for which previous approaches do not apply. Our results settle conjectures and open problems in the three aforementioned works, and provide theoretical support that simple quadratic algorithms are optimal and robust for sorting evolving data, as empirically observed by Besa Vial, Devanny, Eppstein, Goodrich and Johnson (2018b).

Abstract. We introduce a new class of balanced allocation processes which are primarily characterized by “filling” underloaded bins. A prototypical example is the Packing process: At each round we only take one bin sample, and if the load is below the average load, then we place as many balls until the average load is reached; otherwise, we place only one ball. We prove that for any process in this class the gap between the maximum and average load is [Formula: see text] w.h.p. for any number of balls [Formula: see text]. For the Packing process, we also provide a matching lower bound. Additionally, we prove that the Packing process is sample efficient in the sense that the expected number of balls allocated per sample is strictly greater than one. Finally, we also demonstrate that the upper bound of [Formula: see text] on the gap can be extended to the Memory process studied by Mitzenmacher, Prabhakar, and Shah [43 rd Annual IEEE Symposium on Foundations of Computer Science, Vancouver, BC, Canada, 2002, pp. 799–808].

In the balanced allocations framework, there are \(m\) jobs (balls) to be allocated to \(n\) servers (bins). The goal is to minimize the gap , the difference between the maximum and the average load. In 2015, Peres, Talwar and Wieder used the hyperbolic cosine potential function to analyze the challenging case where \(m\gg n\) , for a large family of processes, including the \((1+\beta)\) -process and graphical balanced allocations. The key ingredient was to prove that the potential drops in every step, i.e., a drift inequality . In this work, we improve the drift inequality so that (i) it is asymptotically tight (leading to tighter gap bounds), (ii) it assumes weaker preconditions (thereby resolving an open problem regarding weighted graphical allocations), (iii) it applies not only to processes allocating to more than one bin in a single step but also (iv) to processes allocating a varying number of balls depending on the sampled bin. Our applications include the aforementioned large family of processes, and also several new processes and settings, including outdated information and memory. We hope that our techniques can be used to analyze further interesting settings and processes.

We consider the allocation of m balls (jobs) into n bins (servers). In the standard TWO-CHOICE process, at each step t = 1, 2,…, m we first sample two bins uniformly at random and place a ball in the least loaded bin. It is well-known that for any m  n, this results in a gap (difference between the maximum and average load) of log2 log n + θ(1) (with high probability). In this work, we consider the MEMORY process [27] where instead of two choices, we only sample one bin per step but we have access to a cache which can store the location of one bin. Mitzenmacher, Prabhakar and Shah [23] showed that in the lightly loaded case (m = n), the MEMORY process achieves a gap of

In the balanced allocation framework, the goal is to allocate m balls into n bins, so as to minimize the gap (difference of maximum to average load). The One-Choice process allocates each ball to a bin sampled independently and uniformly at random. The Two-Choice process allocates balls sequentially, and each ball is placed in the least loaded of two sampled bins. Finally, the (1+β)-process mixes these processes, meaning each ball is allocated using Two-Choice with probability β in (0,1), and using One-Choice otherwise. Despite Two-Choice being optimal in the sequential setting, it has been observed in practice that it does not perform well in a parallel environment, where load information may be outdated. Following [BCEFN12], we study such a parallel setting where balls are allocated in batches of size b, and balls within the same batch are allocated with the same strategy and based on the same load information. For small batch sizes b in [n, n log n], it was shown in [LS22c] that Two-Choice achieves an asymptotically optimal gap among all allocation processes with two (or any constant number of) samples. In this work, we focus on larger batch sizes b in [n log n, n³]. It was proved in [LS22a] that Two-Choice leads to a gap of Θ(b/n). As our main result, we prove that the gap reduces to O(√((b/n) log n)), if one runs the (1+β)-process with an appropriately chosen β (in fact this result holds for a larger class of processes). This not only proves the phenomenon that Two-Choice is not the best (leading to the formation of "towers" over previously light bins), but also that mixing two processes (One-Choice and Two-Choice) leads to a process which achieves a gap that is asymptotically smaller than both. We also derive a matching lower bound of Ω(√((b/n) log n)) for any allocation process, which demonstrates that the above (1+β)-process is asymptotically optimal. Our analysis also works in the presence of randomly weighted balls, and also implies exponential tails for the number of bins above a certain load value.

We study the repeated balls-into-bins process introduced by Becchetti, Clementi, Natale, Pasquale and Posta (2019). This process starts with m balls arbitrarily distributed across n bins. At each round t = 1,2,…, one ball is selected from each non-empty bin, and then placed it into a bin chosen independently and uniformly at random. We prove the following results: - For any n ⩽ m ⩽ poly(n), we prove a lower bound of Ω(m/n ⋅ log n) on the maximum load. For the special case m = n, this matches the upper bound of 𝒪(log n), as shown in [Luca Becchetti et al., 2019]. It also provides a positive answer to the conjecture in [Luca Becchetti et al., 2019] that for m = n the maximum load is ω(log n/ log log n) at least once in a polynomially large time interval. For m ∈ [ω(n), n log n], our new lower bound disproves the conjecture in [Luca Becchetti et al., 2019] that the maximum load remains 𝒪(log n). - For any n ⩽ m ⩽ poly(n), we prove an upper bound of 𝒪(m/n ⋅ log n) on the maximum load for all steps of a polynomially large time interval. This matches our lower bound up to multiplicative constants. - For any m ⩾ n, our analysis also implies an 𝒪(m²/n) waiting time to reach a configuration with a 𝒪(m/n ⋅ log m) maximum load, even for worst-case initial distributions. - For m ⩾ n, we show that every ball visits every bin in 𝒪(m log m) rounds. For m = n, this improves the previous upper bound of 𝒪(n log² n) in [Luca Becchetti et al., 2019]. We also prove that the upper bound is tight up to multiplicative constants for any n ⩽ m ⩽ poly(n).

We consider the allocation of m balls (jobs) into n bins (servers). In the standard Two-Choice process, at each step t =1,2,... ,m we first sample two randomly chosen bins, compare their two loads and then place a ball in the least loaded bin. It is well-known that for any m ⩾ n , this results in a gap (difference between the maximum and average load) of log 2 log n + Θ (1) (with high probability). In this work, we consider Two-Choice in different settings with noisy load comparisons. One key setting involves an adaptive adversary whose power is limited by some threshold \(g \in \mathbb {N}\) . In each step, such adversary can determine the result of any load comparison between two bins whose loads differ by at most g , while if the load difference is greater than g , the comparison is correct. For this adversarial setting, we first prove that for any m ⩾ n the gap is \(\mathcal {O}(g+\log n)\) with high probability. Then through a refined analysis we prove that if g ⩽ log n , then for any m ⩾ n the gap is \(\mathcal {O}(\frac{g}{\log g} \cdot \log \log n)\) . For constant values of g , this generalizes the heavily loaded analysis of [ 19 , 61 ] for the Two-Choice process, and establishes that asymptotically the same gap bound holds even if load comparisons among “similarly loaded” bins are wrong. Finally, we complement these upper bounds with tight lower bounds, which establish an interesting phase transition on how the parameter g impacts the gap. The analysis also applies to settings with outdated and delayed information. For example, for the setting of [ 18 ] where balls are allocated in consecutive batches of size \(b = n\) , we present an improved and tight gap bound of \(\Theta (\frac{\log n}{\log \log n})\) . This bound also extends for a range of values of b and applies to a relaxed setting where the reported load of a bin can be any load value from the last b steps.

We consider the sequential allocation of m balls (jobs) into n bins (servers) by allowing each ball to choose from some bins sampled uniformly at random. The goal is to maintain a small gap between the maximum load and the average load. In this paper, we present a general framework that allows us to analyze various allocation processes that slightly prefer allocating into underloaded, as opposed to overloaded bins. Our analysis covers several natural instances of processes, including: The Caching process (a.k.a. memory protocol) as studied by Mitzenmacher, Prabhakar and Shah (2002). The Packing process: At each round we only take one bin sample. If the load is below some threshold (e.g., the average load), then we place as many balls until the threshold is reached; otherwise, we place only one ball. The Twinning process: At each round, we only take one bin sample. If the load is below some threshold, then we place two balls; otherwise, we place only one ball. The Thinning process as recently studied by Feldheim and Gurel-Gurevich (2021). As we demonstrate, using an interplay between several potential functions our general framework implies for all these processes a gap of O(log n) for any number of balls m ≥ n.

We study the repeated balls-into-bins process introduced by Becchetti, Clementi, Natale, Pasquale and Posta [3]. This process starts with m balls arbitrarily distributed across n bins. At each step t = 1, 2, . . ., we select one ball from each non-empty bin, and then place it into a bin chosen independently and uniformly at random. We prove the following results:

We consider the allocation of $m$ balls (jobs) into $n$ bins (servers). In the Two-Choice process, for each of $m$ sequentially arriving balls, two randomly chosen bins are sampled and the ball is placed in the least loaded bin. It is well-known that the maximum load is $m/n+\log_2 \log n + O(1)$ w.h.p. Berenbrink, Czumaj, Englert, Friedetzky and Nagel (2012) introduced a parallel version of this process, where $m$ balls arrive in consecutive batches of size $b=n$ each. Balls within the same batch are allocated in parallel, using the load information of the bins at the beginning of the batch. They proved that the gap of this process is $O(\log n)$ with high probability. In this work, we present a new analysis of this setting, which is based on exponential potential functions. This allows us to both simplify and generalize the analysis of [BCE12] in different ways: $\quad 1.$ Our analysis covers a broad class of processes. This includes not only Two-Choice, but also processes with fewer bin samples like $(1+\beta)$, processes which can only receive one bit of information from each bin sample and graphical allocation, where bins correspond to vertices in a graph. $\quad 2.$ Balls may be of different weights, as long as their weights are independent samples from a distribution satisfying a technical condition on its moment generating function. $\quad 3.$ For arbitrary batch sizes $b \geq n$, we prove a gap of $O(b/n \cdot \log n)$. For any $b \in [n , n^3]$, we improve this to $O(b/n + \log n)$ and show that it is tight for a family of processes. This implies the unexpected result that for e.g. $(1+\beta)$ with constant $\beta \in (0, 1]$, the gap is $\Theta(\log n)$ for all $b \in [n,n \log n]$. We also conduct experiments which support our theoretical results, and even hint at a superiority of less powerful processes like $(1+\beta)$ for large batch sizes.