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.

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