Dimitrios Los

I am a 4th year PhD student supervised by Prof Thomas Sauerwald and I am mostly working on randomised algorithms for load balancing. I am a member of St John's college, which together with Cambridge Trust, is funding my PhD.

Publications

• Balanced Allocations in Batches: The Tower of Two Choices [ SPAA 2023 ][ doi ][ arXiv ][ Abstract ][ code ]
  joint work with Thomas Sauerwald

  In the balanced allocations framework, the goal is to allocate \(m\) balls into \(n\) bins, so as to minimize the gap (difference of maximum to average load). The \({\rm O{\small NE}\text{-}C{\small HOICE}}\) process allocates each ball to a randomly sampled bin and achieves w.h.p. a \(\Theta(\sqrt{(m/n) \cdot \log n})\) gap. The \({\rm T{\small WO}\text{-}C{\small HOICE}}\) process allocates to the least loaded of two randomly sampled bins, and achieves w.h.p. a \(\log_2 \log n + \Theta(1)\) gap. Finally, the \((1+\beta)\) process mixes between these two processes with probability \(\beta \in (0, 1)\), and achieves w.h.p. an \(\Theta(\log n/\beta)\) gap.

  We focus on the outdated information setting of Berenbrink, Czumaj, Englert, Friedetzky and Nagel (2012), where balls are allocated in batches of size \(b\). For almost the entire range \(b \in [1,\mathcal{O}(n \log n)]\), it was shown in [LS22a] that \({\rm T{\small WO}\text{-}C{\small HOICE}}\) achieves w.h.p. the asymptotically optimal gap and for \(b = \Omega(n\log n)\) it was shown in [LS22b] that it achieves w.h.p. a \(\Theta(b/n)\) gap.

  In this work, we establish that the \((1+\beta)\) process for appropriately chosen \(\beta\), achieves w.h.p. the asymptotically optimal gap of \(\mathcal{O}(\sqrt{(b/n) \cdot \log n})\) for any \(b \in [2n \log n, n^3]\). This not only proves the surprising phenomenon that allocating greedily based on \({\rm T{\small WO}\text{-}C{\small HOICE}}\) is not the best, but also that mixing two processes (\({\rm O{\small NE}\text{-}C{\small HOICE}}\) and \({\rm T{\small WO}\text{-}C{\small HOICE}}\)) leads to a process with a gap that is better than both. Furthermore, the upper bound on the gap applies to a larger family of processes and continues to hold in the presence of weights sampled from distributions with bounded MGFs.

• Balanced Allocations with Heterogeneous Bins: The Power of Memory [ SODA 2023 ][ doi ][ arXiv ][ Abstract ][ visualisations ]
  joint work with Thomas Sauerwald and John Sylvester

  We consider the allocation of \(m\) balls (jobs) into \(n\) bins (servers). In the standard \({\rm T{\small WO}\text{-}C{\small HOICE}}\) process, at each step \(t=1,2,\ldots,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 \geq n\), this results in a gap (difference between the maximum and average load) of \(\log_2 \log n + \Theta(1)\) (with high probability). In this work, we consider the memory process by Shah and Prabhakar (2002) 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 (2002) showed that in the lightly loaded case (\(m = n\)), the memory process achieves a gap of \(\mathcal{O}(\log \log n)\).

  Extending the setting of [MPS02] in two ways, we first allow the number of balls \(m\) to be arbitrary, which includes the challenging heavily loaded case where \(m \geq n\). Secondly, we follow the heterogeneous bins model of Wieder (2007), where the sampling distribution of bins can be biased up to some arbitrary multiplicative constant. Somewhat surprisingly, we prove that even in this setting, the memory process still achieves a \(\mathcal{O}(\log \log n)\) gap bound. This is in stark contrast with the \({\rm T{\small WO}\text{-}C{\small HOICE}}\) (or any \(d{\rm \text{-}C{\small HOICE}}\) with \(d=\mathcal{O}(1)\)) process, where it is known that the gap diverges [W07]. Finally, we prove a tight gap bound of \(\mathcal{O}(\log n)\) for memory in another relaxed setting with heterogeneous (weighted) balls and a cache which can only be maintained for two steps.

• Balanced Allocations with the Choice of Noise [ PODC 2022 - Best Student Paper Award ][ doi ][ arXiv ][ Abstract ][ visualisations ][ code ]
  joint work with Thomas Sauerwald

  We consider the allocation of \(m\) balls (jobs) into \(n\) bins (servers). In the standard \({\rm T{\small WO}\text{-}C{\small HOICE}}\) process, at each step \(t=1,2,\ldots,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 \geq n\), this results in a gap (difference between the maximum and average load) of \(\log_2 \log n + \Theta(1)\) (with high probability).

  In this work, we consider \({\rm T{\small WO}\text{-}C{\small HOICE}}\) in different models with noisy load comparisons. One key model involves an adaptive adversary whose power is limited by some threshold \(g \in \mathbb{N}\). In each round, 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 model, we first prove that for any \(m \geq n\) the gap is \(O(g+\log n)\) with high probability. Then through a refined analysis we prove that if \(g \leq \log n\), then for any \(m \geq 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 Berenbrink, Czumaj, Steger and Vöcking (2006) and of Talwar and Wieder (2014) for the \({\rm T{\small WO}\text{-}C{\small HOICE}}\) process, and establishes that asymptotically the same gap bound holds even if many (or possibly all) load comparisons among "similarly loaded" bins are wrong. Finally, we complement these upper bounds with tight lower bounds, which establishes an interesting phase transition on how the parameter \(g\) impacts the gap.

  We also apply a similar analysis to other noise models, including ones where bins only update their load information with delay. For example, for the model of Berenbrink, Czumaj, Englert, Friedetzky and Nagel (2012), where balls are allocated in consecutive batches of size \(n\), we present an improved and tight gap bound of \(\Theta(\log n/ \log \log n )\).

• Balanced Allocations in Batches: Simplified and Generalized [ SPAA 2022 ][ doi ][ arXiv ][ Abstract ][ visualisations ][ code ]
  joint work with Thomas Sauerwald

  We consider the allocation of \(m\) balls (jobs) into \(n\) bins (servers). In the \({\rm T{\small WO}\text{-}C{\small HOICE}}\) 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 + \mathcal{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 \(\mathcal{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 [BCEFN12] in different ways:

  1. Our analysis covers a broad class of processes. This includes not only \({\rm T{\small WO}\text{-}C{\small HOICE}}\), 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.
  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.
  3. For arbitrary batch sizes \(b \geq n\), we prove a gap of \(\mathcal{O}(b/n \cdot \log n)\). For any \(b \in [n , n^3]\), we improve this to \(\mathcal{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.
• Tight Bounds for Repeated Balls-into-Bins [ STACS 2023 ][ doi ][ arXiv ][ Abstract ][ visualisations ][ code ]
  joint work with Thomas Sauerwald

  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 step \(t=1,2,\ldots\), 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:

  • For any \(n \leq m \leq \mathrm{poly}(n)\), we prove a lower bound of \(\Omega(m/n \cdot \log n)\) on the maximum load. For the special case \(m=n\), this matches the upper bound of \(\mathcal{O}(\log n)\), as shown in [BCNPP19]. It also provides a positive answer to the conjecture in [BCNPP19] that for \(m=n\) the maximum load is \(\omega(\log n/ \log \log n)\) in a polynomially large window. For \(m \in [\omega(n), n \log n]\), our new lower bound disproves the conjecture in [BCNPP19] that the maximum load remains \(\mathcal{O}(\log n)\).
  • For any \(n \leq m \leq \mathrm{poly}(n)\), we prove an upper bound of \(\mathcal{O}(m/n \cdot \log n)\) on the maximum load for a polynomially large window. This matches our lower bound up to multiplicative constants.
  • For any \(m \geq n\), our analysis also implies an \(\mathcal{O}(m^2 / n)\) waiting time to a configuration with \(\mathcal{O}(m/n \cdot \log m)\) maximum load, even for worst-case initial distributions.
  • For \(m \geq n\), we show that every ball visits every bin in \(\mathcal{O}(m \log m)\) steps. For \(m = n\), this improves the previous upper bound of \(\mathcal{O}(n \log^2 n)\) in [BCNPP19]. We also prove that the upper bound is tight up to multiplicative constants for any \(n \leq m \leq \mathrm{poly}(n)\).
  • Brief Announcement: Tight Bounds for Repeated Balls-into-Bins [ SPAA 2022 ][ doi ][ Abstract ]
    joint work with Thomas Sauerwald

    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 step \(t=1,2,\ldots\), 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:

    • For any \(n \leq m \leq \mathrm{poly}(n)\), we prove a lower bound of \(\Omega(m/n \cdot \log n)\) on the maximum load. For the special case \(m=n\), this matches the upper bound of \(\mathcal{O}(\log n)\), as shown in [BCNPP19]. It also provides a positive answer to the conjecture in [BCNPP19] that for \(m=n\) the maximum load is \(\omega(\log n/ \log \log n)\) in a polynomially large window. For \(m \in [\omega(n), n \log n]\), our new lower bound disproves the conjecture in [BCNPP19] that the maximum load remains \(\mathcal{O}(\log n)\).
    • For any \(n \leq m \leq \mathrm{poly}(n)\), we prove an upper bound of \(\mathcal{O}(m/n \cdot \log n)\) on the maximum load for a polynomially large window. This matches our lower bound up to multiplicative constants.
    • For any \(m \geq n\), our analysis also implies an \(\mathcal{O}(m^2 / n)\) waiting time to a configuration with \(\mathcal{O}(m/n \cdot \log m)\) maximum load, even for worst-case initial distributions.
    • For \(m \geq n\), we show that every ball visits every bin in \(\mathcal{O}(m \log m)\) steps. For \(m = n\), this improves the previous upper bound of \(\mathcal{O}(n \log^2 n)\) in [BCNPP19]. We also prove that the upper bound is tight up to multiplicative constants for any \(n \leq m \leq \mathrm{poly}(n)\).
• Balanced Allocations: Caching and Packing, Twinning and Thinning [ SODA 2022 ][ doi ][ arXiv ][ Abstract ][ visualisations ]
  joint work with Thomas Sauerwald and John Sylvester

  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 \({\rm C{\small ACHING}}\) process (a.k.a. memory protocol) as studied by Mitzenmacher, Prabhakar and Shah (2002): At each round we only take one bin sample, but we also have access to a cache in which the most recently used bin is stored. We place the ball into the least loaded of the two.
  • The \({\rm P{\small ACKING}}\) 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 \({\rm T{\small WINNING}}\) 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 \({\rm T{\small HINNING}}\) process as recently studied by Feldheim and Gurel-Gurevich (2021): At each round, we first take one bin sample. If its load is below some threshold, we place one ball; otherwise, we place one ball into a second bin sample.

  As we demonstrate, our general framework implies for all these processes a gap of \(\mathcal{O}(\log n)\) between the maximum load and average load, even when an arbitrary number of balls \(m \geq n\) are allocated (heavily loaded case). Our analysis is inspired by a previous work of Peres, Talwar and Wieder (2010) for the \((1+\beta)\)-process, however here we rely on the interplay between different potential functions to prove stabilization.

  • The Power of Filling in Balanced Allocations [ arXiv ][ Abstract ]
    joint work with Thomas Sauerwald and John Sylvester Expands some of the results in "Balanced Allocations: Caching and Packing, Twinning and Thinning".

    It is well known that if \(m\) balls (jobs) are placed sequentially into \(n\) bins (servers) according to the \({\rm O{\small NE}\text{-}C{\small HOICE}}\) protocol — choose a single bin in each round and allocate one ball to it — then, for \(m \gg n\), the gap between the maximum and average load diverges. Many refinements of the \({\rm O{\small NE}\text{-}C{\small HOICE}}\) protocol have been studied that achieve a gap that remains bounded by a function of \(n\), for any \(m\). However most of these variations, such as \({\rm T{\small WO}\text{-}C{\small HOICE}}\), are less sample-efficient than \({\rm O{\small NE}\text{-}C{\small HOICE}}\), in the sense that for each allocated ball more than one sample is needed (in expectation).

    We introduce a new class of processes which are primarily characterized by "filling" underloaded bins. A prototypical example is the \(\rm P{\small ACKING}\) process: At each round we only take one bin sample, 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 \(\mathcal{O}(\log n)\) for any number of balls \(m\). For the Packing process, we also prove a matching lower bound. We also prove that the \(\rm P{\small ACKING}\) process is more sample-efficient than \({\rm O{\small NE}\text{-}C{\small HOICE}}\), that is, it allocates on average more than one ball per sample. Finally, we also demonstrate that the upper bound of \(\mathcal{O}(\log n)\) on the gap can be extended to the \({\rm C{\small ACHING}}\) process (a.k.a. memory protocol) studied by Mitzenmacher, Prabhakar and Shah (2002).

• Balanced Allocations with Incomplete Information: The Power of Two Queries [ ITCS 2022 ][ doi ][ arXiv ][ Abstract ][ visualisations ]
  joint work with Thomas Sauerwald

  We consider the allocation of \(m\) balls into \(n\) bins with incomplete information. In the classical \({\rm T{\small WO}\text{-}C{\small HOICE}}\) process a ball first queries the load of two randomly chosen bins and is then placed in the least loaded bin. In our setting, each ball also samples two random bins but can only estimate a bin's load by sending binary queries of the form "Is the load at least the median?" or "Is the load at least 100?".

  For the lightly loaded case \(m=O(n)\), Feldheim and Gurel-Gurevich (2021) showed that with one query it is possible to achieve a maximum load of \(O(\sqrt{\log n/\log \log n})\), and posed the question whether a maximum load of \(m/n+\mathcal{O}(\sqrt{\log n/\log \log n})\) is possible for any \(m = \Omega(n)\). In this work, we resolve this open problem by proving a lower bound of \(m/n+\Omega( \sqrt{\log n})\) for a fixed \(m=\Theta(n \sqrt{\log n})\), and a lower bound of \(m/n+\Omega(\log n/\log \log n)\) for some \(m\) depending on the used strategy. We complement this negative result by proving a positive result for multiple queries. In particular, we show that with only two binary queries per chosen bin, there is an oblivious strategy which ensures a maximum load of \(m/n+O(\sqrt{\log n})\) for any \(m \geq 1\). Further, for any number of \(k = \mathcal{O}(\log \log n)\) binary queries, the upper bound on the maximum load improves to \(m/n + \mathcal{O}(k(\log n)^{1/k})\) for any \(m \geq 1\).

  Further, this result for \(k\) queries implies (i) new bounds for the \((1+\beta)\)-process introduced by Peres, Talwar and Wieder (2010), (ii) new bounds for the graphical balanced allocation process on dense expander graphs, and (iii) the bound of \(m/n+\mathcal{O}(\log \log n)\) on the maximum load achieved by the \({\rm T{\small WO}\text{-}C{\small HOICE}}\) process, including the heavily loaded case \(m=\Omega(n)\) derived by Berenbrink, Czumaj, Steger and Vöcking (2006). One novel aspect of our proofs is the use of multiple super-exponential potential functions, which might be of use in future work.

Some visualisations for the processes described in the papers above, can be found here.

Presentations/Talks

• Tight Bounds for Repeated Balls-into-Bins [ STACS 2023 ][ slides ]
• Balanced Allocations with Heterogeneous Bins: The Power of Memory [ SODA 2023 ][ slides ]
• Balanced Allocations with the Choice of Noise [ ART & TEA, University of Hamburg ]
• Balanced Allocations with the Choice of Noise [ PODC 2022 ][ slides ]
• Brief Announcement: Tight Bounds for Repeated Balls-into-Bins [ SPAA 2022 ][ slides ]
• Balanced Allocations in Batches: Simplified and Generalized [ SPAA 2022 ][ slides ]
• Balanced Allocations: Relaxing Two-Choice [ HALG 2022 ][ slides ][ poster ]
• Balanced Allocations under Incomplete Information [ BCTCS 2022 ][ slides ]
• Balanced Allocations using Potential Functions [ FATA Seminar, University of Glasgow ]
• Balanced Allocations: Caching and Packing, Twinning and Thinning [ SODA 2022 ][ slides ]
• Balanced Allocations with Incomplete Information: The Power of Two Queries [ ITCS 2022 ][ slides ]

The animations on some of the slides run only on some pdf viewers (e.g. Adobe Reader or Okular).

Supervisions

Supervision material can be accessed here. (Raven access required)

Contact details

If you think I could be of help, don't hesitate to contact me.

Email: firstname.lastname at cl.cam.ac.uk
Room: FC13