We study balanced allocations on graphs with removals. Load arrives at each edge e at an exponential rate and is then allocated to the vertex incident to e with the lowest current load. Load is removed from each vertex at an exponential rate. We identify a "conductance-like" quantity that determines if an equilibrium exists and allows us to bound the maximal load at equilibrium. Our analysis, based on simple potential function arguments, is very robust and can also handle noise in how the load is allocated. We also apply our general techniques to study the synchronous version of the process above, in which allocations and removals happen simultaneously at discrete time steps. We prove that, for any regular graph, in equilibrium, the expected difference in load across an edge, averaged over all edges, is at most 2. This implies, for example, that the two-choice process on the cycle has an O(n) gap between maximal and minimal load, improving the state-of-the-art by a log n factor.

We consider discrete, iterative load balancing via matchings on arbitrary graphs. Initially each node holds a certain number of tokens, defining the load of the node, and the objective is to redistribute the tokens such that eventually each node has approximately the same number of tokens. We present results for a general class of simple local balancing schemes where the tokens are balanced via matchings. In each round the process averages the tokens of any two matched nodes. If the sum of their tokens is odd, the node to receive the one excess token is selected at random. Our class covers three popular models: in the matching model a new matching is generated randomly in each round, in the balancing circuit model a fixed sequence of matchings is applied periodically, and in the asynchronous model the load is balanced over a randomly chosen edge.

Random walks on expanders play a crucial role in Markov Chain Monte Carlo algorithms, derandomization, graph theory, and distributed computing. A desirable property is that they are rapidly mixing, which is equivalent to having a spectral gap \(\gamma\) bounded away from 0.

Randomized rumor spreading processes diffuse information on an undirected graph and have been widely studied. In this work, we present a generic framework for analyzing a broad class of such processes on regular graphs. Our analysis is protocol-agnostic, as it only requires the expected proportion of newly informed vertices in each round to be bounded, and a natural negative correlation property. This framework allows us to analyze various protocols, including PUSH, PULL, and PUSH-PULL, thereby extending prior research. Unlike previous work, our framework accommodates message failures at any time $t\geq 0$ with a probability of $1-q(t)$, where the credibility $q(t)$ is any function of time. This enables us to model real-world scenarios in which the transmissibility of rumors may fluctuate, as seen in the spread of ``fake news'' and viruses. Additionally, our framework is sufficiently broad to cover dynamic graphs.

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).

Coalescing random walks is a fundamental distributed process, where a set of particles perform independent discrete-time random walks on an undirected graph. Whenever two or more particles meet at a given node, they merge and continue as a single random walk. The coalescence time is defined as the expected time until only one particle remains, starting from one particle at every node. Despite recent progress such as that of Cooper et al., the coalescence time for graphs, such as binary trees, d -dimensional tori, hypercubes, and, more generally, vertex-transitive graphs, remains unresolved. We provide a powerful toolkit that results in tight bounds for various topologies including the aforementioned ones. The meeting time is defined as the worst-case expected time required for two random walks to arrive at the same node at the same time. As a general result, we establish that for graphs whose meeting time is only marginally larger than the mixing time (a factor of log 2 n ), the coalescence time of n random walks equals the meeting time up to constant factors. This upper bound is complemented by the construction of a graph family demonstrating that this result is the best possible up to constant factors. Finally, we prove a tight worst-case bound for the coalescence time of O(n 3 ) . By duality, our results yield identical bounds on the voter model. Our techniques also yield a new bound on the hitting time and cover time of regular graphs, improving and tightening previous results by Broder and Karlin, as well as those by Aldous and Fill.

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.

We study the biased random walk where at each step of a random walk a “controller” can, with a certain small probability, move the walk to an arbitrary neighbour. This model was introduced by Azar et al. [STOC’1992]; we extend their work to the time dependent setting and consider cover times of this walk. We obtain new bounds on the cover and hitting times. Azar et al. conjectured that the controller can increase the stationary probability of a vertex from p to p 1-ε ; while this conjecture is not true in full generality, we propose a best-possible amended version of this conjecture and confirm it for a broad class of graphs. We also consider the problem of computing an optimal strategy for the controller to minimise the cover time and show that for directed graphs determining the cover time is PSPACE -complete.

We analyse the following random walk process inspired by the power-of-two-choice paradigm: starting from a given vertex, at each step, unlike the simple random walk (SRW) that always moves to a randomly chosen neighbour, we have the choice between two uniformly and independently chosen neighbours. We call this process the choice random walk (CRW). We first prove that for any graph, there is a strategy for the CRW that visits any given vertex in expected time ?(|E|). Then we introduce a general tool that quantifies by how much the probability of a rare event in the simple random walk can be boosted under a suitable CRW strategy. We believe this result to be of independent interest, and apply it here to derive an almost optimal ?(n log log n) bound for the cover time of bounded-degree expanders. This tool also applies to so-called biased walks, and allows us to make progress towards a conjecture of Azar et al. [STOC 1992]. Finally, we prove the following dichotomy: computing an optimal strategy to minimise the hitting time of a vertex takes polynomial time, whereas computing one to minimise the cover time is NP-hard.

Coalescing random walks is a fundamental stochastic process, where a set of particles perform independent discrete-time random walks on an undirected graph. Whenever two or more particles meet at a given node, they merge and continue as a single random walk. The coalescence time is defined as the expected time until only one particle remains, starting from one particle at every node. Despite recent progress such as by Cooper, Elsässer, Ono, Radzik [13] and Cooper, Frieze and Radzik [12], the coalescence time for graphs such as binary trees, d-dimensional tori, hypercubes and more generally, vertex-transitive graphs, remains unresolved. We provide a powerful toolkit that results in tight bounds for various topologies including the aforementioned ones. The meeting time is defined as the worst-case expected time required for two random walks to arrive at the same node at the same time. As a general result, we establish that for graphs whose meeting time is only marginally larger than the mixing time (a factor of log2 n), the coalescence time of n random walks equals the meeting time up to constant factors. This upper bound is complemented by the construction of a graph family demonstrating that this result is the best possible up to constant factors. For almost-regular graphs, we bound the coalescence time by the hitting time, resolving the discrete-time variant of a conjecture by Aldous for this class of graphs. Finally, we prove that for any graph the coalescence time is bounded by O(n3) (which is tight for the Barbell graph); surprisingly even such a basic question about the coalescing time was not answered before this work. By duality, our results give bounds on the voter model and therefore give bounds on the consensus time in arbitrary undirected graphs. We also establish a new bound on the hitting time and cover time of regular graphs, improving and tightening previous results by Broder and Karlin [10], as well as those by Aldous and Fill [1].

We study two random processes on an n-vertex graph inspired by the internal diffusion limited aggregation (IDLA) model. These processes can also be regarded as protocols for allocating jobs in a distributed network of servers. In both processes n particles start from an arbitrary but fixed origin. Each particle performs a simple random walk until it first encounters an unoccupied vertex, at which point the vertex becomes occupied and the random walk terminates. In one of the processes, called Sequential-IDLA, a single particle moves until settling and only then does the next particle start whereas in the second process, called Parallel-IDLA, all unsettled particles move simultaneously. The second process is akin to running the first in parallel. Our main goal is to analyze the so-called dispersion time of these processes, which is the maximum number of steps performed by any of the n particles. In order to compare the two processes, we develop a coupling which shows the dispersion time of the Parallel-IDLA stochastically dominates that of the Sequential-IDLA; however, the total number of steps performed by all particles has the same distribution in both processes. This coupling also gives us that dispersion time of Parallel-IDLA is bounded in expectation by dispersion time of the Sequential-IDLA up to a multiplicative łog n factor. Moreover, we derive asymptotic upper and lower bound on the dispersion time for several graph classes, such as cliques, cycles, binary trees, d-dimensional grids, hypercubes and expanders. Most of our bounds are tight up to a multiplicative constant.

Propositional satisfiability (SAT) is one of the most fundamental problems in computer science. The worst-case hardness of SAT lies at the core of computational complexity theory. The average-case analysis of SAT has triggered the development of sophisticated rigorous and non-rigorous techniques for analyzing random structures. Despite a long line of research and substantial progress, nearly all theoretical work on random SAT assumes a uniform distribution on the variables. In contrast, real-world instances often exhibit large fluctuations in variable occurrence. This can be modeled by a scale-free distribution of the variables, which results in distributions closer to industrial SAT instances. We study random k-SAT on n variables, $m=Θ(n)$ clauses, and a power law distribution on the variable occurrences with exponent $β$. We observe a satisfiability threshold at $β=(2k-1)/(k-1)$. This threshold is tight in the sense that instances with $β\le(2k-1)/(k-1)-\varepsilon$ for any constant $\varepsilon>0$ are unsatisfiable with high probability (w.h.p.). For $β\geq(2k-1)/(k-1)+\varepsilon$, the picture is reminiscent of the uniform case: instances are satisfiable w.h.p. for sufficiently small constant clause-variable ratios $m/n$; they are unsatisfiable above a ratio $m/n$ that depends on $β$.

Iterative load balancing algorithms for indivisible tokens have been studied intensively in the past. Complementing previous worst-case analyses, we study an average-case scenario where the load inputs are drawn from a fixed probability distribution. For cycles, tori, hypercubes and expanders, we obtain almost matching upper and lower bounds on the discrepancy, the difference between the maximum and the minimum load. Our bounds hold for a variety of probability distributions including the uniform and binomial distribution but also distributions with unbounded range such as the Poisson and geometric distribution. For graphs with slow convergence like cycles and tori, our results demonstrate a substantial difference between the convergence in the worst- and average-case. An important ingredient in our analysis is new upper bound on the t-step transition probability of a general Markov chain, which is derived by invoking the evolving set process.

We derive several new results on multiple random walks on "low dimensional" graphs. First, inspired by an example of a weighted random walk on a path of three vertices given by Efremenko and Reingold, we prove the following dichotomy: as the path length n tends to infinity, we have a super-linear speed-up w.r.t. the cover time if and only if the number of walks k is equal to 2. An important ingredient of our proofs is the use of a continuous-time analogue of multiple random walks, which might be of independent interest. Finally, we also present the first tight bounds on the speed-up of the cover time for any d-dimensional grid with d >= 2 being an arbitrary constant, and reveal a sharp transition between linear and logarithmic speed-up.

The rotor-router mechanism was introduced as a deterministic alternative to the random walk in undirected graphs. In this model, an agent is initially placed at one of the nodes of the graph. Each node maintains a cyclic ordering of its outgoing arcs, and during successive visits of the agent, propagates it along arcs chosen according to this ordering in round-robin fashion. The behavior of the rotor-router is fully deterministic but its performance characteristics (cover time, return time) closely resemble the expected values of the corresponding parameters of the random walk. In this work we consider the setting in which multiple, indistinguishable agents are deployed in parallel in the nodes of the graph, and move around the graph in synchronous rounds, interacting with a single rotor-router system. We propose new techniques which allow us to perform a theoretical analysis of the multi-agent rotor-router model, and to compare it to the scenario of parallel independent random walks in a graph. Our main results concern the n-node ring, and suggest a strong similarity between the performance characteristics of this deterministic model and random walks. We show that on the ring the rotor-router with k agents admits a cover time of between $$\varTheta (n^2 / k^2)$$ in the best case and $$\varTheta (n^2 / \log k)$$ in the worst case, depending on the initial locations of the agents, and that both these bounds are tight. The corresponding expected value of the cover time for k random walks, depending on the initial locations of the walkers, is proven to belong to a similar range, namely between $$\varTheta (n^2 / (k^2/\log ^2 k))$$ and $$\varTheta (n^2 / \log k)$$ . Finally, we study the limit behavior of the rotor-router system. We show that, once the rotor-router system has stabilized, all the nodes of the ring are always visited by some agent every $$\varTheta (n / k)$$ steps, regardless of how the system was initialized. This asymptotic bound corresponds to the expected time between successive visits to a node in the case of k random walks. All our results hold up to a polynomially large number of agents ( $$1 \le k < n^{1/11}$$ ).

In this work, we consider the following random process, motivated by the analysis of lock-free concurrent algorithms under high memory contention. In each round, a new scheduling step is allocated to one of n threads, according to a distribution p = (p1, p2, ..., pn), where thread i is scheduled with probability pi. When some thread first reaches a set threshold of executed steps, it registers a win, completing its current operation, and resets its step count to 1. At the same time, threads whose step count was close to the threshold also get reset because of the win, but to 0 steps, being penalized for almost winning. We are interested in two questions: how often does some thread complete an operation (system latency), and how often does a specific thread complete an operation (individual latency)?

We study a natural process for allocating m balls into n bins that are organized as the vertices of an undirected graph G. Balls arrive one at a time. When a ball arrives, it first chooses a vertex u in G uniformly at random. Then the ball performs a local search in G starting from u until it reaches a vertex with local minimum load, where the ball is finally placed on. Then the next ball arrives and this procedure is repeated. For the case m=n, we give an upper bound for the maximum load on graphs with bounded degrees. We also propose the study of the cover time of this process, which is defined as the smallest m so that every bin has at least one ball allocated to it. We establish an upper bound for the cover time on graphs with bounded degrees. Our bounds for the maximum load and the cover time are tight when the graph is vertex transitive or sufficiently homogeneous. We also give upper bounds for the maximum load when m>=n.

We study distributed load balancing in networks with selfish agents. In the simplest model considered here, there are n identical machines represented by vertices in a network and m > n selfish agents that unilaterally decide to move from one vertex to another if this improves their experienced load. We present several protocols for concurrent migration that satisfy desirable properties such as being based only on local information and computation and the absence of global coordination or cooperation of agents. Our main contribution is to show rapid convergence of the resulting migration process to states that satisfy different stability or balance criteria. In particular, the convergence time to a Nash equilibrium is only logarithmic in m and polynomial in n , where the polynomial depends on the graph structure. In addition, we show reduced convergence times to approximate Nash equilibria. Finally, we extend our results to networks of machines with different speeds or to agents that have different weights and show similar results for convergence to approximate and exact Nash equilibria.

We propose and analyze a quasirandom analogue of the classical push model for disseminating information in networks (“randomized rumor spreading”). In the classical model, in each round, each informed vertex chooses a neighbor at random and informs it, if it was not informed before. It is known that this simple protocol succeeds in spreading a rumor from one vertex to all others within O (log n ) rounds on complete graphs, hypercubes, random regular graphs, Erdős-Rényi random graphs, and Ramanujan graphs with probability 1 − o (1). In the quasirandom model, we assume that each vertex has a (cyclic) list of its neighbors. Once informed, it starts at a random position on the list, but from then on informs its neighbors in the order of the list. Surprisingly, irrespective of the orders of the lists, the above-mentioned bounds still hold. In some cases, even better bounds than for the classical model can be shown.

We study probabilistic protocols for concurrent threshold-based load balancing in networks. There are n resources or machines represented by nodes in an undirected graph and m >> n users that try to find an acceptable resource by moving along the edges of the graph. Users accept a resource if the load is below a threshold. Such thresholds have an intuitive meaning, e.g., as deadlines in a machine scheduling scenario, and they allow the design of protocols under strong locality constraints. When migration is partly controlled by resources and partly by users, our protocols obtain rapid convergence to a balanced state, in which all users are satisfied. We show that convergence is achieved in a number of rounds that is only logarithmic in m and polynomial in structural properties of the graph. Even when migration is fully controlled by users, we obtain similar results for convergence to approximately balanced states.

The rotor-router mechanism was introduced as a deterministic alternative to the random walk in undirected graphs. In this model, an agent is initially placed at one of the nodes of the graph. Each node maintains a cyclic ordering of its outgoing arcs, and during successive visits of the agent, propagates it along arcs chosen according to this ordering in round-robin fashion. In this work we consider the setting in which multiple, indistinguishable agents are deployed in parallel in the nodes of the graph, and move around the graph in synchronous rounds, interacting with a single rotor-router system. We propose new techniques which allow us to perform a theoretical analysis of the multi-agent rotor-router model, and to compare it to the scenario of parallel independent random walks in a graph. Our main results concern the n-node ring, and suggest a strong similarity between the performance characteristics of this deterministic model and random walks.

We propose a natural process for allocating n balls into n bins that are organized as the vertices of an undirected graph G.Each ball first chooses a vertex u in G uniformly at random.Then the ball performs a local search in G starting from u until it reaches a vertex with local minimum load, where the ball is finally placed on.In our main result, we prove that this process yields a maximum load of only Θ(log log n) on expander graphs.In addition, we show that for d-dimensional grids the maximum load is Θ log n log log n 1 d+1 .Finally, for almost regular graphs with minimum degree Ω(log n), we prove that the maximum load is constant and also reveal a fundamental difference between random and arbitrary tie-breaking rules.

We consider sequential balls-into-bins processes that randomly allocate m balls into n bins. We analyze two allocation schemes that achieve a close to optimal maximum load of ⌈m/n⌉ + 1 and require only O(m) (expected) allocation time. These parameters should be compared with the classic d-choice-process which achieves a maximum load of m/n + log log n/d + O(1) and requires m • d allocation time.

We consider the problem of balancing load items (tokens) on networks. Starting with an arbitrary load distribution, we allow in each round nodes to exchange tokens with their neighbors. The goal is to achieve a distribution where all nodes have nearly the same number of tokens. For the continuous case where tokens are arbitrarily divisible, most load balancing schemes correspond to Markov chains whose convergence is fairly well-understood in terms of their spectral gap. However, in many applications load items cannot be divided arbitrarily and we need to deal with the discrete case where the load is composed of indivisible tokens. This discretization entails a non-linear behavior due to its rounding errors, which makes the analysis much harder than in the continuous case. Therefore, it has been a major open problem to understand the limitations of discrete load balancing and its relation to the continuous case. We investigate several randomized protocols for different communication models in the discrete case. Our results demonstrate that there is almost no difference between the discrete and continuous case. For instance, for any regular network in the matching model, all nodes have the same load up to an additive constant in (asymptotically) the same number of rounds required in the continuous case. This generalizes and tightens the previous best result, which only holds for expander graphs.

We introduce a general method that converts a wide class of continuous neighborhood load balancing algorithms into a discrete version. Assume that initially the tasks are arbitrarily distributed among the nodes of a graph. In every round every node is allowed to communicate and exchange load with an arbitrary subset of its neighbors. The goal is to balance the load as evenly as possible. Continuous load balancing algorithms that are allowed to split tasks arbitrarily can balance the load perfectly, so that every node has exactly the same load. Discrete load balancing algorithms are not allowed to split tasks and therefore cannot balance the load perfectly.

We analyze the popular push-pull protocol for spreading a rumor in networks. Initially, a single node knows of a rumor. In each succeeding round, every node chooses a random neighbor, and the two nodes share the rumor if one of them is already aware of it. We present the first theoretical analysis of this protocol on random graphs that have a power law degree distribution with an arbitrary exponent β > 2. Our main findings reveal a striking dichotomy in the performance of the protocol that depends on the exponent of the power law. More specifically, we show that if 2 < β < 3, then the rumor spreads to almost all nodes in Θ(log log n) rounds with high probability. On the other hand, if β > 3, then Ω(log n) rounds are necessary. We also investigate the asynchronous version of the push-pull protocol, where the nodes do not operate in rounds, but exchange information according to a Poisson process with rate 1. Surprisingly, we are able to show that, if 2 < β < 3, the rumor spreads even in constant time, which is much smaller than the typical distance of two nodes. To the best of our knowledge, this is the first result that establishes a gap between the synchronous and the asynchronous protocol.

We study the relation between the rate at which rumors spread throughout a graph and the vertex expansion of the graph. We consider the standard rumor spreading protocol where every node chooses a random neighbor in each round and the two nodes exchange the rumors they know. For any n-node graph with vertex expansion α, we show that this protocol spreads a rumor from a single node to all other nodes in rounds with high probability. Further, we construct graphs for which Ω(α−1 log2 n) rounds are needed. Our results complement a long series of works that relate rumor spreading to edge-based notions of expansion, resolving one of the most natural questions on the connection between rumor spreading and expansion.

We consider the classical rumor spreading problem, where a piece of information must be disseminated from a single node to all n nodes of a given network. We devise two simple push-based protocols, in which nodes choose the neighbor they send the information to in each round using pairwise independent hash functions, or a pseudo-random generator, respectively. For several well-studied topologies our algorithms use exponentially fewer random bits than previous protocols. For example, in complete graphs, expanders, and random graphs only a polylogarithmic number of random bits are needed in total to spread the rumor in O(log n) rounds with high probability. Previous explicit algorithms require Omega(n) random bits to achieve the same round complexity. For complete graphs, the amount of randomness used by our hashing-based algorithm is within an O(log n)-factor of the theoretical minimum determined by [Giakkoupis and Woelfel, 2011].

We propose a simple distributed algorithm for balancing indivisible tokens on graphs. The algorithm is completely deterministic, though it tries to imitate (and enhance) a randomized algorithm by keeping the accumulated rounding errors as small as possible. Our new algorithm, surprisingly, closely approximates the idealized process (where the tokens are divisible) on important network topologies. On $d$-dimensional torus graphs with $n$ nodes it deviates from the idealized process only by an additive constant. In contrast, the randomized rounding approach of Friedrich and Sauerwald [Proceedings of the \textup41st Annual ACM Symposium on Theory of Computing, 2009, pp. 121--130] can deviate up to $\Omega(\operatorname{polylog}(n))$, and the deterministic algorithm of Rabani, Sinclair, and Wanka [Proceedings of the \textup39th Annual IEEE Symposium on Foundations of Computer Science, 1998, pp. 694--705] has a deviation of $\Omega(n^{1/d})$. This makes our quasirandom algorithm the first known algorithm for this setting, which is optimal both in time and achieved smoothness. We further show that on the hypercube as well, our algorithm has a smaller deviation from the idealized process than the previous algorithms. To prove these results, we derive several combinatorial and probabilistic results that we believe to be of independent interest. In particular, we show that first-passage probabilities of a random walk on a path with arbitrary weights can be expressed as a convolution of independent geometric probability distributions.

We present a new randomized diffusion-based algorithm for balancing indivisible tasks (tokens) on a network. Our aim is to minimize the discrepancy between the maximum and minimum load. The algorithm works as follows. Every vertex distributes its tokens as evenly as possible among its neighbors and itself. If this is not possible without splitting some tokens, the vertex redistributes its excess tokens among all its neighbors randomly (without replacement). In this paper we prove several upper bounds on the load discrepancy for general networks. These bounds depend on some expansion properties of the network, that is, the second largest eigenvalue, and a novel measure which we refer to as refined local divergence. We then apply these general bounds to obtain results for some specific networks. For constant-degree expanders and torus graphs, these yield exponential improvements on the discrepancy bounds compared to the algorithm of Rabani, Sinclair, and Wanka [14]. For hypercubes we obtain a polynomial improvement. In contrast to previous papers, our algorithm is vertex-based and not edge-based. This means excess tokens are assigned to vertices instead to edges, and the vertex reallocates all of its excess tokens by itself. This approach avoids nodes having “negative loads” (like in [8, 10]), but causes additional dependencies for the analysis.

We study distributed load balancing in networks with selfish agents. In the simplest model considered here, there are n identical machines represented by vertices in a network and m ≫ n selfish agents that unilaterally decide to move from one vetex to another if this improves their experienced load. We present several protocols for concurrent migration that satisfy desirable properties such as being based only on local information and computation and the absence of global coordination or cooperation of agents. Our main contribution is to show rapid convergence of the resulting migration process to states that satisfy different stability or balance criteria. In particular, the convergence time to a Nash equilibrium is only logarithmic in m and polynomial in n, where the polynomial depends on the graph structure. Using a slight modification with neutral moves, a perfectly balanced state can be reached after additional time polynomial in n. In addition, we show reduced convergence times to approximate Nash equilibria. Finally, we extend our results to networks of machines with different speeds or to agents that have different weights and show similar results for convergence to approximate and exact Nash equilibria.

We study the relation between the vertex expansion of a graph and the performance of randomized rumor spreading (push model). We prove that randomized rumor spreading takes O((1/α) · polylog(n)) time on any regular n-vertex graph with vertex expansion α. This bound extends previously known upper bounds by replacing conductance by vertex expansion. Our result is almost tight in the sense that the dependency on (1/α) is optimal (up to logarithmic factors) and that on non-regular graphs with constant vertex expansion, the runtime can be polynomial in n. Our upper bound also implies that randomized rumor spreading is “fast” on every vertex-transitive graph and yields a new upper bound on the cover time of random walks. We also exhibit a subtle difference between the impact of vertex expansion and conductance on rumor spreading. We show that there are regular graphs with constant vertex expansion for which randomized rumor spreading takes considerably longer than on any regular graph with constant conductance. Finally, we also prove a more general, but weaker result for the push & pull model which also covers non-regular graphs.

In the standard consensus problem there are n processes with possibly different input values and the goal is to eventually reach a point at which all processes commit to exactly one of these values. We are studying a slight variant of the consensus problem called the stabilizing consensus problem [2]. In this problem, we do not require that each process commits to a final value at some point, but that eventually they arrive at a common, stable value without necessarily being aware of that. This should work irrespective of the states in which the processes are starting. Our main result is a simple randomized algorithm called median rule that, with high probability, just needs O(log m log log n + log n) time and work per process to arrive at an almost stable consensus for any set of m legal values as long as an adversary can corrupt the states of at most √n processes at any time. Without adversarial involvement, just O(log n) time and work is needed for a stable consensus, with high probability. As a by-product, we obtain a simple distributed algorithm for approximating the median of n numbers in time O(log m log log n + log n) under adversarial presence.

We consider the problem of diffusion-based load balancing on a distributed network with n processors. If the load is arbitrarily divisible, then the convergence is fairly well captured in terms of the second largest eigenvalue of the diffusion matrix. As for many applications load can not be arbitrarily divided, we consider a model where load consists of indivisible, unit-size tokens. Quantifying by how much this integrality assumption worsens the efficiency of load balancing algorithms is a natural question which has been posed by many authors [9, 15, 16, 6, 19, 17].

We study the cover time of parallel random walks which was recently introduced by Alon et al. [2]. We consider k parallel (independent) random walks starting from arbitrary vertices. The expected number of steps until these k walks have visited all n vertices is called cover time of G.

We consider the following marking process (rw-rand) made by a random walk on an undirected graph G. Upon arrival at a vertex v, it marks v if unmarked and otherwise it marks a randomly chosen unmarked neighbor of v. We also consider a variant of this process called rw-r-rank. Here each vertex is assigned a global random rank first and then in each step, the walk marks the lowest ranked unmarked neighbor of the currently visited vertex. Depending on the degree and the expansion of the graph, we prove several upper bounds on the time required by these processes to mark all vertices. For instance, if G is a hypercube or random graph, our processes mark all vertices in time O(n), significantly speeding up the Θ(n log n)-cover time of standard random walks.

A Random Geometric Graph (RGG) in two dimensions is constructed by distributing n nodes independently and uniformly at random in and creating edges between every pair of nodes having Euclidean distance at most r, for some prescribed r. We analyze the following randomized broadcast algorithm on RGGs. At the beginning, only one node from the largest connected component of the RGG is informed. Then, in each round, each informed node chooses a neighbor independently and uniformly at random and informs it. We prove that with probability 1 – (n−1) this algorithm informs every node in the largest connected component of an RGG within rounds. This holds for any value of r larger than the critical value for the emergence of a connected component with Ω(n) nodes. In order to prove this result, we show that for any two nodes sufficiently distant from each other in , the length of the shortest path between them in the RGG, when such a path exists, is only a constant factor larger than the optimum. This result has independent interest and, in particular, gives that the diameter of the largest connected component of an RGG is , which surprisingly has been an open problem so far.

We propose a simple distributed algorithm for balancing indivisible tokens on graphs. The algorithm is completely deterministic, though it tries to imitate (and enhance) a random algorithm by keeping the accumulated rounding errors as small as possible. Our new algorithm approximates the idealized process (where the tokens are divisible) on important network topologies surprisingly closely. On d-dimensional torus graphs with n nodes it deviates from the idealized process only by an additive constant. In contrast to that, the randomized rounding approach of Friedrich and Sauerwald [8] can deviate up to Ω(polylog n) and the deterministic algorithm of Rabani, Sinclair and Wanka [23] has a deviation of Ω(n1/d). This makes our quasirandom algorithm the first known algorithm for this setting which is optimal both in time and achieved smoothness. We further show that also on the hypercube our algorithm has a smaller deviation from the idealized process than the previous algorithms. To prove these results, we derive several combinatorial and probabilistic results that we believe to be of independent interest. In particular, we show that first-passage probabilities of a random walk on a path with arbitrary weights can be expressed as a convolution of independent geometric probability distributions.

We empirically analyze two versions of the well-known “randomized rumor spreading” protocol to disseminate a piece of information in networks. In the classical model, in each round each informed node informs a random neighbor. At SODA 2008, three of the authors proposed a quasirandom variant. Here, each node has a (cyclic) list of its neighbors. Once informed, it starts at a random position of the list, but from then on informs its neighbors in the order of the list. While for sparse random graphs a better performance of the quasirandom model could be proven, all other results show that, independent of the structure of the lists, the same asymptotic performance guarantees hold as for the classical model. In this work, we compare the two models experimentally. This not only shows that the quasirandom model generally is faster (which was expected, though maybe not to this extent), but also that the runtime is more concentrated around the mean value (which is surprising given that much fewer random bits are used in the quasirandom process). These advantages are also observed in a lossy communication model, where each transmission does not reach its target with a certain probability, and in an asynchronous model, where nodes send at random times drawn from an exponential distribution. We also show that the particular structure of the lists has little influence on the efficiency. In particular, there is no problem if all nodes use an identical order to inform their neighbors.

A K-smoothing network is a distributed, low-contention data structure where tokens arrive arbitrarily on w input wires and reach w output wires via their completely asynchronous propagation through the network. The maximum discrepancy among the numbers of tokens arriving at the ouput wires, called smoothness, is at most K. It has been a longstanding open problem to construct a K-smoothing network with (i) optimal K, (ii) optimal Θ(lg w) depth (called smalldepth), (iii) no use of the AKS sorting network, and (iv) no reliance on global initialization. In this work, we present a very simple, randomized network which meets all four desiderata: • It is the cascade of a reasonably small number (about 150) of copies of the simple block network [6]; hence,

We introduce a new technique for bounding the cover time of random walks by relating it to the runtime of randomized broadcast. In particular, we strongly confirm for dense graphs the intuition of Chandra et al. (1997) that ``the cover time of the graph is an appropriate metric for the performance of certain kinds of randomized broadcast algorithms''. In more detail, our results are as follows: \begin{itemize} \item For any graph $G=(V,E)$ of size $n$ and minimum degree $\delta$, we have $\mathcal{R}(G)= \mathcal{O}(\frac{|E|}{\delta} \cdot \log n)$, where $\mathcal{R}(G)$ denotes the quotient of the cover time and broadcast time. This bound is tight for binary trees and tight up to logarithmic factors for many graphs including hypercubes, expanders and lollipop graphs. \item For any $\delta$-regular (or almost $\delta$-regular) graph $G$ it holds that $\mathcal{R}(G) = \Omega(\frac{\delta^2}{n} \cdot \frac{1}{\log n})$. Together with our upper bound on $\mathcal{R}(G)$, this lower bound strongly confirms the intuition of Chandra et al.~for graphs with minimum degree $\Theta(n)$, since then the cover time equals the broadcast time multiplied by $n$ (neglecting logarithmic factors). \item Conversely, for any $\delta$ we construct almost $\delta$-regular graphs that satisfy $\mathcal{R}(G) = \mathcal{O}(\max \{ \sqrt{n},\delta \} \cdot \log^2 n)$. Since any regular expander satisfies $\mathcal{R}(G) = \Theta(n)$, the strong relationship given above does not hold if $\delta$ is polynomially smaller than $n$. \end{itemize} Our bounds also demonstrate that the relationship between cover time and broadcast time is much stronger than the known relationships between any of them and the mixing time (or the closely related spectral gap).

We consider and analyze a new algorithm for balancing indivisible loads on a distributed network with n processors. The aim is minimizing the discrepancy between the maximum and minimum load. In every time-step paired processors balance their load as evenly as possible. The direction of the excess token is chosen according to a randomized rounding of the participating loads.

Graph partitioning requires the division of a graph's vertex set into k equally sized subsets such that some objective function is optimized. For many important ob jective functions, e. g., the number of edges incident to different partitions, the problem is MV-hard. Graph partitioning is an important task in many applications, so that a variety of algorithms and tools for its solution have been developed. Most state-of-the-art graph partitioning libraries use a variant of the Kernighan-Lin (KL) heuristic within a multilevel framework. While these libraries are very fast, their solutions do not always meet all requirements of the users. This includes the choice of the appropriate objective function and the shape of the computed partitions. Moreover, due to its sequential nature, the KL heuristic is not easy to parallelize. Thus, its use as a load balancer in parallel numerical applications requires complicated adaptations. That is why we have developed previously an inherently parallel algorithm, called BUBBLE-FOS/C (Meyerhenke et ah, IPDPS'06), which optimizes the partition shapes by a diffusive mechanism. Yet, it is too slow to be of real practical use, despite its high solution quality. In this paper, besides proving that BUBBLE-FOS/C converges towards a local optimum, we develop a much faster method for the improvement of partitionings. It is based on a different diffusive process, which is restricted to local areas of the graph and also contains a high degree of parallelism. By coupling this new technique with BUBBLE-FOS/C in a multilevel framework based on two different hierarchy construction methods, we obtain our new graph partitioning heuristic DibaP. Compared to BUBBLE-FOS/C, it shows a considerable acceleration, while retaining the positive properties of the slower algorithm. Experiments with popular benchmark graphs show an extremely good behavior. First, DibaP computes consistently better results - measured by the edge-cut and the number of boundary vertices in the summation and the maximum norm - than the state-of-the-art libraries METIS and JOSTLE. Second, with our new algorithm, we have improved the best known edge-cut values for a significant number of partitionings of six widely used benchmark graphs.

We revisit smoothing networks which are made up of balancers and wires. Tokens arrive arbitrarily on w input wires and propagate asynchronously through the network; each token gets service on the output wire it arrives at. The smoothness is the maximum discrepancy among the numbers of tokens arriving at the w output wires. We assume that balancers are oriented independently and uniformly at random. We present a collection of lower and upper bounds on smoothness, which are to some extent surprising:-The smoothness of a single block network is log log w + Θ(1) (with high probability), where the additive constant is between -2 and 4. This tight bound improves vastly over the upper bound of O(√log w) from Herlihy and Tirthapura, and it significantly improves our understanding of the smoothing properties of the block network. -Most significantly, the smoothness of the cascade of two block networks is no more than 16 (with high probability); this is the first known randomized network with so small depth (2 log w) and so good smoothness. The proof introduces some novel combinatorial and probabilistic structures and techniques which may be further applicable. This result demonstrates the full power of randomization in smoothing networks. -There is no randomized 1-smoothing network of width w and depth d that achieves 1-smoothness with probability better than d/w-1. In view of the deterministic 1-smoothing network from Klugerman and Plaxton, this result implies the first separation between deterministic and randomized smoothing networks, which demonstrates an unexpected limitation of randomization: it can get to constant smoothness very easily, but after that, the progress to 1-smoothing is very limited.