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.

We consider an infinite balls-into-bins process with deletions where in each discrete step \(t\) a coin is tossed as to whether, with probability \(\beta(t)\in(0,1)\), a new ball is allocated using the Greedy[2] strategy (which places the ball in the lower loaded of two bins sampled uniformly at random) or, with remaining probability \(1-\beta(t)\), a ball is deleted from a non-empty bin chosen uniformly at random. Let \(n\) be the number of bins and \(m(t)\) the total load at time \(t\). We are interested in bounding the discrepancy \(x_{\max}(t)-m(t)/n\) (current maximum load relative to current average) and the overload \(x_{\max}(t)-m_{\max}(t)/n\) (current maximum load relative to highest average observed so far).

The discrete incremental voting process (DIV), introduced by Cooper, Radzik, and Shiraga [OPODIS '23], operates on an undirected graph where each node has an integer opinion. In one step a randomly selected node interacts with its randomly selected neighbor and changes its opinion by 1 towards the neighbor's opinion. The final consensus opinion has expectation equal to the degree-weighted average of the initial opinions. We show that for graphs with n nodes, conductance Φ, and the ratio of the average to smallest degree γ, if the maximal difference between initial opinions is K, then the expected convergence time is O(n (K log(Kn) + γn)/Φ2). This bound is essentially optimal for graphs of bounded expansion. We also show that for regular graphs, if the second largest eigenvalue (in absolute value) is o(1/log2 n) and K is o(n/log2 n), then w.h.p. DIV converges to the rounded initial average opinion.

Understanding the formation and evolution of opinions is of broad interdisciplinary interest. Many classical models for opinion formation focus on the impact of different notions of locality , e.g., locality due to network effects among agents or the role of the proximity of opinions. In practice, however, opinion formation is often governed by the interplay of local and global influences. In this paper, we study these influences with a model for opinion formation of agents embedded in a social network. Each agent has a static intrinsic opinion as well as a public opinion that is updated asynchronously over time. Moreover, agents have access to a global aggregate (e.g., the outcome of a vote) of all public opinions. We focus on the popular median voting rule and show that pure Nash equilibria always exist. For every initial state of the dynamics, a pure equilibrium can be reached. The set of reachable equilibria forms a complete lattice, and extremal equilibria can be computed in polynomial time. We show that by uniformly increasing the influence of the global median we can enforce that the median opinion is the same in every reachable equilibrium. We can compute the increase scheme that achieves this property in polynomial time. In contrast, when we can increase the influence of the global median for a set of at most k agents, finding the set that leads to a unique median opinion in every reachable equilibrium is NP -complete.

We present a silent, self-stabilizing ranking protocol for the population protocol model of distributed computing, where agents interact in randomly chosen pairs to solve a common task. We are given n anonymous agents, and the goal is to assign each agent a unique rank in {1,…,n}. Given unique ranks, it is straightforward to select a designated leader. Thus, our protocol is a self-stabilizing leader election protocol as well.Ranking requires at least n states per agent; hence, the goal is to minimize the additional number of states, called overhead states. The core of our protocol is a space-efficient but non-self-stabilizing ranking protocol that requires only n+O(logn) states. Our protocol stabilizes in O(n2logn) interactions w.h.p. and in expectation, using n + O(log2n) states in total. Our stabilization time is asymptotically optimal (see Burman et al., PODC ’21). In comparison to the currently best known ranking protocol by Burman et al., which requires n + Ω(n) states, our result exponentially improves the number of overhead states.

We study the epigenetic consensus problem, in which simple processors move across and modify a shared memory, seeking to achieve consensus across the cells of the memory. The memory topology is a ring with the cells initialised to 0 or 1. The ring is traversed by multiple processors moving clockwise in synchronous steps. Each processor belongs to one of four types: There are two types of erasers that erase either memory cells holding a 0 adjacent to a 1 or those holding a 1 adjacent to a 0. There are also two types of writers; those writing 1 or those writing 0 into empty cells.We are interested whether and how fast the above process converges to a consensus state where all memory cells have the same value. The origin of this process lies in biology, in the modelling of the activation and deactivation of DNA sequences. A variant of this process has been introduced and studied by Rashid, Taubenfeld, and Bar-Joseph.The convergence properties of the process depend on the initialisation of the shared memory, as well as on the number and types of processors and their initial locations. We show that, with adversarial initial processor positions, consensus cannot be reached.Having observed that a deterministic or adversarial model can be very powerful with regards to reaching consensus, we focus our attention on randomised initialisations. As our main contribution, we show the following two results that depend on a measure of processor bias describing whether the processors are biased towards increasing 0s or 1s in the cells: (a) With randomised initialisation of the memory cells and random processor placement, eventually consensus is reached with high probability, even with sublinear processor bias. (b) With high probability, consensus is reached quickly whenever there is an arbitrarily small constant factor processor bias. These two results hold even if the memory cell initialisation has a bias that is in the opposite direction compared to the bias in the processors.

We consider the problem of self-stabilizing leader election in the population model by Angluin et al. (JDistComp '06). The population model is a well-established and powerful model for asynchronous, distributed computation with a large number of applications. For self-stabilizing leader election, the population of n anonymous agents, interacting in uniformly random pairs, must stabilize with a single leader from any possible initial configuration.

Abstract. In an influential article, Papadimitriou [ On selecting a satisfying truth assignment, in Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1991, pp. 163–169] proved that a local search algorithm called WalkSAT finds a satisfying assignment of a satisfiable 2-CNF with [Formula: see text] variables in [Formula: see text] expected time. Variants of the WalkSAT algorithm have become a mainstay of practical SAT solving (see, e.g., [Hoos and Stützle, J. Autom. Reason., 24 (2000), pp. 421–481]). In the present article, we analyze the expected running time of WalkSAT on random 2-SAT instances. Answering a question raised by Alekhnovich and Ben-Sasson [ SIAM J. Comput., 36 (2007) pp. 1248–1263], we show that WalkSAT runs in linear expected time for all clause/variable densities up to the random 2-SAT satisfiability threshold.

Abstract Opinion spreading in a society decides the fate of elections, the success of products, and the impact of political or social movements. A prominent model to study opinion formation processes is due to Hegselmann and Krause. It has the distinguishing feature that stable states do not necessarily show consensus, i.e., the population of agents might not agree on the same opinion. We focus on the social variant of the Hegselmann–Krause model. There arenagents, which are connected by a social network. Their opinions evolve in an iterative, asynchronous process, in which agents are activated one after another at random. When activated, an agent adopts the average of the opinions of its neighbors having a similar opinion (where similarity of opinions is defined using a parameter $$\varepsilon $$ ε ). Thus, the set of influencing neighbors of an agent may change over time. We show that such opinion dynamics are guaranteed to converge for any social network. We provide an upper bound of $${\text {O}}(n|E|^2 (\varepsilon /\delta )^2)$$ O(n|E|2(ε/δ)2) on the expected number of opinion updates until convergence to a stable state, where $$|E|$$ |E| is the number of edges of the social network, and $$\delta $$ δ is a parameter of the stability concept. For the complete social network we show a bound of $${\text {O}}(n^3(n^2 + (\varepsilon /\delta )^2))$$ O(n3(n2+(ε/δ)2)) that represents a major improvement over the previously best upper bound of $${\text {O}}(n^9 (\varepsilon /\delta )^2)$$ O(n9(ε/δ)2) .

In this paper we study dynamic averaging load balancing on general graphs. We consider infinite time and dynamic processes, where in every step new load items are assigned to randomly chosen nodes. A matching is chosen, and the load is averaged over the edges of that matching. We analyze the discrete case where load items are indivisible, moreover our results also carry over to the continuous case where load items can be split arbitrarily. For the choice of the matchings we consider three different models, random matchings of linear size, random matchings containing only single edges, and deterministic sequences of matchings covering the whole graph. We bound the discrepancy, which is defined as the difference between the maximum and the minimum load. Our results cover a broad range of graph classes and, to the best of our knowledge, our analysis is the first result for discrete and dynamic averaging load balancing processes. As our main technical contribution we develop a drift result that allows us to apply techniques based on the effective resistance in an electrical network to the setting of dynamic load balancing.

We analyze the convergence of the k-opinion Undecided State Dynamics (USD) in the population protocol model. For k=2 opinions it is well known that the USD reaches consensus with high probability within O(n log n) interactions. Proving that the process also quickly solves the consensus problem for k > 2 opinions has remained open, despite analogous results for larger k in the related parallel gossip model. In this paper we prove such convergence: under mild assumptions on k and on the initial number of undecided agents we prove that the USD achieves plurality consensus within O(kn log n) interactions with high probability, regardless of the initial bias. Moreover, if there is an initial additive bias of at least Ω (√n log n) we prove that the initial plurality opinion wins with high probability, and if there is a multiplicative bias the convergence time is further improved. Note that this is the first result for k > 2 for the USD in the population protocol model. Furthermore, it is the first result for the unsynchronized variant of the USD with k > 2 which does not need any initial bias.

We consider two simple asynchronous opinion dynamics on arbitrary graphs where every node u of the graph has an initial value ξu(0). In the first process, which we call the NodeModel, at each time step t ≥ 0, a random node u and a random sample of k of its neighbours υ1, υ2, ... , υk are selected. Then, u updates its current value ξu(t) to [EQUATION], where α ∈ (0, 1) and k ≥ 1 are parameters of the process. In the second process, called the EdgeModel, at each step a random pair of adjacent nodes (u, υ) is selected, and then node u updates its value equivalently to the NodeModel with k = 1 and υ as the selected neighbour.

We consider the so-called Independent Cascade Model for rumor spreading or epidemic processes popularized by Kempe et al. (2003). In this model, a node of a network is the source of a rumor – it is informed. In discrete time steps, each informed node “infects” each of its uninformed neighbors with probability p. While many facets of this process are studied in the literature, less is known about the inference problem: given a number of infected nodes in a network, can we learn the source of the rumor? In the context of epidemiology this problem is often referred to as patient zero problem. It belongs to a broader class of problems where the goal is to infer parameters of the underlying spreading model. In this work we present a maximum likelihood estimator for the rumor’s source, given a snapshot of the process in terms of a set of active nodes X after t steps. Our results show that, for acyclic graphs, the likelihood estimator undergoes a phase transition as a function of $t$. We provide a rigorous analysis for two prominent classes of acyclic network, namely d-regular trees and Galton-Watson trees, and verify empirically that our heuristics work well in various general networks.

Solid State Drives (SSDs) have replaced magnetic disks in many application areas, as they provide very high performance for arbitrary access patterns. Nevertheless, data written to a physical page has to be erased before a page can be rewritten. The corresponding garbage collection (GC) process can only be performed on a block granularity, where a block includes many pages, impacting both the performance and lifetime of an SSD. The cost of a GC process is typically measured in terms of its write amplification, i.e., the number of blocks internally written by the SSD divided by the number of write requests of the host.Several GC heuristics have been proposed to optimize the write amplification of SSDs. These heuristics have been mostly empirically evaluated, while no thorough theoretical results are available on the optimality of GC algorithms even for seemingly simple cases like uniform and independent access distributions.In this work, we theoretically investigate the GREEDY GC strategy for uniformly independently distributed write accesses. We therefore model the garbage collection process on SSDs as a stochastic process and prove that the expected write amplification incurred by the GREEDY GC strategy is at most that of any other online GC strategy.

We study the Consensus problem among $n$ agents, defined as follows. Initially, each agent holds one of two possible opinions. The goal is to reach a consensus configuration in which every agent shares the same opinion. To this end, agents randomly sample other agents and update their opinion according to a simple update function depending on the sampled opinions. We consider two communication models: the gossip model and a variant of the population model. In the gossip model, agents are activated in parallel, synchronous rounds. In the population model, one agent is activated after the other in a sequence of discrete time steps. For both models we analyze the following natural family of majority processes called $j$-Majority: when activated, every agent samples $j$ other agents uniformly at random (with replacement) and adopts the majority opinion among the sample (breaking ties uniformly at random). As our main result we show a hierarchy among majority protocols: $(j+1)$-Majority (for $j > 1$) converges stochastically faster than $j$-Majority for any initial opinion configuration. In our analysis we use Strassen's Theorem to prove the existence of a coupling. This gives an affirmative answer for the case of two opinions to an open question asked by Berenbrink et al. [2017].

We consider the plurality consensus problem for population protocols. Here, n anonymous agents start each with one of k opinions. Their goal is to agree on the initially most frequent opinion (the plurality opinion) via random, pairwise interactions. Exact plurality consensus refers to the requirement that the plurality opinion must be identified even if the bias (difference between the most and second most frequent opinion) is only 1.

We consider the plurality consensus problem for n agents. Initially, each agent has one of k opinions. Agents choose random interaction partners and revise their state according to a fixed transition function, depending on their own state and the state of the interaction partners. The goal is to reach a configuration in which all agents agree on the same opinion. If there is initially a sufficiently large bias towards some opinions one of them should prevail. In this paper we consider a synchronized variant of the undecided state dynamics where the agents use so-called phase clocks. The phase clocks divide the time in overlapping phases. Each phase consists of a decision and a boosting part. In the decision part, any agent that encounters an agent with a different opinion becomes undecided. In the boosting part, undecided agents adopt the first opinion they encounter. We consider this dynamics both in the sequential population model and the parallel gossip model. In the population model agents interact in randomly chosen pairs, one pair per time step. The runtime is measured in parallel time (number of interactions divided by n). We show that our protocol reaches consensus (w.h.p.) in O(log2 n) parallel time, providing the first polylogarithmic result for k > 2 (w.h.p.) in this model. If there is an initial bias of , then (w.h.p.) that opinion wins. The gossip model assumes parallel rounds. During each round every agent is allowed to communicate with one randomly chosen agent. Here it is known that consensus can be reached fast (in polylogarithmic time) if there is a bias of order towards one opinion [Ghaffari and Parter, PODC'16; Berenbrink et al., ICALP'16]. Without any assumption on the bias, fast consensus has only been shown for k = 2 for the unsynchronized version of the undecided state dynamics [Clementi et al., MFCS'18]. To account for the yet unsolved general case, we show that the synchronized variant of the undecided state dynamics reaches consensus (w.h.p.) in time O(log2 n) for every initial configuration. Again, we guarantee that if there is an initial bias of , then (w.h.p.) that opinion wins. A simple extension of our protocol in the gossip model yields a dynamics that does not depend on n or k, is anonymous, and has (w.h.p.) runtime O(log2 n). This solves an open problem formulated by Becchetti et al. [Distributed Computing, 2017].

We consider a population protocol version of the SIR model. In every round, an individual is chosen uniformly at random. If the individual is susceptible, then it becomes infected w.p. $\beta I_t/N$, where $I_t$ is the number of infections at time $t$ and $N$ is the total number of individuals. If the individual is infected, then it recovers w.p. $\gamma$, whereas, if the individual is already recovered, nothing happens. We prove sharp bounds on the probability of the disease becoming pandemic vs extinguishing early (dying out quickly). The probability of extinguishing early, $\Pr{\mathcal{E}_{ext}}$, is typically neglected in prior work since most use (deterministic) differential equations. Leveraging on this, using $\Pr{\mathcal{E}_{ext}}$, we proceed by bounding the expected size of the population that contracts the disease $\mathbf{E}\left[R_\infty\right]$. Prior work only calculated $\mathbf{E}\left[R_\infty | \overline{\mathcal{E}_{ext}}\right]$, or obtained non-closed form solutions. We then study the two-country model also accounting for the role of $\Pr{\mathcal{E}_{ext}}$. We assume that both countries have different infection rates $\beta^{(i)}$, but share the same recovery rate $\gamma$. In this model, each round has two steps: First, an individual is chosen u.a.r. and travels w.p. $p_{travel}$ to the other country. Afterwards, the process continues as before with the respective infection rates. Finally, using simulations, we characterise the influence of $p_{travel}$ on the total number of infections. Our simulations show that, depending on the $\beta^{(i)}$, increasing $p_{travel}$ can decrease or increase the expected total number of infections $\mathbf{E}\left[R_\infty\right]$.

We analyze the following infinite load balancing process, modeled as a classical balls-into-bins game: There are$n$bins (servers) with a limited capacity (buffer) of size$c=c(n)\in \mathbb{N}$. Given a fixed arrival rate$\lambda=\lambda(n)\in(0,1)$, in every round$\lambda n$new balls (requests) are generated. Together with possible leftovers from previous rounds, these balls compete to be allocated to the bins. To this end, every ball samples a bin independently and uniformly at random and tries to allocate itself to that bin. Each bin accepts as many balls as possible until its buffer is full, preferring balls of higher age. At the end of the round, every bin deletes the ball it allocated first. We study how the buffer size$c$affects the performance of this process. For this, we analyze both the number of balls competing each round (including the leftovers from previous rounds) as well as the worst-case waiting time of individual balls. We show that (i) the number of competing balls is at any (even exponentially large) time bounded with high probability by$4 \cdot c^{-1} \cdot \ln (1/(1-\lambda))\cdot n + \mathrm{O}(c \cdot n)$and that (ii) the waiting time of a given ball is with high probability at most$(4 \cdot \ln (1/(1-\lambda)))/ (c \cdot (1-1/e)) + \log \log n + \mathrm{O}(c)$. These results indicate a sweet spot for the choice of$c$around$c = \Theta(\sqrt{\log (1/(1-\lambda))})$. Compared to a related process with infinite capacity [Berenbrink et al., PODC'16], for constant$\lambda$the waiting time is reduced from$\mathrm{O}(\log n)$to$\mathrm{O}(\log \log n)$. Even for large$\lambda \approx 1 - 1/n$we reduce the waiting time from$\mathrm{O}(\log n)$to$\mathrm{O}(\sqrt{\log n})$.

Abstract Population protocols are a model for distributed computing that is focused on simplicity and robustness. A system of n identical agents (finite state machines) performs a global task like electing a unique leader or determining the majority opinion when each agent has one of two opinions. Agents communicate in pairwise interactions with randomly assigned communication partners. Quality is measured in two ways: the number of interactions to complete the task and the number of states per agent. We present protocols for the majority problem that allow for a trade-off between these two measures. Compared to the only other trade-off result (Alistarh et al. in Proceedings of the 2015 ACM symposium on principles of distributed computing, Donostia-San Sebastián, 2015), we improve the number of interactions by almost a linear factor. Furthermore, our protocols can be made uniform (working correctly without any information on the population size n), yielding the first uniform majority protocols that stabilize in a subquadratic number of interactions.

We consider the efficient simulation of population protocols. In the population model, we are given a system of n agents modeled as identical finite-state machines. In each step, two agents are selected uniformly at random to interact by updating their states according to a common transition function. We empirically and analytically analyze two classes of simulators for this model. First, we consider sequential simulators executing one interaction after the other. Key to the performance of these simulators is the data structure storing the agents' states. For our analysis, we consider plain arrays, binary search trees, and a novel Dynamic Alias Table data structure. Secondly, we consider batch processing to efficiently update the states of multiple independent agents in one step. For many protocols considered in literature, our simulator requires amortized sub-constant time per interaction and is fast in practice: given a fixed time budget, the implementation of our batched simulator is able to simulate population protocols several orders of magnitude larger compared to the sequential competitors, and can carry out 2^50 interactions among the same number of agents in less than 400s.

Population protocols are a model of distributed computing, where n agents with limited computational power and memory perform randomly scheduled pairwise interactions. Recently, a significant amount of work has been devoted to the study of the time and space complexity of leader election in this model. It is known that Ω (log log n) states per agent are needed to elect a leader in fewer than [EQUATION] expected interactions (Alistarh et al.; SODA'17) and that Ω (n log n) expected interactions are required regardless of the number of states (Sudo and Masuzawa; 2020). On the positive side, Gasieniec and Stachowiak (SODA'18) gave the first protocol that uses an optimal Θ(log log n) number or states and elects a leader in O(n log2 n) expected interactions. This running time was subsequently improved to O(n log n log log n) (Gasieniec et al.; SPAA'19). We provide the first leader election population protocol that is both time and space optimal, electing a leader in O(n log n) expected interactions and using Θ(log log n) states per agent. A novel component is a simple protocol that efficiently selects a small set of agents of polylog n size, given O(n∈) initially selected agents. Unlike existing approaches, which monotonically shrink this initially selected set, we first grow it in a controlled way to a specific size before shrinking it again.

Population protocols are a model of distributed computing, where n agents with limited computational power and memory perform randomly scheduled pairwise interactions. A fundamental problem in this setting is that of leader election, where all agents start from the same state, and they seek to reach and maintain a global state where exactly one agent is in a dedicated leader state. A significant amount of work has been devoted to the study of the time and space complexity of this problem. Alistarh et al. (SODA’17) have shown that Ω(loglogn) states per agent are needed in order to elect a leader in fewer than Θ(n 2) expected interactions. Moreover, Ω(nlogn) expected interactions are required regardless of the number of states (Sudo and Masuzawa, 2019). On the upper bound side, Gasieniec and Stachowiak (SODA’18) have presented the first protocol that uses an optimal, Θ(loglogn), number or states and elects a leader in O(n log2 n) expected interactions. This running time was subsequently improved to O(n lognloglogn) (Gasieniec et al., SPAA’19).

We consider the following load balancing process for m tokens distributed arbitrarily among n nodes connected by a complete graph. In each time step a pair of nodes is selected uniformly at random. Let ℓ1and ℓ2be their respective number of tokens. The two nodes exchange tokens such that they have [(ℓ1+ℓ2)/2] and [(ℓ1+ℓ2)/2] tokens, respectively. We provide a simple analysis showing that this process reaches almost perfect balance within O(n log n + n log Δ) steps with high probability, where Δ is the maximal initial load difference between any two nodes. This bound is asymptotically tight.

We consider the problem of counting the population size in the population model. In this model, we are given a distributed system of n identical agents which interact in pairs with the goal to solve a common task. In each time step, the two interacting agents are selected uniformly at random. In this paper, we consider so-called uniform protocols, where the actions of two agents upon an interaction may not depend on the population size n. We present two population protocols to count the size of the population: protocol Approximate, which computes with high probability either [log n] or [log n], and protocol CountExact, which computes the exact population size in optimal O(log n) interactions, using Õ (n) states. Both protocols can also be converted to stable protocols that give a correct result with probability 1 by using an additional multiplicative factor of O(log n) states.

We consider the problem of deterministic load balancing of tokens in the discrete model. A set of n processors is connected into a d -regular undirected network. In every timestep, each processor exchanges some of its tokens with each of its neighbors in the network. The goal is to minimize the discrepancy between the number of tokens on the most-loaded and the least-loaded processor as quickly as possible. In this work, we identify some natural conditions on deterministic load-balancing algorithms to improve upon the long-standing results of Rabani et al. (1998). Specifically, we introduce the notion of cumulatively fair load-balancing algorithms where in any interval of consecutive timesteps, the total number of tokens sent out over an edge by a node is the same (up to constants) for all adjacent edges. We prove that algorithms that are cumulatively fair and where every node retains a sufficient part of its load in each step, achieve a discrepancy of O ( d min { √ log n /μ,√ n }) in time O ( T ), where μ is the spectral gap of the transition matrix of the graph. We also show that, in general, neither of these assumptions may be omitted without increasing discrepancy. We then show, by a combinatorial potential reduction argument, that any cumulatively fair scheme satisfying some additional assumptions achieves a discrepancy of O ( d ) almost as quickly as the continuous diffusion process. This positive result applies to some of the simplest and most natural discrete load balancing schemes.

A Coalescing-Branching Random Walk (CoBra) is a natural extension to the standard random walk on a graph. The process starts with one pebble at an arbitrary node. In each round of the process every pebble splits into k pebbles, which are sent to k random neighbors. At the end of the round all pebbles at the same node coalesce into a single pebble. The process is also similar to randomized rumor spreading, with each informed node pushing the rumor to k random neighbors each time it receives a copy of the rumor. Besides its mathematical interest, this process is relevant as an information dissemination primitive and a basic model for the spread of epidemics. We study the cover time of CoBra walks, which is the time until each node has seen at least one pebble. Our main result is a bound of O (φ–1 log n) rounds with high probability on the cover time of a CoBra walk with k = 2 on any regular graph with n nodes and conductance φ. This bound improves upon all previous bounds in terms of graph expansion parameters (Dutta et al. [13], Mitzenmacher et al. [27], Cooper et al. [8, 9]). Moreover, we show that for any connected regular graph the cover time is O (n log n) with high probability, independently of the expansion. Both bounds are asymptotically tight. Since our bounds coincide with the worst-case time bounds for Push rumor spreading on regular graphs until all nodes are informed, this raises the question whether CoBra walks and Push rumor spreading perform similarly in general. We answer this negatively by separating the cover time of CoBra walks and the rumor spreading time of Push by a super-polylogarithmic factor on a family of tree-like regular graphs.

A population protocol can be viewed as a sequence of pairwise interactions of $n$ agents (nodes). During one interaction, two agents selected uniformly at random update their states by applying a specified deterministic transition function. In a long run, the whole system should stabilize at the correct output property. The main performance objectives in designing population protocols are small number of states per agent and fast stabilization time. We present a fast population protocol for the exact-majority problem which uses $Θ(\log n)$ states (per agent) and stabilizes in $O(\log^{5/3} n)$ parallel time (i.e., $O(n\log^{5/3} n)$ interactions) in expectation and with high probability. Alistarh et al. [SODA 2018] showed that any exact-majority protocol which stabilizes in expected $O(n^{1-ε})$ parallel time, for any constant $ε> 0$, requires $Ω(\log n)$ states. They also showed an $O(\log^2 n)$-time protocol with $O(\log n)$ states, the currently fastest exact-majority protocol with polylogarithmic number of states. The standard design framework for majority protocols is based on $O(\log n)$ phases and requires that all nodes are well synchronized within each phase, leading naturally to upper bounds of the order of at least $\log^2 n$ because of $Θ(\log n)$ synchronization time per phase. We show how this framework can be tightened with {\em weak synchronization} to break the $O(\log^2 n)$ upper bound of previous protocols.

We consider the following balls-into-bins process with n bins and m balls: Each ball is equipped with a mutually independent exponential clock of rate 1. Whenever a ball's clock rings, the ball samples a random bin and moves there if the number of balls in the sampled bin is smaller than in its current bin. This simple process models a typical load balancing problem where users (balls) seek a selfish improvement of their assignment to resources (bins). From a game theoretic perspective, this is a randomized approach to the well-known KP model [1], while it is known as Randomized Local Search (RLS) in load balancing literature [2], [3]. Up to now, the best bound on the expected time to reach perfect balance was O((ln n)2+ln(n).n2/m) due to [3]. We improve this to an asymptotically tight O(ln(n)+n2/m). Our analysis is based on the crucial observation that performing destructive moves (reversals of RLS moves) cannot decrease the balancing time. This allows us to simplify problem instances and to ignore “inconvenient moves” in the analysis.

We study consensus processes on the complete graph of n nodes. Initially, each node supports one up to n different opinions. Nodes randomly and in parallel sample the opinions of constantly many nodes. Based on these samples, they use an update rule to change their own opinion. The goal is to reach consensus, a configuration where all nodes support the same opinion.

We consider plurality consensus in networks of n nodes. Initially, each node has one of k opinions. The nodes execute a (randomized) distributed protocol to agree on the plurality opinion (the opinion initially supported by the most nodes). In certain types of networks the nodes can be quite cheap and simple, and hence one seeks protocols that are not only time efficient but also simple and space efficient. Typically, protocols depend heavily on the employed communication mechanism, which ranges from sequential (only one pair of nodes communicates at any time) to fully parallel (all nodes communicate with all their neighbors at once) and everything in-between. We propose a framework to design protocols for a multitude of communication mechanisms. We introduce protocols that solve the plurality consensus problem and are, with probability 1-o(1), both time and space efficient. Our protocols are based on an interesting relationship between plurality consensus and distributed load balancing. This relationship allows us to design protocols that generalize the state of the art for a large range of problem parameters.

Plurality consensus considers a network of n nodes, each having one of k opinions. Nodes execute a (randomized) distributed protocol with the goal that all nodes adopt the plurality (the opinion initially supported by the most nodes). Communication is realized via the Gossip (or random phone call) model. A major open question has been whether there is a protocol for the complete graph that converges (w.h.p.) in polylogarithmic time and uses only polylogarithmic memory per node (local memory). We answer this question affirmatively. We propose two protocols that need only mild assumptions on the bias in favor of the plurality. As an example of our results, consider the complete graph and an arbitrarily small constant multiplicative bias in favor of the plurality. Our first protocol achieves plurality consensus in O(log(k)*log(log(n))) rounds using log(k) + Theta(log(log(k))) bits of local memory. Our second protocol achieves plurality consensus in O(log(n)*log(log(n))) rounds using only log(k) + 4 bits of local memory. This disproves a conjecture by Becchetti et al. (SODA'15) implying that any protocol with local memory log(k)+O(1) has worst-case runtime Omega(k). We provide similar bounds for much weaker bias assumptions. At the heart of our protocols lies an undecided state, an idea introduced by Angluin et al. (Distributed Computing'08).

In the voter model, each node of a graph has an opinion, and in every round each node chooses independently a random neighbour and adopts its opinion. We are interested in the consensus time, which is the first point in time where all nodes have the same opinion. We consider dynamic graphs in which the edges are rewired in every round (by an adversary) giving rise to the graph sequence G_1, G_2, ..., where we assume that G_i has conductance at least phi_i. We assume that the degrees of nodes don't change over time as one can show that the consensus time can become super-exponential otherwise. In the case of a sequence of d-regular graphs, we obtain asymptotically tight results. Even for some static graphs, such as the cycle, our results improve the state of the art. Here we show that the expected number of rounds until all nodes have the same opinion is bounded by O(m/(d_{min}*phi)), for any graph with m edges, conductance phi, and degrees at least d_{min}. In addition, we consider a biased dynamic voter model, where each opinion i is associated with a probability P_i, and when a node chooses a neighbour with that opinion, it adopts opinion i with probability P_i (otherwise the node keeps its current opinion). We show for any regular dynamic graph, that if there is an epsilon > 0 difference between the highest and second highest opinion probabilities, and at least Omega(log(n)) nodes have initially the opinion with the highest probability, then all nodes adopt w.h.p. that opinion. We obtain a bound on the convergence time, which becomes O(log(n)/phi) for static graphs.

A fundamental problem in distributed computing is the distribution of requests to a set of uniform servers without a centralized controller. Classically, such problems are modelled as static balls into bins processes, where m balls (tasks) are to be distributed to n bins (servers). In a seminal work, [Azar et al.; JoC'99] proposed the sequential strategy Greedy[d] for n = m. When thrown, a ball queries the load of d random bins and is allocated to a least loaded of these. [Azar et al.; JoC'99] showed that d=2 yields an exponential improvement compared to d=1. [Berenbrink et al.; JoC'06] extended this to m ⇒ n, showing that the maximal load difference is independent of m for d=2 (in contrast to d=1).

In this paper we consider a wide class of discrete diffusion load balancing algorithms. The problem is defined as follows. We are given an interconnection network and a number of load items, which are arbitrarily distributed among the nodes of the network. The goal is to redistribute the load in iterative discrete steps such that at the end each node has (almost) the same number of items. In diffusion load balancing, nodes are only allowed to balance their load with their direct neighbors. We show three main results. Firstly, we present a general framework for randomly rounding the flow generated by continuous diffusion schemes over the edges of a graph in order to obtain corresponding discrete schemes. Compared to the results of Rabani, Sinclair, and Wanka, FOCS'98, which are only valid w.r.t. The class of homogeneous first order schemes, our framework can be used to analyze a larger class of diffusion algorithms, such as algorithms for heterogeneous networks and second order schemes. Secondly, we bound the deviation between randomized second order schemes and their continuous counterparts. Finally, we provide a bound for the minimum initial load in a network that is sufficient to prevent the occurrence of negative load at a node during the execution of second order diffusion schemes. Our theoretical results are complemented with extensive simulations on different graph classes. We show empirically that second order schemes, which are usually much faster than first order schemes, will not balance the load completely on a number of networks within reasonable time. However, the maximum load difference at the end seems to be bounded by a constant value, which can be further decreased if first order scheme is applied once this value is achieved by second order scheme.

Renaming is a task in distributed computing where n processes are assigned new names from a name space of size m. The problem is called tight if m = n, and loose if m > n. In recent years renaming came to the fore again and new algorithms were developed. For tight renaming in asynchronous shared memory systems, Alistarh et al. describe a construction based on the AKS network that assigns all names within O(log n) steps per process. They also show that, depending on the size of the name space, loose renaming can be done considerably faster. For m = (1 + ϵ) · n and constant ϵ, they achieve a step complexity of O(log log n). In this paper we consider tight as well as loose renaming and introduce randomized algorithms that achieve their tasks with high probability. The model assumed is the asynchronous shared memory model against an adaptive adversary. Our algorithm for loose renaming maps n processes to a name space of size m = (1+2/(log n)ℓ)·n = (1+o(1))·n performing O(ℓ · (log logn)2) test-and-set operations. In the case of tight renaming, we present a protocol that assigns n processes to n names with step complexity O(log n), but without the overhead and impracticality of the AKS network. This algorithm utilizes modern hardware features in form of a counting device which is also described in the paper. This device may have the potential to speed up other distributed algorithms as well.

We study threshold-based load balancing protocols for weighted tasks. We are given an arbitrary graph G with n nodes (resources, bins) and m > n tasks (balls). Initially the tasks are distributed arbitrarily over the n nodes. The resources have a threshold and we are interested in the balancing time, i.e., the time it takes until the load of all resources is below the threshold. We distinguish between resource-based and user based protocols. In the case of resource-based protocols resources with a load larger than the threshold are allowed to send tasks to neighbouring resources. In the case of user-based protocols tasks allocated to resources with a load above the threshold decide on their own whether to migrate to a neighbouring resource or not. For resource-controlled protocols we present results for arbitrary graphs. Our bounds are in terms of the mixing time (for above-average thresholds) and the hitting time (for tight thresholds) of the graph. We relate the balancing time of resource-controlled protocols for above-average thresholds in arbitrary graphs to the mixing time of the graph and to the hitting time for tight thresholds. Our bounds are tight and, surprisingly, they are independent of the weights of the tasks. For the user-controlled migration we consider complete graphs and derive bounds for both above-average and tight thresholds.

We consider the problem of deterministic load balancing of tokens in the discrete model. A set of n processors is connected into a d-regular undirected network. In every time step, each processor exchanges some of its tokens with each of its neighbors in the network. The goal is to minimize the discrepancy between the number of tokens on the most-loaded and the least-loaded processor as quickly as possible. Rabani et al. (1998) present a general technique for the analysis of a wide class of discrete load balancing algorithms. Their approach is to characterize the deviation between the actual loads of a discrete balancing algorithm with the distribution generated by a related Markov chain. The Markov chain can also be regarded as the underlying model of a continuous diffusion algorithm. Rabani et al. showed that after time T = O(log (Kn)/μ), any algorithm of their class achieves a discrepancy of O(d log n/μ), where μ is the spectral gap of the transition matrix of the graph, and K is the initial load discrepancy in the system.

A palindrome is defined as a string which reads forwards the same as backwards, like, for example, the string "racecar". In the Palindrome Problem, one tries to find all palindromes in a given string. In contrast, in the case of the Longest Palindromic Substring Problem, the goal is to find an arbitrary one of the longest palindromes in the string. In this paper we present three algorithms in the streaming model for the the above problems, where at any point in time we are only allowed to use sublinear space. We first present a one-pass randomized algorithm that solves the Palindrome Problem. It has an additive error and uses square root of n space. We also give two variants of the algorithm which solve related and practical problems. The second algorithm determines the exact locations of all longest palindromes using two passes and square root of n space. The third algorithm is a one-pass randomized algorithm, which solves the Longest Palindromic Substring Problem. It has a multiplicative error using only O(log(n)) space.

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 study the parallel rotor walk process, which works as follows: Consider a graph along with an arbitrary distribution of tokens over its nodes. Every node is equipped with a rotor that points to its neighbours in a fixed circular order. In each round, every node distributes all of its tokens using the rotor. One token is allocated to the neighbour pointed at by the rotor, then the rotor moves to the subsequent neighbour, and so on, until no token remains.

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.

In this paper we consider load balancing in a static and discrete setting where a fixed number of indivisible tasks have to be allocated to processors. We assume uniform tasks but the processors may have different speeds. The load of a processor is the number of tasks assigned to it divided by its speed. We consider diffusion load balancing which works in rounds. In every round the processors are allowed to compare their own load with the load of their neighbors and to balance the load with the neighbors, using their local information only. The question is how many rounds does it take until the whole processor network is balanced, meaning the load discrepancy (difference between maximum load and m/n) is minimized. Our balancing algorithm is deterministic and extends the algorithm studied in [1] from the case of uniform speeds to non-uniform speeds. We use a potential function argument to show that a better load balance can be obtained when the algorithm is allowed to run longer compared to the algorithm of [1].

In this paper we consider neighborhood load balancing in the context of selfish clients. We assume that a network of n processors is given, with m tasks assigned to the processors. The processors may have different speeds and the tasks may have different weights. Every task is controlled by a selfish user. The objective of the user is to allocate his/her task to a processor with minimum load, where the load of a processor is defined as the weight of its tasks divided by its speed.

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.

In this paper, we consider a modified random walk which uses unvisited edges whenever possible, and makes a simple random walk otherwise. We call such a walk an edge-process (or E-process). We assume there is a rule A, which tells the walk which unvisited edge to use whenever there are several unvisited edges. In the simplest case, A is a uniform random choice over unvisited edges incident with the current walk position. However we do not exclude arbitrary choices of rule A. For example, the rule could be determined on-line by an adversary, or could vary from vertex to vertex.

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.

Balls-into-bins games for uniform bins are widely used to model randomized load balancing strategies. Recently, balls-into-bins games have been analysed under the assumption that the selection probabilities for bins are not uniformly distributed. These new models are motivated by properties of many peer-to-peer (P2P) networks, which are not able to perfectly balance the load over the bins. While previous evaluations try to find strategies for uniform bins under non-uniform bin selection probabilities, this paper investigates heterogeneous bins, where the "capacities" of the bins might differ significantly. We show that heterogeneous environments can even help to distribute the load more evenly, and that the load difference between bins can be bounded by 0(log log n) if each ball has two random choices, where n is the number of bins. Our analysis and simulation results show, for the first time, that the maximum load in heterogeneous balls-into-bins games is independent from the overall system capacity C and that bigger bins therefore can help to achieve good load balancing properties.

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.

We consider a variation of classical ball-into-bins games. We randomly allocate m balls into ◊n bins. Following Godfrey's model [6], we assume that each ball i comes with a β-balanced set of clusters of bins Βi = Βi,...Βsi}. The condition of β-balancedness essentially enforces a uniform-like selection of bins, where the parameter β governs the deviation from uniformity. We use a more relaxed notion of balancedness than [6], and also generalise the concept to deterministic balancedness.

Imitating successful behavior is a natural and frequently applied approach when facing scenarios for which we have little or no experience upon which we can base our decision. In this paper, we consider such behavior in atomic congestion games. We propose to study concurrent imitation dynamics that emerge when each player samples another player and possibly imitates this agents' strategy if the anticipated latency gain is sufficiently large. Our main focus is on convergence properties. Using a potential function argument, we show that these dynamics converge in a monotonic fashion to stable states. In such a state none of the players can improve their latency by imitating others.

We consider broadcasting in random d-regular graphs by using a simple modification of the so-called random phone call model introduced by Karp et al. [19]. In the phone call model every time step each node calls on a randomly chosen neighbour to establish a communication channel with this node. The communication channels can then be used to transmit messages in both directions. We show that, if we allow every node to choose four distinct neighbours instead of one, then the average number of message transmissions per node decreases exponentially. Formally, we present a broadcasting algorithm that has time complexity O(log n) and uses O(n log log n) transmissions per message. In contrast, we show for the standard model that every distributed and address-oblivious algorithm that broadcasts a message in time O(log n) needs Ω(n log n/ log d) message transmissions. Our algorithm can efficiently handle limited communication failures, only requires rough estimates of the number of nodes, and is robust against limited changes in the size of the network. Our results have applications in peer-to-peer networks and replicated databases.

This paper studies broadcasting and gossiping algorithms in random and general AdHoc networks. Our goal is not only to minimise the broadcasting and gossiping time, but also to minimise the energy consumption, which is measured in terms of the total number of messages (or transmissions) sent. We assume that the nodes of the network do not know the network, and that they can only send with a fixed power, meaning they can not adjust the area sizes that their messages cover. We believe that under these circumstances the number of transmissions is a very good measure for the overall energy consumption.

The (asymptotic) degree distributions of the best-known "scale-free" network models are all similar and are independent of the seed graph used; hence, it has been tempting to assume that networks generated by these models are generally similar. In this paper, we observe that several key topological features of such networks depend heavily on the specific model and the seed graph used. Furthermore, we show that starting with the "right" seed graph (typically a dense subgraph of the protein-protein interaction network analyzed), the duplication model captures many topological features of publicly available protein-protein interaction networks very well.

Suppose that a set of m tasks are to be shared as equally as possible among a set of n resources. A game-theoretic mechanism to find a suitable allocation is to associate each task with a “selfish agent” and require each agent to select a resource, with the cost of a resource being the number of agents that select it. Agents would then be expected to migrate from overloaded to underloaded resources, until the allocation becomes balanced. Recent work has studied the question of how this can take place within a distributed setting in which agents migrate selfishly without any centralized control. In this paper we discuss a natural protocol for the agents which combines the following desirable features: It can be implemented in a strongly distributed setting, uses no central control, and has good convergence properties. For $m \gg n$, the system becomes approximately balanced (an $\epsilon$-Nash equilibrium) in expected time $O(\log \log m)$. We show using a martingale technique that the process converges to a perfectly balanced allocation in expected time $O(\log \log m + n^4)$. We also give a lower bound of $\Omega(\max\{\log \log m, n\})$ for the convergence time.

We propose a new proof technique which can be used to analyze many parallel load balancing algorithms. The technique is designed to handle concurrent load balancing actions, which are often the main obstacle in the analysis. We demonstrate the usefulness of the approach by analyzing various natural diffusion-type protocols. Our results are similar to, or better than, previously existing ones, while our proofs are much easier. The key idea is to first sequentialize the original, concurrent load transfers, analyze this new, sequential system, and then to bound the gap between both.

We investigate balls-into-bins processes allocating m balls into n bins based on the multiple-choice paradigm. In the classical single-choice variant each ball is placed into a bin selected uniformly at random. In a multiple-choice process each ball can be placed into one out of $d \ge 2$ randomly selected bins. It is known that in many scenarios having more than one choice for each ball can improve the load balance significantly. Formal analyses of this phenomenon prior to this work considered mostly the lightly loaded case, that is, when $m \approx n$. In this paper we present the first tight analysis in the heavily loaded case, that is, when $m \gg n$ rather than $m \approx n$. The best previously known results for the multiple-choice processes in the heavily loaded case were obtained using majorization by the single-choice process. This yields an upper bound of the maximum load of bins of $m/n + {\mbox{$\cal O$}}(\sqrt{m \ln n \,/\, n})$ with high probability. We show, however, that the multiple-choice processes are fundamentally different from the single-choice variant in that they have "short memory." The great consequence of this property is that the deviation of the multiple-choice processes from the optimal allocation (that is, the allocation in which each bin has either $\lfloor m/n \rfloor$ or $\lceil m/n \rceil$ balls) does not increase with the number of balls as in the case of the single-choice process. In particular, we investigate the allocation obtained by two different multiple-choice allocation schemes, the greedy scheme due to Azar et al. and the always-go-left scheme due to Vöcking. We show that these schemes result in a maximum load of only $m/n + {\mbox{$\cal O$}}(\ln \ln n)$ with high probability. All our detailed bounds on the maximum load are tight up to an additive constant. Furthermore, we investigate the two multiple-choice algorithms in a comparative study. We present a majorization result showing that the always-go-left scheme obtains a better load balancing than the greedy scheme for any choice of n, m, and d.

In this paper we consider the following scenario. A set of n jobs with different threads is being run concurrently. Each job has an associated weight, which gives the proportion of processor time that it should be allocated. In a single time quantum, p threads of (not necessarily distinct) jobs receive one unit of service, and we require a rule that selects those p threads, at each quantum. Proportionate fairness means that over time, each job will have received an amount of service that is proportional to its weight. That aim cannot be achieved exactly due to the discretisation of service provision, but we can still hope to bound the extent to which service allocation deviates from its target. It is important that any scheduling rule be simple since the rule will be used frequently.We consider a variant of the Surplus Fair Scheduling (SFS) algorithm of Chandra, Adler, Goyal, and Shenoy. Our variant, which is appropriate for scenarios where jobs consist of multiple threads, retains the properties that make SFS empirically attractive but allows the first proof of proportionate fairness in a multiprocessor context. We show that when the variant is run, no job lags more than p H(n)-p+1 steps below its target number of services, where H(n) is the Harmonic function. Also, no job is over-supplied by more than O(1) extra services. This analysis is tight and it also extends to an adversarial setting, which models some situations in which the relative weights of jobs change over time.

In this paper we analyze a very simple dynamic work-stealing algorithm. In the work-generation model, there are n (work) generators. A generator-allocation function is simply a function from the n generators to the n processors. We consider a fixed, but arbitrary, distribution $\cal D$ over generator-allocation functions. During each time step of our process, a generator-allocation function h is chosen from $\cal D$, and the generators are allocated to the processors according to h. Each generator may then generate a unit-time task, which it inserts into the queue of its host processor. It generates such a task independently with probability $\lambda$. After the new tasks are generated, each processor removes one task from its queue and services it. For many choices of $\cal D$, the work-generation model allows the load to become arbitrarily imbalanced, even when $\lambda < 1$. For example, $\cal D$ could be the point distribution containing a single function h which allocates all of the generators to just one processor. For this choice of $\cal D$, the chosen processor receives around $\lambda n$ units of work at each step and services one. The natural work-stealing algorithm that we analyze is widely used in practical applications and works as follows. During each time step, each empty processor (with no work to do) sends a request to a randomly selected other processor. Any nonempty processor having received at least one such request in turn decides (again randomly) in favor of one of the requests. The number of tasks which are transferred from the nonempty processor to the empty one is determined by the so-called work-stealing functionf . In particular, if a processor that accepts a request has $\ell$ tasks stored in its queue, then $f(\ell)$ tasks are transferred to the currently empty one. A popular work-stealing function is $f(\ell)=\lfloor \ell/2\rfloor$, which transfers (roughly) half of the tasks. We analyze the long-term behavior of the system as a function of $\lambda$ and f. We show that the system is stable for any constant generation rate $\lambda < 1$ and for a wide class of functions f. Most intuitively sensible functions are included in this class (for example, every monotonically nondecreasing function f which satisfies $0 \leq f(\ell)\leq \ell/2$ and $f(\ell)=\omega(1)$ as a function of $\ell$ is included). Furthermore, we give upper bounds on theaverage system load (as a function of f and n). Our proof techniques combine Lyapunov function arguments with domination arguments, which are needed to cope with dependency.

In this paper we consider the problem of delivering dynamically changing input streams in dynamically changing networks where both the topology and the input streams can change in an unpredictable way. In particular, we present two simple distributed balancing algorithms (one for packet injections and one for flow injections) and show that for the case of a single receiver these algorithms will always ensure that the number of packets or flow in the system is bounded at any time step, even for an injection process that completely saturates the capacities of the available edges and even if the network topology changes in a completely unpredictable way. We also show that the maximum number of packets or flow that can be in the system at any time is essentially best possible by providing a lower bound that holds for any online algorithm, whether distributed or not. Interestingly, our balancing algorithms do not behave well in a completely adversarial setting. We show that also in the other extreme of a static network and a static injection pattern the algorithms will converge to a point in which they achieve an average routing time that is close to the best possible average routing time that can be achieved by any strategy. This demonstrates that there are simple algorithms that can be efficient for very different scenarios.

In this paper we analyse a very simple dynamic work-stealing algorithm. In the work-generation model, there are n generators which are arbitrarily distributed among a set of n processors. During each time-step, with probability /spl lambda/, each generator generates a unit-time task which it inserts into the queue of its host processor. After the new tasks are generated, each processor removes one task from its queue and services it. Clearly, the work-generation model allows the load to grow more and more imbalanced, so, even when /spl lambda/<1, the system load can be unbounded. The natural work-stealing algorithm that we analyse works as follows. During each time step, each empty processor sends a request to a randomly selected other processor. Any non-empty processor having received at least one such request in turn decides (again randomly) in favour of one of the requests. The number of tasks which are transferred from the non-empty processor to the empty one is determined by the so-called work-stealing function f. We analyse the long-term behaviour of the system as a function of /spl lambda/ and f. We show that the system is stable for any constant generation rate /spl lambda/<1 and for a wide class of functions f. We give a quantitative description of the functions f which lead to stable systems. Furthermore, we give upper bounds on the average system load (as a function of f and n).

In recent years, the task of allocating jobs to servers has been studied with the “balls and bins” abstraction. Results in this area exploit the large decrease in maximum load that can be achieved by allowing each job (ball) a little freedom in choosing its destination server (bin).

We investigate load balancing processes based on the multiplechoice paradigm.In these randomized processes m balls are inserted into n bins.In the classical single-choice variant each ball is placed simply into a randomly selected bin.In a multiple-choice process each ball can be placed into one out of d _> 2 randomly selected bins.It is well known that having more than one choice for each ball can improve the load balance significantly.In contrast to previous work on multiple-choice processes, we investigate the heavily loaded case, that is, we assume m >> n rather than m ,.~ n.The best previously known results for the multiple-choice processes in the heavily loaded case were obtained by majorization from the single-choice process.This yields an upper bound of m/n + O(~n).We show, however, that the multiplechoice processes are fundamentally different from the singlechoice variant in that they have "short memory".The great consequence of this property is that the deviation of the multiple-choice processes from the optimal allocation (i.e., at most [m/n] balls in every bin) does not increase with the number of balls as in case of the single-choice process.In particular, we investigate the allocation obtained by two different multiple-choice allocation schemes, the original greedy scheme and the recently presented always-go-left scheme.We show that

In this paper we consider dynamic load balancing algorithms for randomized and adversarial load generation models. Consider a system of n processors. In our randomized generation models every processor may generate a task with a certain probability at each time step, leading to an expected system load of O(n). We present a load balancing algorithm that assures that with high probability no processor has a load exceeding O(log log n) at an arbitrary point of time. This improves upon the O ((log log n) 2 ) bound of [4] In the case of the adversarial load generation model every processor can change its load by some constant at each time step. Thus, the system load may become arbitrarily large. We present a balancing algorithm and show that if at some point of time r no processor has a load exceeding some constant times the average, with high probability this holds for the next polynomial number of steps. Furthermore, we show that if the system is unstable at some point of time (meaning that there are processors with load much more than the average), then our algorithm recovers the system within expected poly(n) steps.

In this paper we study the problem of scheduling real-time requests in distributed data servers. We assume the time to be divided into time steps of equal length called rounds. During every round a set of requests arrives at the system, and every resource is able to fulfill one request per round. Every request specifies two (distinct) resources and requires to get access to one of them. Furthermore, every request has a deadline of d, i.e. a request that arrives in round t has to be fulfilled during round t +d 1 at the latest. The number of requests which arrive during some round and the two alternative resources of every request are selected by an adversary. The goal is to maximize the number of requests that are fulfilled before their deadlines expire. We examine the scheduling problem in an online setting, i.e. new requests continuously arrive at the system, and we have to determine online an assignment of the requests to the resources in such a way that every resource has to fulfil...

) Petra Berenbrink Department of Mathematics and Computer Science Paderborn University, Germany Email: [email protected] Tom Friedetzky and Ernst W. Mayr y Institut fur Informatik Technische Universitat Munchen, Germany Email: (friedetz---mayr)@informatik.tu-muenchen.de Abstract Recently, the subject of allocating tasks to servers has attracted much attention. There are several ways of distinguishing load balancing problems. There are sequential and parallel strategies, that is, placing the tasks one after the other or all of them in parallel. Another approach divides load balancing problems into continuous and static ones. In the continuous case new tasks are generated and consumed as time proceeds, in the second case the number of tasks is fixed. We present and analyze a parallel randomized continuous load balancing algorithm in a scenario where n processors continuously generate and consume tasks according to some given probability distribution. Each processor initiates l...

It is well known that after placing m n balls independently and uniformly at random (i.u.r.) into n bins, the fullest bin contains \\Theta(log n= log log n+ m n ) balls, with high probability. It is also known (see [Ste96]) that a maximum load of O \\Gamma m n \\Delta can be obtained for all m n if a ball is allocated in one (suitably chosen) of two (i.u.r.) bins. Stemann ([Ste96]) shows that r communication rounds suffice to guarantee a maximum load of maxf r p log n; O \\Gamma m n \\Delta g, with high probability. Adler et al. have shown in [ACMR95] that Stemanns protocol is optimal for constant r. In this paper we extend the above results in two directions: We generalize the lower bound to arbitrary r log log n. This implies that the result of Stemanns protocol is optimal for all r. Our main result is a generalization of Stemanns upper bound to weighted jobs: Let W A (W M ) denote the average (maximum) weight of the balls. Further let \\Delta = W A =W M . Note that...