We study simple dynamics in the population protocol model, in which n agents start with totally ordered initial opinions x1, x2, …, xn and, in each round, a randomly chosen agent changes its opinion as a function of the opinion of other randomly chosen agents. Such dynamics often converge to consensus on a single fixation value X^. This paper asks how to control the distribution of X^ as a randomised choice among the initial opinions by designing suitable simple dynamics. Writing the sorted initial values as x(1) ≤ … ≤ x(n), we design two protocols that realise natural target laws over order statistics.

We study the plurality consensus problem in distributed systems where a population of extremely simple agents, each initially holding one of k opinions, aims to agree on the initially most frequent one. In this setting, h-Majority is arguably the simplest and most studied protocol, in which each agent samples the opinion of h neighbors uniformly at random and updates its opinion to the most frequent value in the sample.

Boczkowski et al. (2018) considered the noisy PULL(h) model on the complete graph, where in each parallel round, every agent passively receives observations of the messages held by h randomly chosen agents, and where each message can be viewed as any other message in the alphabet ∑ with probability δ. The authors proved that in this model, the basic task of propagating a bit value from a single source to the whole population requires [EQUATION] rounds. The current work shows that the aforementioned lower bound is almost tight. We present two simple and efficient protocols that remain effective even in the presence of multiple conflicting sources, and quickly converge to their plurality opinion. Our first protocol operates with any alphabet of size at least two. Our second protocol, while slightly less efficient and requiring an alphabet of size four, is self-stabilizing. Overall, our results demonstrate how increasing the sample size can compensate for the lack of communication structure by linearly accelerating information spread.

We present the first upper bound on the convergence time to consensus of the well-known $h$-majority dynamics with $k$ opinions, in the synchronous setting, for $h$ and $k$ that are both non-constant values. We suppose that, at the beginning of the process, there is some initial additive bias towards some plurality opinion, that is, there is an opinion that is supported by $x$ nodes while any other opinion is supported by strictly fewer nodes. We prove that, with high probability, if the bias is $ω(\sqrt{x})$ and the initial plurality opinion is supported by at least $x = ω(\log n)$ nodes, then the process converges to plurality consensus in $O(\log n)$ rounds whenever $h = ω(n \log n / x)$. A main corollary is the following: if $k = o(n / \log n)$ and the process starts from an almost-balanced configuration with an initial bias of magnitude $ω(\sqrt{n/k})$ towards the initial plurality opinion, then any function $h = ω(k \log n)$ suffices to guarantee convergence to consensus in $O(\log n)$ rounds, with high probability. Our upper bound shows that the lower bound of $Ω(k / h^2)$ rounds to reach consensus given by Becchetti et al. (2017) cannot be pushed further than $\widetildeΩ(k / h)$. Moreover, the bias we require is asymptotically smaller than the $Ω(\sqrt{n\log n})$ bias that guarantees plurality consensus in the $3$-majority dynamics: in our case, the required bias is at most any (arbitrarily small) function in $ω(\sqrt{x})$ for any value of $k \ge 2$.

We address the self-stabilizing bit-dissemination problem, designed to capture the challenges of spreading information and reaching consensus among entities with minimal cognitive and communication capacities. Specifically, a group of n agents is required to adopt the correct opinion, initially held by a single informed individual, choosing from two possible opinions. In order to make decisions, agents are restricted to observing the opinions of a few randomly sampled agents, and lack the ability to communicate further and to identify the informed individual. Additionally, agents cannot retain any information from one round to the next. According to a recent publication in SODA (2024), a logarithmic convergence time without memory is achievable in the parallel setting (where agents are updated simultaneously), as long as the number of samples is at least [EQUATION]. However, determining the minimal sample size for an efficient protocol to exist remains a challenging open question. As a preliminary step towards an answer, we establish the first lower bound for this problem in the parallel setting. Specifically, we demonstrate that it is impossible for any memory-less protocol with constant sample size, to converge with high probability in less than an almost-linear number of rounds.

International audience