Supplementary Material of "No Time to Interact: Simulating Population Protocols at Scale" / ESA2026. Please also check https://codeberg.org/manpen/graph-based-pop-prot-sim for updates.

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.

In group testing, the task is to identify defective items by testing groups of them together using as few tests as possible. We consider the setting where each item is defective with a constant probability $\alpha$, independent of all other items. In the (over-)idealized noiseless setting, tests are positive exactly if any of the tested items are defective. We study a more realistic model in which observed test results are subject to noise, i.e., tests can display false positive or false negative results with constant positive probabilities. We determine precise constants $c$ such that $cn\log n$ tests are required to recover the infection status of every individual for both adaptive and non-adaptive group testing: in the former, the selection of groups to test can depend on previously observed test results, whereas it cannot in the latter. Additionally, for both settings, we provide efficient algorithms that identify all defective items with the optimal amount of tests with high probability. Thus, we completely solve the problem of binary noisy group testing in the studied setting.

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

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