<figure><img src="image_1.png" /></figure>

HAL
open science

# Fast and Robust Information Spreading in the Noisy PULL Model

Niccolò d'Archivio, Amos Korman, Emanuele Natale, Robin Vacus

<figure><img src="image_2.png" /></figure>

## To cite this version:

Niccolò d'Archivio, Amos Korman, Emanuele Natale, Robin Vacus. Fast and Robust Information Spreading in the Noisy PULL Model. 2024. hal-04778388

HAL Id: hal-04778388

https://hal.science/hal-04778388v1

Preprint submitted on 12 Nov 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Fast and Robust Information Spreading in the Noisy *PULL* Model

Niccolò D'Archivio*

Amos Korman†

Emanuele Natale*

Robin Vacus‡

## Abstract

Understanding how information can efficiently spread in distributed systems under stochastic and noisy communication conditions is a fundamental question in both biological research and artificial system design. When the communication pattern is stable, allowing agents to control whom they interact with, noise in communication can often be mitigated through redundancy or more sophisticated coding techniques. In contrast, previous work has shown that noisy communication has fundamentally different consequences on well-mixed systems. Specifically, Boczkowski et al. (2018) considered the noisy *PULL*(*h*) model, in which in each (parallel) round, each agent passively receives observations of the messages held by *h* randomly chosen agents, 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 $\Omega(\frac{n\delta}{h(1-\delta|\Sigma|)^2})$ rounds. For example, for one-to-one interactions (*h* = 1) and constant *δ*, this lower bound is exponentially higher than the time required to reliably spread information over a stable complete network, thus exemplifying how the loss of structure in communication can undermine the system's ability to effectively counteract noise.

The current work shows that the aforementioned lower bound is almost tight. In particular, in the extreme case where each agent observes all other agents in each round, which can be related to scenarios where each agent senses the average tendency of the system, information spreading can reliably be achieved in $O(\log n)$ time, assuming constant noise. We present two simple and highly efficient protocols, thus suggesting their applicability to real-life scenarios. Notably, they also work in the presence of multiple conflicting sources and efficiently converge to their plurality opinion. The first protocol we present uses 1-bit messages but relies on a simultaneous wake-up assumption. By increasing the message size to 2 bits and removing the speedup in the information spreading time that may result from having multiple sources, we also present a simple and highly efficient self-stabilizing protocol that avoids the simultaneous wake-up requirement.

Overall, our results demonstrate how, under stochastic communication, increasing the sample size can compensate for the lack of communication structure by linearly accelerating information spreading time.

**Keywords.** Information Spreading; Noisy Communication; Zealot Consensus; Self-Stabilization; Cooperative Transport; Crazy Ants; Natural Algorithms

# 1 Introduction

## 1.1 Context and Motivation

This work falls within the research area of “natural algorithms”, investigating biologically inspired settings through an algorithmic perspective [1, 2, 3, 4]. By taking a higher-level, abstract approach, this research has the potential to provide fundamental computational insights into the underlying biological processes, which may be challenging to derive using more conventional computational techniques such as differential equations and simulations [5, 6, 7, 8, 9]. Such abstraction can help uncover computational constraints shaped by environmental factors and, alternatively, identify adaptable, efficient problem-solving strategies relevant across various biological constraints [10, 5, 7, 11]. At the same time, this perspective can inspire applications that harness these insights for artificial systems.

<footnote>*INRIA, COATI, Université Côte d'Azur, Sophia-Antipolis.</footnote>

<footnote>†Department of Computer Science, University of Haifa, Haifa, Israel.</footnote>

<footnote>‡BIDSA, Bocconi University, Milan, Italy.</footnote>
**A motivating scenario: Cooperative transport by “crazy ants”**. This study is motivated by the fascinating phenomenon of cooperative transport exhibited by *Paratrechina longicornis* ants, commonly known as “crazy ants”. This process involves a group of ants working together to physically transport a large food load to their nest [12, 13, 14, 6]. Researchers typically assume that each ant carrying the load senses the combined force exerted by all the carrying ants through the object being transported. After obtaining noisy measurements of this sum, each ant decides whether, and to what extent, it should align its force with this measurement. It is also believed that the ants physically transporting the load have limited information about the direction to the nest and that occasionally, a new knowledgeable ant enters the carrying group and helps navigate the load toward the nest [12, 13]. However, the directional signal from a knowledgeable ant might be diluted in the noise generated by the many other ants holding the load. This raises a natural question: How can a single informed ant convey directional information to the rest of the group when communication is limited to the inherently noisy perception of the load’s movement? This question was explored in [12], where the authors used statistical mechanics methods to show that, in principle, if the ants balance their response to the load’s movement with their individual directional preferences in a specific way, a single ant can, eventually (i.e., in a steady state), influence the entire group and steer the load in its preferred direction. However, another key question remains: Can such a process occur quickly?

Since it is known that disseminating information through pairwise noisy interactions requires time that is linear in the group size [8], a positive answer would depend on whether sensing the average opinion could lead to fundamentally different scenarios, where convergence is significantly sped up compared to pairwise interactions. This motivated us to study convergence time as a function of sample size.

## 1.2 Background

Disseminating information under randomized or unpredictable communication is a fundamental building block in multiple multi-agent systems, and has thus been extensively studied in various communities, including computer science [15, 16, 17, 18, 19, 20], physics [21, 22], and biology [8, 23, 24, 25]. In particular, in the biological world, the nature of computations performed by multi-agent systems under noisy communication varies across different organisms. Some systems effectively share information despite communication noise [26, 27], while others avoid gathering social information, thereby missing out on its potential benefits [28]. The key features that reduce unreliability in stochastic multi-agent systems are generally not well understood, nor are the circumstances in which these strategies might fail. Advancing our understanding in this area could deepen our insight into the constraints that shape the evolution of cooperative biological systems.

Following this approach, we study the basic information spreading problem (also called broadcast, or rumor spreading) in a well-mixed population, where messages are noisy [18, 17, 19, 8, 29]. More specifically, we consider a population of $n$ agents, each having an opinion, which, for simplicity, is assumed to be binary, i.e., either 0 or 1. One opinion corresponds to the ground truth and is called correct. A few agents, called sources, know which opinion is correct and are moreover aware of being sources [23, 24]. The goal of all agents is to have their opinions coincide with the correct opinion as quickly as possible. We also consider the more general case of having conflicting sources, that is, scenarios with sources that do not necessarily agree on which opinion is correct. In this case, we require that all agents converge on the majority opinion among sources.

Similarly to [8, 19], we consider the noisy *PULL*($h$) model of communication, in which each agent receives noisy observations from $h$ randomly chosen agents in each (parallel) round. Each agent $u$ holds a (public) message $\sigma$ in some alphabet $\Sigma$ and whenever another agent observes $u$, it receives a noisy version $\sigma'$ of $\sigma$, where noise is independent among observations. It is convenient to think of the noise such that the message observed $\sigma'$ has a bias to be the original message $\sigma$, but there is also some (e.g., constant) probability $\delta$ that each other possible message in the alphabet $\Sigma$ is received as $\sigma'$.

The authors in [8] showed that for a constant $\delta$ and a constant number of sources (all supporting the correct opinion), information spreading requires $\Omega(n/h)$ rounds, no matter which strategy is employed by the agents. For a constant sample size $h$, such as in the case of pairwise communication (where $h = 1$), this lower bound is exponentially greater than the time needed to reliably disseminate information in a stable, complete network, highlighting how the loss of communication structure can severely weaken the system's ability to effectively counteract noise.

However, the lower bound formula also leaves open the possibility of achieving a speedup as sample size
increases. Indeed, at first glance, there is reason to believe that increasing the sample size could dramatically improve the convergence time because agents obtain more information about the system's configuration in each round. On the other hand, these extra observations come from a single configuration (at round t), and it is perhaps required to monitor the evolution of the system over many rounds in order to determine the opinion of the source, as in [20].

Under this intuition, it is not even clear whether letting each agent observe all other agents in each round (albeit through noisy observations) could break the $\Omega(n)$ lower bound. Indeed, in this case, a logarithmic number of rounds would suffice for an agent $u$ to extract the correct opinion if it could reliably detect which of the samples it received in each round originated from the source. However, this detection capability is not readily available to $u$. For instance, the sources cannot safely signal the fact that they are sources using a designated bit, since this bit itself would be noisy. Consequently, since the sources are few, most of the received samples would falsely appear to come from the source, even though they originate from non-sources. Conversely, without the ability to identify the source, non-source agents must somehow extract information from multiple samples, most of which are unreliable. Indeed, in any given round, all agents are likely to have roughly the same quality of information about the correct opinion. Enhancing this quality, particularly in the initial stages, when it is very poor, appears challenging in the presence of noisy interactions. These considerations suggest that understanding which opinion is correct in a logarithmic or even poly-logarithmic number of rounds, may not be a trivial task.

## 1.3 Problem Definition

Consider a set $I = \{1, \dots, n\}$ of agents, where each agent $i$ holds a binary opinion $Y^{(i)} \in \{0, 1\}$. We also consider a subset of the agents, referred to as *source agents*, where each source agent is initially given a *preference* in $\{0, 1\}$ (which does not prevent it from later adopting a different opinion). We let $s_1$ (resp. $s_0$) denote the number of source agents with preference 1 (resp. 0), and make the mild assumption that $s_0, s_1 \le \frac{n}{4}$. We further define the *bias* as $s := |s_1 - s_0|$, and require that $s \ge 1$. The preference supported by the strict majority of sources is referred to as the *correct opinion*. The goal is for all agents, including sources, to eventually adopt the correct opinion as fast as possible.

**The Noisy PUŁL(h) model.** Agents employ communication using an alphabet of messages, termed $\Sigma$, that may differ from the opinion set $\{0, 1\}$. Time proceeds in discrete rounds, where in every round the following happens.

1. Each agent (source or non-source) chooses a message $\sigma \in \Sigma$ to display.

2. Every agent samples $h$ agents in $I$, uniformly at random with replacement. In particular, Agent $i$ may sample twice the same agent, and may also sample itself.

3. Every agent receives noisy versions of the messages displayed by the sampled agents. Specifically, we consider a stochastic<fnref n="1" /> matrix $N \in \mathbb{R}^{|\Sigma|^2|\Sigma|}$, called *noise matrix*, so that if Agent $i$ samples Agent $j$, displaying a message $\sigma \in \Sigma$, then Agent $i$ observes message $\sigma'$ with probability $N_{\sigma, \sigma'}$.

4. Every Agent $i$ may update its opinion $Y^{(i)}$, and its internal state (that may include counters, and other variables).

The decisions of an agent may depend on all the messages that it received so far, and possibly on the agent's coin tosses (in the case that the agent's protocol is probabilistic). We assume that the random events involved in sampling, noise, and agents' coin tosses are all independent (across both rounds and agents). As a standard convention, we say that an event $A$ happens with high probability (w.h.p.) if $\mathbb{P}(A) = 1 - \mathcal{O}(1/n^2)$.

**Definition 1.** For $\delta \in [0, 1/|\Sigma|]$ and a (stochastic) noise matrix $N$, we say that

* $N$ is $\delta$-lower bounded if $N_{\sigma, \sigma'} \ge \delta$ for every $\sigma, \sigma' \in \Sigma$.

* $N$ is $\delta$-upper bounded if

$$ \left\{ \begin{array}{ll} N_{\sigma, \sigma} \ge 1 - (|\Sigma| - 1)\delta & \text{for every } \sigma \in \Sigma, \\ N_{\sigma, \sigma'} \le \delta & \text{for every } \sigma \ne \sigma' \in \Sigma. \end{array} \right. \qquad (1) $$

<footnote n="1">¹A matrix is stochastic if its coefficients are non-negative, with each row summing to 1 (see Definition 9).</footnote>
• N is δ-uniform if there is equality in Eq. (1), i.e.,

$$ 
\begin{cases} 
N_{\sigma,\sigma} = 1 - (|\Sigma| - 1)\delta & \text{for every } \sigma \in \Sigma, \\ 
N_{\sigma,\sigma'} = \delta & \text{for every } \sigma \neq \sigma'. 
\end{cases} 
$$

**Self-stabilizing setting.** In order to capture the lack of ability to synchronize clocks, and in particular, the inability to know when the process starts, we consider a somewhat relaxed version of the classical notion of self-stabilization in distributed computing [30, 31]. That is, we assume that at time 0 (unknown to the agents) an adversary can manipulate and possibly corrupt the initial configuration, however, there are some constraints on such a manipulation. Specifically, we assume that the adversary first chooses the set of sources and their preferences. As before, the preference that is more frequent among sources is referred to as the correct opinion. Subsequently, the adversary chooses the internal states of agents, for example, by including in their memory fake samples presumably gathered earlier, or by corrupting their counters or clocks if they have any. However, we assume that agents know both the number of agents n and the noise matrix N, and whether or not they are sources with a given preference; this information is not corrupted by the adversary.

**Definition 2 (Convergence).** We say that a protocol solves the noisy information spreading problem in time $T$ w.h.p if the system reaches consensus on the correct opinion in at most $T$ rounds w.h.p. Note that with this definition, even the sources whose preference is incorrect must converge on the correct opinion. We additionally say that a protocol solves the problem in time $T$ in a self-stabilizing manner if, starting with any initial configuration (in the sense described above), the system reaches consensus on the correct opinion in at most $T$ rounds and remains with it for a polynomial number of rounds, say $n^3$ rounds, w.h.p.

## 1.4 Our Results

Let us first state the lower bound theorem in [8] which merely requires correctness with probability 2/3. The authors in [8] assumed that all sources agree on the correct opinion, which means, in particular, that the bias $s$ is the same as the number of sources. The main focus of [8] was the case of pairwise interactions, that is, $h = 1$, however their proof, that can be found in [32], applies for general $h$. Note that in the case that $\delta$ is bounded away from $1/|\Sigma|$, the lower bound becomes informative only when $s \le \sqrt{n}$.

**Theorem 3 (Theorem 4 in [32].).** Fix a non-source agent $u$ and an integer $h$. Any rumor spreading protocol in the noisy PUML(h) model with alphabet $\Sigma$ and $\delta$-lower bounded noise requires $\Omega(\frac{n\delta}{s^2h(1-|\Sigma|/\delta)^2})$ rounds in order to guarantee that the opinion of $u$ is correct with probability at least 2/3. This lower bound holds even assuming that all the system's parameters, including the number of agents $n$, the noise matrix $N$, and the number of sources $s$, are known to the designer of the protocol.

We prove the following theorem which guarantees high probability correctness. Similarly to Theorem 3, the theorem assumes that the designer of the protocol knows all the system's parameters.

**Theorem 4.** Consider $n$ agents with bias $s := |s_1 - s_0| \ge 1$ interacting according to the noisy PUML(h) model with alphabet $\Sigma = \{0, 1\}$ and $\delta$-upper bounded noise. The noisy information spreading problem can be solved w.h.p in

$$ T := \mathcal{O}\left(\frac{1}{h}\left(\frac{n\delta}{\min\{s^2, n\}(1-2\delta)^2} + \frac{\sqrt{n}}{s} + \frac{s_0 + s_1}{s^2}\right) \cdot \log n + \log n\right) $$

number of rounds, while using $\mathcal{O}(\log T + \log h)$ bits of memory per agent.

**Remark.**

• Note that the theorem guarantees convergence to the correct opinion even when the bias $s = 1$. This is in contrast to multiple works in the area of population protocols that guarantee convergence to the majority opinion only when the bias towards it is $\Omega(\sqrt{n \log n})$, see e.g., [33, 34, 35].

• When $\delta > \frac{s}{4\sqrt{n}}$ and the number of source agents is bounded as $s_0, s_1 \le \sqrt{n}$, the upper bound in Theorem 4 becomes

$$ \mathcal{O}\left(\frac{n\delta}{s^2h(1-2\delta)^2} \cdot \log n + \log n\right). $$
Thus, under these conditions and assuming the noise to be $\delta$-uniform, the theorem matches the lower bound in Theorem 3 up to a logarithmic factor.

* The missing log factor is likely due to the fact that Theorem 3 only requires agents to be correct with constant probability, while our notion of convergence demands high probability. Indeed, for the case where $\delta$ is constant, the authors in [19] showed that the extra log $n$ factor is necessary to achieve convergence w.h.p. when $h = 1$ (Theorem 7 in [19]), but in fact, their technique applies for general $h$ (see also Footnote 3).

**Theorem 4** demonstrates how a larger sample size can linearly accelerate the information spreading time. In particular, in the extreme case where each agent observes all other agents in each parallel communication round, we show that information spreading can be reliably achieved in $O(\log n)$ time, assuming $s$ and $\delta > 0$ are constants. In practical contexts, this shift from linear to logarithmic time can be the difference between impracticality and feasibility. This suggests that an increased sample size can effectively compensate for the lack of structure in noisy environments (see further discussion in Section 3).

To prove Theorem 4, we first reduced the general case of $\delta$-upper bounded noise to a uniform-noise scenario by letting agents add artificial noise to their observations. A high-level overview of such a strategy is given in Section 2. The validity of the transformation follows from a general proof of the non-singularity of the noise matrix $N$ (provided in Corollary 14). Although the corresponding linear algebra question is very simple to define, we could not find the answer in the literature, and instead, we provide one in Section 4.

Relying on this reduction allows us to restrict attention to uniform noise. For this case, we first present a simple synchronous protocol that achieves the upper bound stated in Theorem 4. This protocol is essentially composed of three phases. During the first two phases, source agents present their preferences at all rounds while each non-source agent overall presents the same number of 0's and 1's. Over time, this “neutral” behavior of non-sources allows the bias in the sources' preferences to somehow “stand-out” despite noise. Meanwhile, all agents (including sources) assemble samples from the population so that at the end of the two phases, each agent has gathered sufficiently many samples to obtain an opinion that is biased towards the correct opinion, by a very small, yet, non-negligible amount. This opinion is then presented by each agent throughout the third phase, which is dedicated to amplifying the slight bias in opinions using a majority rule.

The correctness of the protocol depends on the assumption that agents begin execution simultaneously, allowing them to transition through the phases in sync. At the cost of increasing the message size to 2 bits, and giving up for the acceleration that is caused by having a large bias $s$, we also present an efficient protocol that removes the simultaneous wake-up assumption to become self-stabilizing.

**Theorem 5.** Consider $n$ agents with bias $s := |s_1 - s_0| \ge 1$ interacting according to the noisy PUŁL($h$) model with alphabet $\Sigma = \{0,1\}^2$ and $\delta$-upper bounded noise. The noisy information spreading problem can be solved w.h.p in

$$T := \mathcal{O}\left(\frac{\delta n \log n}{h(1 - 4\delta)^2} + \frac{n}{h}\right)$$

number of rounds, in a self-stabilizing manner, while using $O(\log T + \log h)$ bits of memory per agent.

Recall from our definition of self-stabilization, that we assume that agents know the number of agents $n$ and the noise matrix $N$, and that such knowledge cannot be corrupted by the adversary. Moreover, after the adversary chooses the set of sources and their preferences, each agent knows whether it is a source or not, and this information cannot be corrupted by the adversary. In contrast to Theorem 4 (the non-self-stabilizing setting), Theorem 5 does not require agents to know the bias $s$.

We present our protocols and the intuition behind them in Section 2. Both are simple, and mainly rely on basic operations, namely, averaging, counting, and taking majority.

## 1.5 Related Works

In various natural scenarios, a group must reach a consensus on a particular value determined by the environment. In these cases, agents possess varying levels of knowledge about the target value, and the system must leverage the insights of the more informed individuals [24, 36, 37, 25, 23]. The problem of propagating information from one or more sources to an entire population has been extensively studied in distributed
computing under various names such as rumor spreading, information dissemination, epidemics, gossip, and
broadcast, see, e.g., [38, 16, 39, 40]. The problem of converging to the most frequent opinion among sources
is also known as “zealot consensus”, “majority bit dissemination” and “majority consensus” [41, 42, 43, 44].
These tasks become particularly challenging when communication is limited and the system is vulnerable to
faults.

The terms *PULL*(*h*) and *PUSH*(*h*) denote random meeting patterns, in which in each round, each agent *u* samples *h* agents uniformly at random, and may either extract information from them (*PULL*), or inform them with a message (*PUSH*) [38, 16]. These models capture “well-mixed” scenarios, in which agents have little to no control over who they interact with, and are reminiscent of random meeting patterns studied in the areas of *population protocols* [45, 15, 46] and *opinion dynamics* [47, 48]. A classical information spread algorithm that works in both models is based on copying the opinions held by the knowledgable agents upon interaction [16]. This simple mechanism, however, is not self-stabilizing [30, 31] and may fail if the internal states of non-source agents are set arbitrarily. Such conditions can occur when the system dynamically changes and the agents do not share a global notion of time. Consequently, one line of work has recently focused on obtaining efficient self-stabilizing information spreading in the *PULL*(*h*) model, while specifically aiming to minimize communication and/or memory capacities [42, 49, 20, 50, 51]. While most proposed self-stabilizing algorithms are unlikely to be found in nature, some may suggest elements that could be realistically plausible [51].

In the absence of noise in communication, with some “grain of salt” [16], the *PUSH* and *PULL* models are generally considered similar<fnref n="2" />. However, when the communication is noisy, there is an exponential separation between the two models. Indeed, the authors in [8] considered the noisy *PULL*(*h*) model (see Section 1.3), and proved Theorem 3. In particular, this theorem implies that for a single source (i.e., *s* = 1), constant sample size *h*, and constant noise *δ* > 0, the information spreading time is *Ω*(*n*), even if correctness is guaranteed with only a constant probability per agent. The authors in [19] showed that for constant parameters as above, if convergence is required w.h.p then the techniques in [8] can be modified to yield an *Ω*(*n* log *n*) lower bound<fnref n="3" />. The authors in [19] also present a protocol that is unlikely to be found in nature but achieves information spreading in *O*(*n* log *n*) rounds w.h.p., matching the lower bound. Standing in contrast to the linear lower bounds in [8, 19] for the case *h* = 1, the authors in [18] proved that in the noisy *PUSH*(*1*) model, information spreading can be solved in logarithmic time in *n*. The reason behind this exponential separation is that the noisy *PUSH* model hides a reliable component in the communication: When an agent receives a message, she cannot be sure of its original content, but she can nevertheless be sure that the sender of the message “intended” to send it. This reliability aspect is exploited in [18] to synchronize agents and control the propagation of information, to achieve fast and reliable information spreading. In this sense, communication under the noisy *PUSH* model — but where an agent cannot be certain not only of a message’s content but also of whether the message was genuinely “intended” for communication — may more closely resemble the noisy *PULL* model. This applies, for instance, to communication through physical bumping between ants [24, 8] where bumping could be both intentional or accidental.

Several scenarios in nature may be viewed as following noisy *PULL*-like communication patterns that involve relatively large sample sizes. Examples include flocks of birds, schools of fish, and bat groups, where individuals scan their surroundings to observe and respond to others' locations [22, 21, 23]. Swarming behaviors in midges [52] and firefly synchronization [53] are further cases where each individual (midge or firefly) responds to aggregated auditory or visual signals from numerous group members. In all these contexts, debates persist over the relevant communication models, particularly regarding the number and placement of observed agents [21, 53]. Additionally, during cooperative transport by longhorn “crazy ants” [12, 13, 54, 14, 6], carrying ants use the transported object to sense the cumulative force exerted by all participating ants. This setup allows ants to directly sense the overall directional tendency of the system,

<footnote n="2">²Potentially, by increasing the alphabet in messages, one could imagine that the *PUSH* model could be simulated under the *PULL* model by designating a bit in the message that signifies whether the agent is intending or not to reveal its message. However, if messages are noisy then this bit cannot be trusted.</footnote>

<footnote n="3">³ Specifically, the authors in [19] showed that a protocol that solves the bit dissemination problem in the *PULL*(*1*) model can be reduced to a so-called (*m*, *x*, *δ*)-Two-Party Protocol. This is a protocol that ensures that a party *A* can reliably receive a bit from a party *B*, with a probability of success at least 1 − *x*, after exchanging *m* messages that are affected by a *δ*-uniform noise. Thinking of *A* as the party of non-source agents, and *B* as the source, they modified the lower bound for the high probability regime for the case *h* = 1, which was the main focus of that paper. However, since the number of messages received by party *A* in the *PULL*(*h*) model is simply the number of rounds times *h*, it is possible to extend their result to apply for general *h*.</footnote>
bypassing the spatial considerations in communication that appear to be more prominent in the previous examples.

## 2 Protocols, Intuition, and Main Ingredients of Analysis

In this section, we present our protocols and the intuition behind their construction.

In Section 4, we show how to reduce the problem to the case that the noise is $\delta$-uniform, in order to facilitate several aspects of our algorithms and their analysis. For this purpose, upon receiving a message $\sigma \in \Sigma$, we let each agent apply an “artificial” noise to $\sigma$ to obtain a new random message $\sigma'$, and then run the original protocol on $\sigma'$. The combination of the noise matrix $N$ and the artificial noise ends up being a noise matrix $T$ which is $\delta$-uniform for some suitable $\delta > 0$. A formal definition of this notion of reduction is given in Definition 6, while the fact that it can be achieved in our scenario is proved in Theorem 8. When $|\Sigma| = 2$, this reduction can be easily achieved; however, for a larger alphabet, its feasibility is less obvious. Specifically, showing that uniform noise can be achieved for a general $\Sigma$ under a noise matrix $N$ involves showing that $N$ can be inverted, computing a suitable $\delta > 0$, and proving that the product of $N^{-1}$ with a $\delta$-uniform matrix is stochastic, so that the strategy can be implemented. We establish the non-singularity of $N$ in Section 4.1 (Corollary 14), and the other statements in Proposition 16.

In Section 5, we then consider the setting with uniform noise, presenting two related protocols, Source Filter (SF) and Self-stabilizing Source Filter (SSF). The former protocol requires agents to start the execution simultaneously at the same time, while the latter is self-stabilizing, at the cost of reduced efficiency and a larger communication alphabet. Since both protocols rely on similar ideas, we present their analysis in a unified manner.

The basic approach behind the construction of our algorithms is the following.

* On the one hand, each agent tries to extract information from her samples to form a first guess about the correct opinion. We refer to this guess as a weak-opinion, and show that it is correct with probability at least $1/2 + \varepsilon$ for some sufficiently large $\varepsilon > 0$. This is informally explained in Section 2.3 and formally proved in Lemma 23.

* On the other hand, all agents share their weak opinions with each other. Through majority-based operations, agents develop a refined guess that, with high probability, aligns with the correct opinion. This boosting mechanism is similar to those used in prior works involving the majority rule, such as [18, 17].

For such a procedure to work, it is desirable that all weak-opinions are mutually independent, so that the majority of weak-opinions would be correct with high probability. However, having non-source agents relay information between themselves can cause dependencies. Therefore, in our algorithms, weak-opinions are computed in a way that is oblivious of the information obtained (and the randomness involved) by other non-source agents. Hence, in a sense, the weak-opinions are based on “first-hand” information, that is, information that comes directly from the sources, despite the fact that sources are not easily detectable. This implies that to form a weak-opinion, an agent must sample a source sufficiently many times, which means that their computation alone already requires many rounds.

### 2.1 Source Filter (SF)

Here, we describe our fastest protocol, whose pseudo-code is given in Algorithm 1. The protocol uses a communication alphabet that corresponds to the opinion’s set, namely, $\Sigma := \{0, 1\}$. The execution is divided into three phases (where the first two phases are symmetric). The protocol relies on a simultaneous wake-up assumption, which is used to synchronize the clocks of agents. Each of the first two phases lasts for $\lceil m/h \rceil$ rounds, where

$$m = \Theta \left( \frac{n\delta \log n}{\min\{s^2, n\}(1 - |\Sigma|\delta)^2} + \frac{\sqrt{n} \log n}{s} + \frac{(s_0 + s_1) \log n}{s^2} + h \log n \right).$$

Since every agent observes $h$ samples per round, it collects at least $m$ messages in each of the first two phases.
* **Phase 0.** All non-source agents display 0, while sources display their (original) preference. In addition, all agents count the number of 1-opinions that they observe during the phase (variable $Counter_1$ in Algorithm 1).

* **Phase 1.** All non-source agents display 1, and sources still display their preference. All agents count the number of 0-opinions that they observe during the phase (variable $Counter_0$ in Algorithm 1).

At the end of Phase 1, each agent $i$ compares the number of 1-messages observed in Phase 0, with the number of 0-messages observed in Phase 1, and then sets its weak-opinion $\tilde{Y}^{(i)}$ to be the opinion corresponding to the greater number (breaking ties randomly). In other words, $\tilde{Y}^{(i)} := \mathbb{1}\{Counter_1 > Counter_0\}$ (breaking ties randomly). Note that the 0-messages observed in Phase 0 and the 1-messages observed in Phase 1 are ignored in this computation.

The third phase is devoted to boosting the bias in the population, based on a majority rule.

* **Majority Boosting phase.** In every round $t$ during this phase, each agent displays its opinion $Y_t^{(i)}$, which is initially equal to its weak-opinion (computed as above), and then updated from time to time by sampling the opinions of several other agents and taking the majority. More specifically, the Majority Boosting phase is divided into $10 \log n + 1$ sub-phases. At the end of each sub-phase, every agent $i$ sets its opinion to be the majority over all messages it received during this sub-phase. All sub-phases except the last one have the same duration, which is chosen in order to allow each agent to gather at least $w = \frac{100}{(1-2\delta)^2}$ messages per sub-phase. Finally, the last sub-phase lasts long enough for agents to gather at least $m$ messages.

By design, the Majority Boosting phase lasts for $\lceil w/h \rceil \cdot 10 \log n + \lceil m/h \rceil$ rounds, which is in fact at most the duration of the first two phases (Lemma 31). Therefore, the running time of Algorithm SF is overall $O(m/h)$ rounds.

By the symmetric construction of the algorithm and since the noise is uniform, we expect the number of messages wrongly counted as 1s in Phase 0, to be the same as the number of messages wrongly counted as 0s in Phase 1. Since there are more sources supporting the correct opinion, we also expect that they observe more correct messages originating from source agents. Together, these two observations imply that $\tilde{Y}^{(i)}$ is correct with a probability larger than $1/2$. By setting $m$ to be large enough, we can get this probability to be at least $1/2 + \sqrt{\log(n)/n}$ (see more details in Section 2.3), which is sufficiently high to allow the Majority Boosting phase to be efficient and reliable.

In addition, we show that the value of $\tilde{Y}^{(i)}$ depends only on the random samples received by Agent $i$, the noise affecting these samples, and the coin tosses of Agent $i$ used to break ties. Since all these random variables are mutually independent among agents, so are the weak-opinions.

**Remark.** In the first two phases of Algorithm SF, each non-source agent presents the message 0 consecutively for many rounds and then switches to presenting 1 for the same number of rounds. Perhaps a more natural algorithm would allow each agent to first flip a fair coin to determine the message it will present on the first round, and then, over the following rounds, deterministically alternate between 0 and 1. While it is plausible that such a scheme would work as well, it does add some complexity to the analysis. For the sake of simplicity, we therefore decided to focus on Algorithm SF.

## 2.2 Self-stabilizing Source Filter (SSF)

Algorithm SF has an optimal convergence time for a wide range of values of $\delta$, and moreover, it only relies on a small communication alphabet containing only the opinions. However, it requires agents to share a global notion of time, so that they can agree on when to start each phase. In Section 5.4, we show that, at the cost of increasing the size of the alphabet and slightly increasing the running time, such a synchronization assumption is not essential.

For this purpose, we present a self-stabilizing protocol, whose pseudo-code is given in Algorithm 2. The protocol uses a communication alphabet of size 4, namely, $\Sigma := \{0, 1\}^2$, meaning that each message is simply composed of 2 bits. In every round $t$, each agent $i$ maintains a weak-opinion $\tilde{Y}_t^{(i)} \in \{0, 1\}$ as well as an opinion $Y_t^{(i)} \in \{0, 1\}$ that is held internally. The first bit of each message indicates whether or not the sender is a source. For source agents, the second bit corresponds to their preference, whereas for non-source agents, it indicates their weak-opinion. In addition, each agent $i$ holds a multi-set (containing at most $m$ messages)
in her memory, whose content in round $t$ is denoted by $M_t^{(i)}$. In every round, Agent $i$ adds all messages received in this round to $M_t^{(i)}$. If this results in $|M_t^{(i)}|$ exceeding $m$ (which happens every $\lfloor m/h \rfloor$ rounds), the agent updates its opinion and weak-opinion based on the content of the multi-set, and then empties it. Specifically, on such a round, which we refer to as an *update round* for Agent $i$, the following occurs:

* the new weak-opinion of Agent $i$, namely, $\tilde{Y}_{t+1}^{(i)}$, is computed as the majority over the second bits of all messages in $M_t^{(i)}$ whose first bit is 1 (breaking ties uniformly at random). Recall that in absence of noise, by construction, such a bit would correspond to the preference of a source agent.

* the new opinion of Agent $i$, namely $Y_{t+1}^{(i)}$, is computed as the majority over the second bits of all messages in $M_t^{(i)}$ (breaking ties uniformly at random).

Note that in a self-stabilizing framework, the multi-sets $\{M_t^{(i)}\}_{i \in I}$ are initialized arbitrarily. In particular, they may start with different sizes, in which case the update rounds of different agents may not occur simultaneously.

Importantly, the larger number of sources with the correct opinion (say, 1), together with the uniform noise, imply that each agent is more likely to receive the message (1, 1) than the message (1, 0), even after noise is applied. In turn, this implies that each weak-opinion $\tilde{Y}_t^{(i)}$ is correct with a probability larger than $1/2$. This is formally proved in Lemma 36. We remark that the fact that for every round $t$, all weak-opinions $\{\tilde{Y}_t^{(i)}\}_{i \in I}$ are mutually independent is less obvious than for Algorithm SF. As mentioned, the weak opinion of an agent is updated according to the second bits of messages that were received with a first bit that equals 1. If such a message $\sigma$ originated from a non-source agent, then it must have been corrupted by noise. Therefore, because of the noise being uniform, the distribution of the second bit of $\sigma$ is independent of the second bit of the original message (which is the weak opinion of the sampled non-source agent). This implies that, eventually, the weak-opinion of each agent $i$ is independent from the behavior of all other non-source agents. Finally, notice that, after $2\lfloor m/h \rfloor$ rounds, each agent has updated twice. For every agent $i$, the set $M_t^{(i)}$ is emptied after its first update, and from now on, it will only contain messages that were actually sampled (and not generated adversarially during the initialization), which allows the protocol to be self-stabilizing.

## 2.3 Intuition Behind the Correctness Analysis of Weak-opinions

In this section, we give an overview of the computations ensuring that the weak-opinions are correct, in both Algorithms SF and SSF. Formal statements and corresponding proofs are provided in Section 5.

Let us fix an agent $i$. For both protocols, for the sake of analysis, we map the messages used to compute the weak-opinions of Agent $i$, to a set of i.i.d. random variables $\{X_k\}_k$ taking values in $\{-1, 0, +1\}$. Although these variables are defined differently for each protocol, the general idea is that $X_k = +1$ (resp. $-1$) if the corresponding messages suggest that the correct opinion is 1 (resp. 0), whereas $X_k = 0$ if the corresponding messages do not carry relevant information. For instance, in the case of Algorithm SF, we define one $X_k$ for each message in the memory of the agent. When a message has a first bit equal to 1 (i.e., it is tagged as coming from a source), the corresponding $X_k$ is assigned value $+1$ or $-1$ depending on the second bit of the message, and otherwise, it is assigned value 0. Instead, in the case of Algorithm SF, each $X_k$ corresponds to a pair of messages, one received in Phase 0 and one in Phase 1. When these messages are either both equal to 1, or both equal to 0, then the corresponding $X_k$ is assigned value $+1$ or $-1$ respectively. Conversely, when these messages are different, $X_k$ is assigned value 0. Now, let us consider the sum $X = \sum_k X_k$. The protocols and the $X_k$s are defined so that the weak-opinion of Agent $i$ is equal to 1 if and only if $X > 0$ (leaving the tie-breaking mechanism aside). Without loss of generality, we will assume that the correct opinion is 1, and focus on showing that $X > 0$ with probability at least $1/2 + \Omega(\sqrt{\log n/n})$. This requires a fine-grained analysis of the distribution of $X$, that classical concentration inequalities do not provide directly.

Recall that a Rademacher random variable takes values in $\{-1, +1\}$. Although the $\{X_k\}$ variables are not Rademacher, since we expect the number of non-zero $X_k$s to be $\ell := m \cdot \mathbb{P}(X_k \neq 0)$, we show that $X$ is distributed roughly as a sum of $\ell$ i.i.d. Rademacher random variables. Moreover, each variable in this sum would be equal to 1 with probability $p = \mathbb{P}(X_k = 1 | X_k \neq 0)$. We can then apply the following lower
bound, derived directly from existing literature (see Lemma 22):

$$ \mathbb{P}(X > 0) - \mathbb{P}(X < 0) \geq \sqrt{\frac{2}{\pi e}} \cdot \min\{(p - \frac{1}{2})\sqrt{\ell}, 1\}. $$

Hence, a sufficient condition for having $X > 0$ with probability at least $1/2 + \Omega(\sqrt{\log n/n})$, is (up to a constant factor):

$$ \left(p - \frac{1}{2}\right) \cdot \sqrt{\ell} \geq \sqrt{\frac{\log n}{n}}. \qquad (2) $$

This condition reflects the need to gather sufficient information from the variables $X_k$. Specifically, $\ell$ represents the number of $X_k$'s that provide any useful information, while $p - \frac{1}{2}$ quantifies the extent to which each non-zero $X_k$ contributes in correctly inferring the correct opinion. In order to estimate $\ell = m \cdot \mathbb{P}(X_k \neq 0)$, we show that for both protocols,

$$ \mathbb{P}(X_k \neq 0) \geq \delta + \frac{s_0 + s_1}{2n} (1 - |\Sigma|\delta). $$

The first term corresponds to corrupted messages, while the second term corresponds to uncorrupted messages from the sources (in Algorithm SSF, there is another factor of $(1 - |\Sigma|\delta)$ that is due to the more complex pairing of $X_k$-messages; but we ignore it here for the sake of clarity).

When computing $p - \frac{1}{2}$, we distinguish between two regimes.

* When

$$ \delta < \frac{s_0 + s_1}{2n} (1 - |\Sigma|\delta), $$

we are in a situation in which each non-zero $X_k$ is more likely to be the consequence of a direct observation of a source without distortion, than to be a consequence of noise. Hence, each non-zero $X_k$ is relatively informative, since the probability that it corresponds to an observation of a source is large. Indeed, we can show that in this case, for both protocols

$$ p - \frac{1}{2} \geq \frac{s}{4(s_0 + s_1)}. $$

* Conversely, when

$$ \delta \geq \frac{s_0 + s_1}{2n} (1 - |\Sigma|\delta), $$

each non-zero $X_k$ is quite likely to be the consequence of a corrupted message, implying that $p - \frac{1}{2}$ cannot be too large; in fact, we show that for both protocols, we only have

$$ p - \frac{1}{2} \geq \frac{s}{n} \frac{(1 - |\Sigma|\delta)}{8\delta}. $$

However, this drop in quality is offset by the greater number of $X_k$'s different from 0, enabling the agents to accumulate enough information.

The aforementioned computations of $p$ and $\mathbb{P}(X_k \neq 0)$ are presented in Lemma 28 for Algorithm SF, and in Lemma 36 for Algorithm SSF. From these quantities, we derive a sufficient condition on $m$ that applies to both protocols, in Lemma 23. Specifically, with the above bounds, we obtain that in the regime where $\delta \geq \frac{s_0+s_1}{2n}(1 - |\Sigma|\delta)$, it is sufficient to choose $m$ such that

$$ m \geq \frac{\delta n \log n}{s^2(1 - |\Sigma|\delta)^2}, $$

in order to satisfy Eq. (2). However, to ensure the correctness of the weak opinion across a broader range of parameters, additional additive terms for $m$ are necessary.
# 3 Conclusions and Discussion

We consider the task of spreading a binary value from a set of (possibly conflicting) *source* agents to the rest of the population, under the noisy *PULL*(*h*) model of communication, where the goal is to converge to the plurality opinion of the sources.

When the sample size *h* is small, the lower bound proved in [8] becomes linear in the group size. This result allowed the authors to predict that recruiting a few desert ants among a population, a process which could be viewed as an information spreading process under the noisy *PULL*(*h*) model, would be slower when more ants are involved. This counter-intuitive prediction was indeed verified empirically in [8]. As a general message, the authors in [8] used the linear lower bound to argue that in the case of pairwise-meeting patterns, the loss of communication structure can severely weaken the system's ability to effectively counteract noise. While a small sample size is evident in some biological scenarios [24], it is inconsistent with various other natural scenarios where agents extract information from numerous other agents simultaneously (see more details in Section 1.5). This paper provides upper bounds for the information spreading time for every *h*, which match the bounds proved in [8] up to lower order terms, thus demonstrating how a larger sample size can linearly accelerate the information spreading time.

From a heuristic perspective, the structure of our protocols, particularly Algorithm SF, can be conceptualized as comprising two main stages: a “listening stage” (Phases 0 and 1 in Algorithm SF) and a “majority-consensus stage” (Phase 2 in Algorithm SF). During the “listening stage”, unknowledgeable agents independently gather samples while refraining from relaying information, maintaining neutrality to minimize interference with the sampling process. After this period, each agent has collected enough samples to form a non-trivial “guess”. In the “majority-consensus stage”, agents then share their guesses and reinforce the prevailing majority. The simplicity and effectiveness demonstrated here for this heuristic suggest its potential applicability to information dissemination scenarios in stochastic environments.

It might be interesting to interpret natural scenarios through the lens of our findings. One example is the process of *house-hunting* observed in ant species such as *Temnothorax*. When their nest is damaged, these ants embark on a house-hunting process to find and select a new site for their colony [55, 56]. Suppose the possible nest locations have already been identified, and the remaining task is to reach a consensus on the best site. This process can be divided into two phases. In the first phase, scout ants are sent to evaluate the quality of different sites — a process that can be expected to be noisy. Upon completing an evaluation, a scout ant returns to the nest and begins a *tandem run*, leading another ant from the nest to the site. The leader moves slowly enough to keep the follower engaged, with regular pauses to ensure the follower remains close. Communication occurs through frequent physical contact, such as antennal touching. This allows the leader to adjust pace and direction, maintaining coordination with the follower, which can in turn, learn the path to the new site. When reaching the site, the newly recruited ant assesses it herself and, upon returning to the nest, repeats the tandem run process. The rate of tandem runs for a particular site depends on its quality, but each tandem run is time-consuming delaying the assessment phase. While relaying quality estimates between ants could have sped up the process, it might have also introduced errors due to the difficulty of accurately communicating those measurements. Instead, tandem runs, though slow, allow ants to gather first-hand information by evaluating the sites themselves. In the language of this paper, one may interpret the ants' strategy as investing time (performing tandem runs) to increase the number of sources (and thereby the bias) instead of attempting to relay estimates. The second phase involves a quorum-sensing mechanism, where if a sufficient number of ants are present at a site, that site is chosen by the colony. This phase bears similarities to the majority-consensus phase.

Another example is the *cooperative transport* process in longhorn “crazy ants” mentioned in Section 1.1, where a knowledgeable ant is thought to transmit directional information to the group of carrying ants. Communication there relies on ants sensing the load’s movement rather than direct interaction [12, 13]. In [12], the authors used a variant of the Voter model to demonstrate that such directional information could, theoretically, be transmitted eventually. However, the question of whether this process could be achieved quickly remained unresolved. Here, we showed that when the sample size is large, e.g., when $h = n$, the noisy information spreading problem could be solved in logarithmic time. The averaging operation over all samples gathered by an agent at a given round corresponds to a noisy sampling of the general tendency of the system [12, 52, 13, 53]. Our results thus demonstrate how sensing the general tendency in the population can suffice to quickly transmit information from a few knowledgeable individuals to the rest of the group.
Overall, in light of the above, our results suggest that in the context of reliable and efficient information dissemination, a large sample size can effectively compensate for the lack of structure in noisy environments.

**Acknowledgments.** The authors thank Ofer Feinerman for the helpful and insightful discussions regarding ants.

AK was supported by the Israel Science Foundation (https://www.isf.org.il) grant 1574/24.

ND has been supported by the AID INRIA-DGA project n°2023000872 "BioSwarm".

# 4 Handling Non-Uniform Noise

In this section, we demonstrate that, given a $\delta$-upper bounded noise matrix $N$, agents can apply an artificial noise $P$ to incoming messages such that the combined effect of $N$ and $P$ is $\delta'$-uniform, with $\delta'$ slightly exceeding $\delta$. This will allow us to focus on uniform noise when proving the correctness of our algorithms in Section 5. In what follows, we formalize this statement.

**Definition 6 (Simulation with artificial noise).** Given a protocol $\mathcal{A}$ and a (stochastic) noise matrix $P$, we say that agents simulate $\mathcal{A}$ with artificial noise $P$ when they perform the following operations. In every round, each agent replaces every sampled message $i$ by a random $\sigma \in \Sigma$, such that $\mathbb{P}(\sigma = j) = P_{ij}$. Each agent then applies protocol $\mathcal{A}$ to the resulting set of modified messages.

**Definition 7.** Let $f: [0, \frac{1}{d}) \to \mathbb{R}$ s.t. $f(0) = 0$, and for every $\delta \in (0, \frac{1}{d})$,

$$f(\delta) := \left( d + \frac{1}{2} \cdot \frac{1}{(d-1)^2} \cdot \frac{1 - d\delta}{\delta} \right)^{-1}.$$

See Figure 1 for an illustration.

**Theorem 8.** Let $N$ be a $\delta$-upper bounded noise matrix on an alphabet $\Sigma$ of size $d$, and let $\mathcal{A}$ be a protocol. Let $\delta' = f(\delta)$ as given by Definition 7. There exists a stochastic matrix $P = P(N, \delta)$, such that the simulation of $\mathcal{A}$ with artificial noise $P$ (Definition 6) under noise $N$ has the same distribution as Protocol $\mathcal{A}$ under a $\delta'$-uniform noise matrix.

The proof of Theorem 8 is given in Section 4.2.

<figure><img src="image_4.png" /><figcaption>Figure 1: Plot of function $f$ for 2 different values of $d$.</figcaption></figure>

## 4.1 Preliminary Results on the Noise Matrix

Before presenting the proof of Theorem 8, we first define several key terms and notations that will be useful for this section and establish a few intermediate results.
**Definition 9 (Stochasticity).** We say that a matrix $A \in \mathbb{R}^{n \times n}$ is weakly-stochastic if and only if the coefficients on each row sum to 1, i.e.,

$$ \forall i \in \{1, \dots, n\}, \quad \sum_{j=1}^{n} A_{ij} = 1. $$

If, in addition, all coefficients of A are non-negative, then we say that A is stochastic.

**Definition 10 (Operator norm).** For any matrix $A \in \mathbb{R}^{d \times d}$, we write $\|A\|_{\infty}$ to denote the operator norm, defined as

$$ \|A\|_{\infty} := \sup_{x \in \mathbb{R}^d} \frac{\|A \cdot x\|_{\infty}}{\|x\|_{\infty}}. \qquad (3) $$

In general, it holds that

$$ \|A\|_{\infty} = \max_{1 \le i \le d} \sum_{j=1}^{d} |A_{i,j}|. \qquad (4) $$

**Claims 11 and 12 below** outline simple properties of weakly-stochastic matrices that we will use throughout our analysis. The proofs are straightforward but we give them here, for completeness.

**Claim 11.** Let $A, B \in \mathbb{R}^{\ell \times \ell}$, for some integer $\ell$. If $AB$ is weakly-stochastic and $B$ is weakly-stochastic, then $A$ is weakly-stochastic.

*Proof.* We have for every $i \in \{1, \dots, \ell\}$,

$$ 1 = \sum_{j=1}^{\ell} (AB)_{i,j} \qquad (\text{since } AB \text{ is weakly-stochastic}) $$

$$ = \sum_{j=1}^{\ell} \sum_{k=1}^{\ell} A_{i,k} B_{k,j} = \sum_{k=1}^{\ell} \sum_{j=1}^{\ell} A_{i,k} B_{k,j} = \sum_{k=1}^{\ell} A_{i,k} \left( \sum_{j=1}^{\ell} B_{k,j} \right) $$

$$ = \sum_{k=1}^{\ell} A_{i,k}, \qquad (\text{since } B \text{ is weakly-stochastic}) $$

which concludes the proof of Claim 11. $\square$

**Claim 12.** Let $A \in \mathbb{R}^{\ell \times \ell}$. If $A$ is invertible and weakly-stochastic, then $A^{-1}$ is weakly-stochastic.

*Proof.* Since $A$ is weakly-stochastic and $A^{-1} \cdot A = I$ is weakly-stochastic, $A^{-1}$ is weakly-stochastic by Claim 11. $\square$

It is well-known that strictly diagonally dominant matrices are invertible. In what follows, we show that this result can be generalized to all $\delta$-upper bounded matrices – even though they may not be strictly diagonally dominant in general – and we bound the operator norm of their inverse. We start with a technical lemma, from which the aforementioned result will follow.

**Lemma 13.** Let $N$ be a $\delta$-upper bounded matrix of dimension $d \times d$. Then

$$ \inf_{\|x\|_{\infty}=1} \|N \cdot x\|_{\infty} \ge \frac{1-d\delta}{d-1}. $$

*Proof.* Let $S \subset \mathbb{R}^{d \times d}$ be the set of all $\delta$-upper bounded matrices of size $d$. Let $N \in S$, and $x \in \mathbb{R}^d$ s.t. $\|x\|_{\infty} = 1$. Let $I_+ = \{j : x_j \ge 0\}$ and $I_- = \{j : x_j < 0\}$. Recall that stochastic matrices are non-negative. Therefore, since we are ultimately interested in $\|N \cdot x\|_{\infty}$, we can assume w.l.o.g. (up to replacing $x$ by $-x$) that

$$ \sum_{j \in I_+} x_j \ge \sum_{j \in I_-} |x_j|. \qquad (5) $$
Let $i^* = \min\{\operatorname{argmax}_{i \in I_+} x_i\} \in I_+$. Let $f: S \to \mathbb{R}$, defined as

$$f(M) := \sum_{j \in I_+} M_{i^*j} x_j - \sum_{j \in I_-} M_{i^*j} |x_j|.$$

By the reverse triangular inequality, and since $N$ is non-negative,

$$\|N \cdot x\|_{\infty} \geq \left| \sum_{j} N_{i^*j} x_j \right| \geq \left| \sum_{j \in I_+} N_{i^*j} x_j \right| - \left| \sum_{j \in I_-} N_{i^*j} x_j \right| = f(N). \quad (6)$$

Let

$$\Delta = \sum_{j \in I_{-}} (\delta - N_{i^*j}).$$

(Since $N$ satisfies Eq. (1), $\Delta \geq 0$.) We define matrix $N'$ as

$$\left\{ \begin{array}{ll} N'_{i^*i^*} = N_{i^*i^*} - \Delta, & \\ N'_{i^*j} = N_{i^*j} & \text{for } j \in I_+, \\ N'_{i^*j} = \delta & \text{for } j \in I_- \end{array} \right.$$

The coefficients of $N'$ in rows other than $i^*$ are irrelevant, but for completeness, we may set them equal to those of $N$. By construction,

$$\sum_{j} N'_{i^*j} = \sum_{j} N_{i^*j} = 1 \quad \text{and for every } j \neq i^*, \quad 0 \le N'_{i^*j} \le \delta.$$

Therefore

$$N'_{i^*i^*} = 1 - \sum_{j \neq i^*} N_{i^*j} \geq 1 - (d-1) \cdot \delta,$$

and hence $N' \in S$. We have that

$$\left\{ \begin{array}{ll} N_{i^*j} \ge N'_{i^*j} & \text{for all } j \in I_+, \\ N_{i^*j} \le N'_{i^*j} & \text{for all } j \in I_- \end{array} \right.$$

which implies that $f(N) \ge f(N')$. Now, let us define matrix $N''$ as

$$\left\{ \begin{array}{ll} N''_{ii} = 1 - (d-1)\delta & \text{for every } i, \\ N''_{ij} = \delta & \text{for every } i, j \text{ s.t. } i \neq j. \end{array} \right.$$

Clearly $N'' \in S$. Since by definition, $x_{i^*} \ge x_j$ for all $j \in I_+$, and since

$$\left\{ \begin{array}{ll} N'_{i^*i^*} \ge N''_{i^*i^*}, & \\ N'_{i^*j} \le N''_{i^*j} & \text{for all } j \in I_+ \setminus \{i^*\}, \\ N'_{i^*j} = N''_{i^*j} & \text{for all } j \in I_-, \end{array} \right.$$

we have that $f(N') \ge f(N'')$. By Eq. (5), we can give a lower bound on $f(N'')$:

$$f(N'') = \delta \sum_{j \in I_+} x_j + (1 - d\delta) x_{i^*} - \delta \sum_{j \in I_-} |x_j| \ge (1 - d\delta) x_{i^*}.$$

From Eq. (6) and since we have shown that $f(N) \ge f(N') \ge f(N'')$, this implies that

$$\|N \cdot x\|_{\infty} \ge (1 - d\delta) x_{i^*}.$$

To conclude, we will show that

$$x_{i^*} \ge \frac{1}{d-1} \qquad (7)$$
If $x_{i*} \ge 1$, Eq. (7) holds trivially, so we only have to consider the case that $x_{i*} < 1$. Recall that $\|x\|_{\infty} = 1$, and since $0 \le x_j \le x_{i*} < 1$ for every $j \in I_+$, there necessarily exists $k \in I_-$ s.t. $x_k = -1$. By Eq. (5),

$$ \sum_{j \in I_+} x_j \ge \sum_{j \in I_-} |x_j| \ge |x_k| = 1. $$

Note that $|I_+| \le d - 1$ since at least $k \in I_-$. Moreover, $x_{i*} \ge x_j$ for all $j \in I_+$, which implies Eq. (7) and concludes the proof of Lemma 13. □

**Corollary 14.** Let $N$ be a $\delta$-upper bounded matrix of dimension $d \times d$. Then $N$ is invertible, and

$$ \|N^{-1}\|_{\infty} \le \frac{d-1}{1-d\delta}. $$

*Proof.* Let $N \in S$. Lemma 13 implies that $N$ is invertible. Indeed, if it was not the case, there would exist a vector $v \in \mathbb{R}^d$ with $\|v\|_{\infty} = 1$ (and hence $v \ne 0$) s.t. $N \cdot v = 0$, which would contradict the lower bound in Lemma 13. Moreover, we can rewrite the norm of $N^{-1}$ (defined in Eq. (3)) as

$$ \|N^{-1}\|_{\infty} = \sup_{x \in \mathbb{R}^d} \frac{\|N^{-1} \cdot x\|_{\infty}}{\|x\|_{\infty}} = \sup_{y \in \mathbb{R}^d} \frac{\|y\|_{\infty}}{\|N \cdot y\|_{\infty}}, $$

by substituting $y = N^{-1} \cdot x$. Therefore,

$$ \|N^{-1}\|_{\infty} = \sup_{y \in \mathbb{R}^d} \frac{\|y\|_{\infty}}{\|N \cdot y\|_{\infty}} = \sup_{y \in \mathbb{R}^d} \frac{1}{\|N \cdot \frac{y}{\|y\|_{\infty}}\|_{\infty}} = \left( \inf_{\|y\|_{\infty}=1} \|N \cdot y\|_{\infty} \right)^{-1}. $$

By Lemma 13, this implies

$$ \|N^{-1}\|_{\infty} \le \frac{d-1}{1-d\delta}, $$

which concludes the proof of Corollary 14. □

## 4.2 Proof of Theorem 8

First, let us observe some properties of the function $f$, given in Definition 7.

**Claim 15.** Function $f$ is continuous and increasing on $[0, \frac{1}{d})$, and for every $\delta$ in this interval,

$$ 0 = f(0) \le f(\delta) < f(\frac{1}{d}) = \frac{1}{d}. $$

*Proof.* Let $g: \delta \to f(\delta)^{-1}$. The function $g$ is clearly well-defined, positive, and decreasing on the interval $(0, \frac{1}{d})$. Moreover, $g(\frac{1}{d}) = d$, and

$$ \lim_{\delta \to 0} g(\delta) = +\infty, $$

which concludes the proof of Claim 15. □

We now prove the main result of the section, from which Theorem 8 follows directly.

**Proposition 16.** Let $N$ be a $\delta$-upper bounded noise matrix on an alphabet $\Sigma$ of size $d$. There exists a stochastic matrix $P$ such that $N \cdot P$ is $\delta'$-uniform, where $\delta' = f(\delta)$ is given by Definition 7.

*Proof.* Let $\delta' = f(\delta)$ as given by Definition 7, and let $T$ be the $\delta'$-uniform noise matrix on $\Sigma$, i.e.,

$$ T_{i,j} = \begin{cases} 1 - (d-1)\delta' & \text{for } i = j, \\ \delta' & \text{for } i \ne j. \end{cases} $$

By Corollary 14, $N$ is invertible, and we can consider the matrix $P := N^{-1} \cdot T$. By Claims 11 and 12, $P$ is weakly stochastic. Now, we will show that $P$ is stochastic. Let

$$ i^*, j^* := \underset{i,j}{\operatorname{argmin}} \{N_{i,j}^{-1}\}. $$
**Claim 17.** We have that

$$-N_{i^*j^*}^{-1} \le 2(d-1)^2 \cdot \frac{\delta}{1-d\delta}.$$

*Proof of Claim 17.* By Corollary 14,

$$-N_{i^*,j^*}^{-1} \le -N_{i^*,j^*}^{-1} + \mathbb{1}(i^* = j^*) \le |N_{i^*,j^*}^{-1} - \mathbb{1}(i^* = j^*)| \le \|N^{-1} - I\|_{\infty} = \|N^{-1}(I - N)\|_{\infty} \\ \le \|N^{-1}\|_{\infty} \cdot \|(I - N)\|_{\infty} \le \frac{d-1}{1-d\delta} \cdot \|(I - N)\|_{\infty}.$$

Moreover,

$$\| (I - N) \|_{\infty} = \max_{1 \le i \le d} \sum_{j=1}^{d} | (I - N)_{i,j} | \qquad \text{(by Eq. (4))} \\ \le 1 - (1 - (d-1)\delta) + (d-1)\delta \qquad \text{(since N satisfies Eq. (1))} \\ = 2(d-1) \cdot \delta,$$

which concludes the proof of Claim 17.

<figure><img src="image_5.png" /></figure>

Assuming $N_{i^*j^*}^{-1} \ne 0$, we have

$$\begin{align*} \delta' = f(\delta) &= \left(d + \frac{1}{2} \cdot \frac{1}{(d-1)^2} \cdot \frac{1-d\delta}{\delta}\right)^{-1} \qquad \text{(restating Definition 7)} \\ &\ge \left(d - \frac{1}{N_{i^*j^*}^{-1}}\right)^{-1} \qquad \text{(by Claim 17)} \\ &= \frac{-N_{i^*j^*}^{-1}}{1 - N_{i^*j^*}^{-1} \cdot d}. \end{align*}$$

Note that the inequality holds trivially when $N_{i^*j^*}^{-1} = 0$. It can be rewritten as

$$(1 - d\delta') \cdot N_{i^*j^*}^{-1} + \delta' \ge 0. \qquad (8)$$

Finally, for every $i, j \in \{1, \dots, d\}$,

$$\begin{align*} P_{i,j} &= (1 - (d-1)\delta')N_{i,j}^{-1} + \delta' \left(\sum_{k \ne j} N_{i,k}^{-1}\right) && \text{(by definition since } P := N^{-1} \cdot T) \\ &= (1 - d\delta') \cdot N_{i,j}^{-1} + \delta' && \text{(since N is weakly-stochastic)} \\ &\ge (1 - d\delta') \cdot N_{i^*j^*}^{-1} + \delta' && \text{(by definition of } i^*, j^* \text{ and since } (1 - d\delta') \ge 0) \\ &\ge 0. && \text{(by Eq. (8))} \end{align*}$$

Therefore, $P$ is stochastic, which concludes the proof of Proposition 16.

<figure><img src="image_6.png" /></figure>

Having proved the existence of a suitable artificial noise matrix $P$ so that the original noise matrix $N$ can be transformed into a uniform noise matrix $T$, it remains to show, to complete the proof of Theorem 8, that the distribution of received messages for agents using such artificial noise is effectively the same as if the original noise were described by $T$.

*Proof of Theorem 8.* Let $\delta' = f(\delta)$ and $P$ a stochastic matrix of artificial noise such that $T := N \cdot P$ is a $\delta'$-uniform matrix, as given by Proposition 16. Consider the case that one agent $u$ observes another agent $v$ in round $t$. We define the following variables:

* $\sigma_v$ is the message originally displayed by Agent $v$;

* $\sigma_{v \to T}$ is the message obtained by applying the noise $T = N \cdot P$ to $\sigma_v$;
• $\sigma_{v \to N}$ is the message obtained by applying the original noise $N$ to $\sigma_v$;

• $\sigma_{N \to P}$ is the message obtained by applying the artificial noise $P$ to $\sigma_{v \to N}$.

For every $i, j \in \Sigma$,

$$ \begin{aligned} \mathbb{P}(\sigma_{N \to P} = j | \sigma_v = i) &= \sum_{k \in \Sigma} \mathbb{P}(\sigma_{v \to N} = k | \sigma_v = i) \cdot \mathbb{P}(\sigma_{N \to P} = j | \sigma_v = i, \sigma_{v \to N} = k) \\ &= \sum_{k \in \Sigma} N_{i,k} \cdot P_{k,j} = T_{i,j} = \mathbb{P}(\sigma_{v \to T} = j | \sigma_v = i), \end{aligned} $$

which shows that if agent $u$ applies the artificial noise matrix $P$ to the received messages, her received message is distributed as if the noise matrix was $T$, concluding the proof. □

# 5 Analysis with Uniform Noise

In this section we show the correctness of Algorithms SF and SSF in the case that the noise matrix $N$ is $\delta$-uniform. Section 5.1 establishes probabilistic results and Section 5.2 introduces notations that are used in the analysis of both algorithms. Finally, Section 5.3 and Section 5.4 focus respectively on the analysis of Algorithms SF and SSF. We recommend referring to Section 2.3 for an informal overview of the proofs presented here.

## 5.1 Preliminary Results in Probability

**Definition 18 (Rademacher distribution).** We say that a random variable $X$ follows a Rademacher distribution with parameter $p$, and write $X \sim \text{Rad}(p)$, if it takes value in $\{-1, 1\}$ and $\mathbb{P}(X = 1) = p$.

The following result is a direct observation concerning binomial random variables with a small success probability parameter $p$.

**Claim 19.** Let $X \sim \text{Binomial}(n, p)$. If $np \le 1$, then

$$ \mathbb{P}(X = 1) \ge \frac{1}{e} np. $$

*Proof.* Let $u_n = (1 - \frac{1}{n})^{n-1}$. $(u_n)_{n \ge 1}$ is decreasing and $\lim_{n \to +\infty} u_n = \frac{1}{e}$, so $u_n \ge \frac{1}{e}$ for every $n \ge 1$. Therefore,

$$ \begin{aligned} \mathbb{P}(X = 1) ={}& np(1-p)^{n-1} \ge npu_n & (\text{since } p \le \frac{1}{n}) \\ & \ge \frac{1}{e}np, \end{aligned} $$

which concludes the proof of Claim 19. □

As outlined informally in Section 2.3, our analysis will later introduce random variables $X_k$ that take values in $\{-1, 0, 1\}$. We will focus specifically on the non-zero variables, treating them as Rademacher variables. The following result formalizes this approach and addresses potential dependency issues.

**Lemma 20.** Let $\{X_i\}_{i=1,...,m}$ be i.i.d. random variables taking values in $\{-1, 0, 1\}$. Let $Y$ be the number of $X_i$ with non-zero value, i.e.,

$$ Y = \left| \{i = 1, \dots, m : X_i \neq 0\} \right|. $$

Let $X = \sum_{i=1}^m X_i$. Conditioning on $\{Y = r\}$, $X$ is distributed as a sum of $r$ Rademacher random variables with parameter $p = \mathbb{P}(X_i = 1 | X_i \neq 0)$.

*Proof.* Let $a = (a_1, ..., a_m) \in \{0, 1\}^m$. Let $\mathcal{E}(a)$ be the event that non-zero elements of $\{X_i\}_{i=1,...,m}$ corresponds to non-zero elements of $a$, i.e.,

$$ \mathcal{E}(a) := \bigcap_{i=1}^{m} \{ |X_i| = a_i \}. $$
Similarly, we write $\mathcal{E}_k(a)$ to denote the same event, without the condition on the element at index $k$:

$$ \mathcal{E}_k(a) := \bigcap_{\substack{i=1 \\ i \neq k}}^{m} \{|X_i| = a_i\}. $$

Note that all $\{\mathcal{E}(a)\}_{a \in \{0,1\}^m}$ are disjoint. Moreover, writing $|a| = \sum_{i=1}^m a_i$, we have

$$ \{Y = r\} = \bigcup_{\substack{a \in \{0,1\}^m \\ |a|=r}} \mathcal{E}(a). $$

Since all $\{X_i\}_{i=1,...,m}$ are mutually independent, $X_k$ and $\mathcal{E}_k$ are also independent. We have

$$
\begin{align*}
\mathbb{P}(X_k = 1 | X_k \neq 0, Y = r) &= \frac{\mathbb{P}(X_k = 1, Y = r)}{\mathbb{P}(X_k \neq 0, Y = r)} \\
&= \frac{\sum_{|a|=r} \mathbb{P}(X_k = 1, \mathcal{E}(a))}{\sum_{|a|=r} \mathbb{P}(X_k \neq 0, \mathcal{E}(a))} \\
&= \frac{\sum_{a_k=1} \mathbb{P}(X_k = 1, \mathcal{E}(a))}{\sum_{a_k=1} \mathbb{P}(X_k \neq 0, \mathcal{E}(a))} \quad (\text{when } a_k = 0, \mathbb{P}(X_k \neq 0, \mathcal{E}(a)) = 0) \\
&= \frac{\sum_{a_k=1} \mathbb{P}(X_k = 1, \mathcal{E}_k(a))}{\sum_{a_k=1} \mathbb{P}(X_k \neq 0, \mathcal{E}_k(a))} \\
&= \frac{\sum_{a_k=1} \mathbb{P}(X_k = 1) \cdot \mathbb{P}(\mathcal{E}_k(a))}{\sum_{a_k=1} \mathbb{P}(X_k \neq 0) \cdot \mathbb{P}(\mathcal{E}_k(a))} \quad (X_k \text{ and } \mathcal{E}_k(a) \text{ being independent}) \\
&= \frac{\mathbb{P}(X_k = 1)}{\mathbb{P}(X_k \neq 0)} = \mathbb{P}(X_k = 1 | X_k \neq 0).
\end{align*}
$$

Moreover, for any $x \in \mathbb{Z}$, we have

$$
\begin{align*}
\mathbb{P}(X = x | Y = r) &= \mathbb{P}\left(\sum_i X_i = x \mid Y = r\right) \\
&= \sum_{|a|=r} \mathbb{P}(\mathcal{E}(a) \mid Y = r) \cdot \mathbb{P}\left(\sum_i X_i = x \mid \mathcal{E}(a)\right) \\
&= \sum_{|a|=r} \mathbb{P}(\mathcal{E}(a) \mid Y = r) \cdot \mathbb{P}\left(\sum_{i:a_i=1} X_i + \sum_{i:a_i=0} X_i = x \mid \mathcal{E}(a)\right) \\
&= \sum_{|a|=r} \mathbb{P}(\mathcal{E}(a) \mid Y = r) \cdot \mathbb{P}\left(\sum_{i:a_i=1} X_i = x \mid \mathcal{E}(a)\right) \\
&= \sum_{|a|=r} \mathbb{P}(\mathcal{E}(a) \mid Y = r) \cdot \mathbb{P}\left(\sum_{i:a_i=1} X_i = x \mid \bigcap_{i:a_i=1} \{X_i \neq 0\}\right) \\
&= \sum_{|a|=r} \mathbb{P}(\mathcal{E}(a) \mid Y = r) \cdot \mathbb{P}\left(\sum_{i=1}^r X_i = x \mid \bigcap_{i=1}^r \{X_i \neq 0\}\right) \quad (X_i \text{ are i.i.d.}) \\
&= \mathbb{P}\left(\sum_{i=1}^r X_i = x \mid \bigcap_{i=1}^r \{X_i \neq 0\}\right),
\end{align*}
$$

which concludes the proof of Lemma 20. $\square$
The next lemma recalls an existing lower bound on the probability to obtain more “heads” than “tails”, when throwing a biased coin m times.

**Lemma 21** (From Lemma 9 in [17]). Let $\theta > 0$ and $B \sim \text{Binomial}(m, 1/2 + \theta)$. Then,

$$ \mathbb{P}\left(B > \frac{m}{2}\right) - \mathbb{P}\left(B < \frac{m}{2}\right) \geq \sqrt{\frac{2m}{\pi}} \cdot g(\theta, m), $$

where

$$ g(\theta, m) = \begin{cases} \theta (1 - \theta^2)^{\frac{m-1}{2}} & \text{if } \theta < \frac{1}{\sqrt{m}}, \\ \frac{1}{\sqrt{m}} (1 - \frac{1}{m})^{\frac{m-1}{2}} & \text{if } \theta \ge \frac{1}{\sqrt{m}}. \end{cases} $$

*Proof.* We note that

$$ \begin{aligned} \mathbb{P}\left(B > \frac{m}{2}\right) - \mathbb{P}\left(B < \frac{m}{2}\right) &= \mathbb{P}\left(B \ge \frac{m}{2}\right) - \mathbb{P}\left(B \le \frac{m}{2}\right) \\ &= \sum_{k=\lceil m/2 \rceil}^{m} \binom{m}{k} p^k (1-p)^{m-k} - \sum_{k=\lceil m/2 \rceil}^{m} \binom{m}{k} p^{m-k} (1-p)^k, \end{aligned} $$

and then we proceed as in the proof of [17, Lemma 9]. Please note that in this paper, the definition of $g$ contains a typographical error; the correct definition is the one provided here. □

Next, we rewrite the previous statement in a more convenient way for our analysis.

**Lemma 22.** Let $0 \le \theta < 1/2$ and $m > 0$, and consider i.i.d. random variables $\{X_i\}_{i=1,...,m} \sim \text{Rad}(\frac{1}{2} + \theta)$. Then, $X = \sum_{i=1}^{m} X_i$ satisfies

$$ \mathbb{P}(X > 0) - \mathbb{P}(X < 0) \geq \sqrt{\frac{2}{\pi e}} \cdot \min\{\sqrt{m}\theta, 1\}. $$

*Proof.* For $i \in \{1, ..., m\}$, let $B_i = (X_i + 1)/2$, and let $B = \sum_{i=1}^{m} B_i$. By definition, $B \sim \text{Binomial}(m, \frac{1}{2} + \theta)$ and $\{X > 0\} = \{B > \frac{m}{2}\}$.

* First, consider the case that $\theta \ge \frac{1}{\sqrt{m}}$. By Lemma 21, we have

$$ \mathbb{P}(X > 0) - \mathbb{P}(X < 0) \geq \sqrt{\frac{2m}{\pi}} \cdot \frac{(1 - 1/m)^{\frac{m-1}{2}}}{\sqrt{m}} \geq \sqrt{\frac{2m}{\pi e}}, $$

where we used the fact $x \mapsto (1 - 1/x)^{\frac{x-1}{2}}$ is decreasing and that $\lim_{x \to \infty} (1 - 1/x)^{\frac{x-1}{2}} = e^{-1/2}$.

* Now, consider the case that $\theta < \frac{1}{\sqrt{m}}$. In that case,

$$ (1 - \theta^2)^{\frac{m-1}{2}} \geq \left(1 - \frac{1}{m}\right)^{\frac{m-1}{2}} \geq e^{-1/2}, $$

and by Lemma 21, we have

$$ \mathbb{P}(X > 0) - \mathbb{P}(X < 0) \geq \sqrt{\frac{2m}{\pi e}}\theta, $$

which concludes the proof of Lemma 22. □

Finally, the following result identifies necessary conditions for correctly identifying the bias with probability at least $1/2 + \Omega(\sqrt{\log n/n})$, when observing a sum of random variables with values in $\{-1, 0, 1\}$. It will be used as a black box when asserting the quality of the agents' weak-opinions in the analysis of Algorithms SF and SSF.
**Lemma 23.** Let $m \in \mathbb{N}$ and $\delta < 1/|\Sigma|$, and consider i.i.d. random variables $\{X_k\}_{k=1,...,m}$ taking values in $\{-1,0,1\}$. Let $X = \sum_{k=1}^m X_k$, and
$$p := \mathbb{P}(X_k = 1 | X_k \neq 0).$$

There exists a constant $c_1 > 0$, s.t. if the following conditions hold:

$$m \ge c_1 \left( \frac{n\delta \log n}{\min\{s^2, n\}(1 - |\Sigma|\delta)^2} + \frac{\sqrt{n} \log n}{s} + \frac{(s_0 + s_1) \log n}{s^2} + \log n \right), \quad (9)$$

$$\mathbb{P}(X_k \neq 0) \geq (1 - |\Sigma|\delta)^2 \cdot \frac{s_0 + s_1}{2n} + \delta, \quad (10)$$

$$\delta \ge \frac{s_0 + s_1}{2n} (1 - |\Sigma|\delta) \quad \implies \quad p \ge \frac{1}{2} + \frac{s(1 - |\Sigma|\delta)}{8\delta}, \quad (11)$$

$$\delta < \frac{s_0 + s_1}{2n} (1 - |\Sigma|\delta) \quad \implies \quad p \ge \frac{1}{2} + \frac{s}{4(s_0 + s_1)}, \quad (12)$$

then for $n$ large enough,

$$\mathbb{P}(X > 0) - \mathbb{P}(X < 0) \ge 8\sqrt{\frac{\log n}{n}}.$$

*Proof.* We begin the proof with a technical computation that will be used multiple times.

**Claim 24.** If $\delta < \frac{s_0+s_1}{2n}(1 - |\Sigma|\delta)$, then $(1 - |\Sigma|\delta)^2 \ge \frac{1}{4}$ for $n$ large enough.

*Proof of Claim 24.* We have

$$\delta < \frac{s_0 + s_1}{2n} (1 - |\Sigma|\delta) \le \frac{1}{2} (1 - |\Sigma|\delta),$$

where in the last inequality we used that $s_0 + s_1 \le n$. This inequality can be rewritten as

$$\delta \le \frac{1}{2 + |\Sigma|}.$$

This implies that

$$(1 - |\Sigma|\delta)^2 \ge \left(1 - \frac{|\Sigma|}{2 + |\Sigma|}\right)^2 \ge \frac{1}{4},$$

where in the last inequality we used that, since $|\Sigma| \ge 2$, we have $\frac{|\Sigma|}{2+|\Sigma|} \le \frac{1}{2}$. This concludes the proof of **Claim 24**. $\square$

Now, let $Y$ denote the number of $k$ for which $X_k \neq 0$. Formally,

$$Y = \left| \{k = 1, \dots, m : X_k \neq 0\} \right|.$$

$Y$ follows a binomial distribution with parameters $\mathbb{P}(X_k \neq 0)$, and $m$. The next two claims consider the case that $Y$ is relatively large, namely, that $\mathbb{E}(Y) \ge 1$. In this regime, the sum $X$ contains enough information about the bias, because many $X_k$s are different from 0. In **Claim 25**, we translate the lower-bound on the expectation of $Y$, into a lower-bound that holds with constant probability. Then, in **Claim 26**, we prove the statement in the case that $Y$ is sufficiently large.

**Claim 25.** If $\mathbb{E}(Y) \ge 1$, there is a constant $c_2 > 0$, such that

$$\mathbb{P}\left(Y > \frac{\mathbb{E}(Y)}{2}\right) \ge c_2.$$
Proof of Claim 25. Recall that $Y$ follows a binomial distribution with parameter $m$, $\mathbb{P}(X_k \neq 0)$. We have

$$
\begin{align*}
\mathbb{P}\left(Y \le \frac{1}{2} \mathbb{E}(Y)\right) &\le \mathbb{P}\left(Y \le \left(1 - \frac{1}{2}\right) \mathbb{E}(Y)\right) \\
&\le \exp\left(-\frac{1}{8} \mathbb{E}(Y)\right) \quad \text{(by the Multiplicative Chernoff's bound)} \\
&\le \exp\left(-\frac{1}{8}\right), \quad \mathbb{E}(Y) \ge 1.
\end{align*}
$$

We conclude the proof of Claim 25 by taking $c_2 = 1 - \exp(-\frac{1}{8})$. $\square$

**Claim 26.** If $\mathbb{E}(Y) \ge 1$, and if $c_1$ from Eq. (9) is large enough, then for every $r \ge \mathbb{E}(Y)/2$,

$$ \mathbb{P}(X > 0 | Y = r) - \mathbb{P}(X < 0 | Y = r) \ge \frac{8}{c_2} \sqrt{\frac{\log n}{n}}. $$

Proof of Claim 26. Let $r \ge \mathbb{E}(Y)/2$. By Lemma 20, conditioning on $\{Y = r\}$, $X$ is a sum of $r$ Rademacher random variables of parameter $p := \mathbb{P}(X_k = 1 | X_k \neq 0)$. Then, we can apply Lemma 22 to obtain

$$ \mathbb{P}(X > 0 | Y = r) - \mathbb{P}(X < 0 | Y = r) \ge \sqrt{\frac{2}{\pi e}} \min \left\{ \sqrt{r} \left(p - \frac{1}{2}\right), 1 \right\}. \quad (13) $$

We distinguish between two cases, depending on the value of $\delta$.

• **Case 1.** Assume that $\delta < \frac{s_0+s_1}{2n} (1 - |\Sigma|\delta)$. Then,

$$ \mathbb{P}(X_k \neq 0) \stackrel{\text{Eq. (10)}}{\ge} (1 - |\Sigma|\delta)^2 \cdot \frac{s_0 + s_1}{2n} + \delta \stackrel{\text{Claim 24}}{\ge} \frac{s_0 + s_1}{8n}. $$

Therefore, by Eq. (9),

$$ \mathbb{E}(Y) = m \cdot \mathbb{P}(X_k \neq 0) \ge c_1 \cdot \frac{(s_0 + s_1) \log n}{s^2} \cdot \frac{s_0 + s_1}{8n}, $$

and thus,

$$ r \ge \frac{\mathbb{E}(Y)}{2} \ge c_1 \cdot \frac{(s_0 + s_1)^2 \log n}{16 s^2 n}. \quad (14) $$

Finally,

$$
\begin{align*}
& \mathbb{P}(X > 0 | Y = r) - \mathbb{P}(X < 0 | Y = r) \\
&\ge \sqrt{\frac{2}{\pi e}} \min \left\{ \sqrt{r} \left(p - \frac{1}{2}\right), 1 \right\} \tag{by Eq. (13)} \\
&\ge \sqrt{\frac{2}{\pi e}} \min \left\{ \sqrt{c_1 \cdot \frac{(s_0 + s_1)^2 \log n}{16 s^2 n}} \cdot \frac{s}{4(s_0 + s_1)}, 1 \right\} \tag{by Eqs. (12) and (14)} \\
&= \sqrt{\frac{2}{\pi e}} \min \left\{ \frac{\sqrt{c_1}}{16} \sqrt{\frac{\log n}{n}}, 1 \right\} \\
&\ge \frac{8}{c_2} \sqrt{\frac{\log n}{n}}, \tag*{(as long as $c_1$ is large enough)}
\end{align*}
$$

which concludes the proof of Case 1.

• **Case 2.** Now, assume that $\delta \ge \frac{s_0+s_1}{2n} (1 - |\Sigma|\delta)$. We have

$$ r \ge \frac{E(Y)}{2} = \frac{1}{2} \cdot m \mathbb{P}(X_k \neq 0) \stackrel{\text{Eq. (10)}}{\ge} \frac{1}{2} \cdot m \delta \stackrel{\text{Eq. (9)}}{\ge} c_1 \cdot \frac{n \delta^2 \log n}{2 \min\{s^2, n\} (1 - |\Sigma|\delta)^2}. \quad (15) $$
Finally,

$$
\begin{align*}
& \mathbb{P}(X > 0 | Y = r) - \mathbb{P}(X < 0 | Y = r) \\
\ge & \sqrt{\frac{2}{\pi e}} \min \left\{ \sqrt{r} \left(p - \frac{1}{2}\right), 1 \right\} \tag*{\text{(by Eq. (13))}} \\
\ge & \sqrt{\frac{2}{\pi e}} \min \left\{ \sqrt{c_1} \cdot \frac{\delta \sqrt{n \log n}}{\min\{s, \sqrt{n}\} (1 - |\Sigma|\delta)} \cdot \frac{s}{n} \frac{(1 - |\Sigma|\delta)}{8\delta}, 1 \right\} \tag*{\text{(by Eqs. (11) and (15))}} \\
\ge & \sqrt{\frac{2}{\pi e}} \min \left\{ \frac{\sqrt{c_1}}{8} \sqrt{\frac{\log n}{n}}, 1 \right\} \ge \frac{8}{c_2} \sqrt{\frac{\log n}{n}},
\end{align*}
$$

where as above, $c_1$ is assumed to be large enough.

This concludes the proof of Claim 26.

<figure><img src="image_7.png" /></figure>

Now, we consider the case that $Y$ is relatively small, that is, $\mathbb{E}(Y) \le 1$. In this regime, few $X_k$s are different from 0, but each non-zero $X_k$ is equal to 1 with a sufficiently large probability. The following result formalizes this claim, by focusing on the event $\{Y = 1\}$.

**Claim 27.** If $\mathbb{E}(Y) \le 1$, we have

$$ \mathbb{P}(Y=1) \cdot \left[ \mathbb{P}(X > 0 | Y=1) - \mathbb{P}(X < 0 | Y=1) \right] \ge 8 \sqrt{\frac{\log n}{n}}. $$

*Proof of Claim 27.* We have

$$ \mathbb{P}(Y=1) \ge \frac{1}{e} m \cdot \mathbb{P}(X_k \ne 0) \tag*{\text{(by Claim 19)}} $$

$$ \ge \frac{1}{e} m \cdot \left( (1 - |\Sigma|\delta)^2 \cdot \frac{s_0 + s_1}{2n} + \delta \right) \tag*{\text{(by Eq. (10))}} $$

$$ \ge \frac{\sqrt{n} \log n}{e s} \left( (1 - |\Sigma|\delta)^2 \cdot \frac{s_0 + s_1}{2n} + \delta \right). \tag*{\text{(by Eq. (9))}} $$

Conditioning on $\{Y = 1\}$, $X$ is a single Rademacher random variable with parameter $p$. Therefore,

$$ \mathbb{P}(X > 0 | Y = 1) - \mathbb{P}(X < 0 | Y = 1) = 2 \left( p - \frac{1}{2} \right), $$

and together with the last equation, we obtain

$$ \mathbb{P}(Y=1) \cdot \left[ \mathbb{P}(X > 0 | Y=1) - \mathbb{P}(X < 0 | Y=1) \right] \\
\ge \frac{\sqrt{n} \log n}{e s} \left( (1 - |\Sigma|\delta)^2 \cdot \frac{s_0 + s_1}{2n} + \delta \right) \cdot 2 \left( p - \frac{1}{2} \right). \quad (16) $$

As in the proof of Claim 26, we distinguish between two cases, depending on the value of $\delta$.

• **Case 1.** Consider the case that $\delta < \frac{s_0+s_1}{2n}(1 - |\Sigma|\delta)$. We can rewrite Eq. (16) as

$$
\begin{align*}
& \mathbb{P}(Y=1) \cdot \left[ \mathbb{P}(X > 0 | Y=1) - \mathbb{P}(X < 0 | Y=1) \right] \\
\ge & \frac{\sqrt{n} \log n}{e s} \left( (1 - |\Sigma|\delta)^2 \cdot \frac{s_0 + s_1}{2n} + \delta \right) \cdot 2 \left( p - \frac{1}{2} \right) \\
\ge & \frac{\sqrt{n} \log n}{e s} \cdot \frac{s_0 + s_1}{8n} \cdot 2 \left( p - \frac{1}{2} \right) \tag*{\text{(by Claim 24)}} \\
\ge & \frac{\sqrt{n} \log n}{e s} \cdot \frac{s_0 + s_1}{8n} \cdot 2 \cdot \frac{s}{4(s_0 + s_1)} \tag*{\text{(by Eq. (12))}} \\
= & \frac{\log n}{16 e \sqrt{n}} \ge 8 \sqrt{\frac{\log n}{n}}.
\end{align*}
$$
• Case 2. Now, consider the case that $\delta \ge \frac{s_0+s_1}{2n}(1 - |\Sigma|\delta)$. Again, we rewrite Eq. (16) as

$$ 
\begin{aligned}
& \mathbb{P}(Y=1) \cdot [\mathbb{P}(X>0 | Y=1) - \mathbb{P}(X<0 | Y=1)] \\
& \ge \frac{\sqrt{n} \log n}{e s} \left( (1 - |\Sigma|\delta)^2 \cdot \frac{s_0 + s_1}{2n} + \delta \right) \cdot 2 \left( p - \frac{1}{2} \right) \\
& \ge \frac{\sqrt{n} \log n}{e s} \cdot \delta \cdot 2 \left( p - \frac{1}{2} \right) \\
& \ge \frac{\sqrt{n} \log n}{e s} \cdot \delta \cdot 2 \cdot \frac{s (1 - |\Sigma|\delta)}{n 8 \delta} \quad \text{(by Eq. (11))} \\
& = \frac{\log n}{4e\sqrt{n}} \cdot (1 - |\Sigma|\delta).
\end{aligned} 
\quad (17) $$

By Eq. (10), $\mathbb{E}(Y) = m\mathbb{P}(X_k \neq 0) \ge m\delta$, therefore $\frac{1}{m} > \frac{\mathbb{E}(Y)}{m} \ge \delta$. For $n \to \infty$, we have $m \ge \log n \to \infty$ and therefore $\delta \to 0$. Then, for $n$ large enough, $(1 - |\Sigma|\delta) \ge \frac{1}{2}$ and by Eq. (17) we finally obtain

$$ \mathbb{P}(Y=1) \ge \frac{\log n}{8e\sqrt{n}} \ge 8\sqrt{\frac{\log n}{n}}. $$

This concludes the proof of Claim 27.

<figure><img src="image_8.png" /></figure>

Now we have the tools to conclude the proof of Lemma 23. If $\mathbb{E}(Y) \ge 1$,

$$ 
\begin{aligned}
\mathbb{P}(X > 0) - \mathbb{P}(X < 0) &\ge \sum_{r=\mathbb{E}(Y)/2}^{m} \mathbb{P}(Y=r) \cdot [\mathbb{P}(X > 0 | Y=r) - \mathbb{P}(X < 0 | Y=r)] \\
&\ge \frac{8}{c_2} \sqrt{\frac{\log n}{n}} \cdot \mathbb{P}\left(Y \ge \frac{\mathbb{E}(Y)}{2}\right) \quad \text{(by Claim 26)}
\end{aligned} 
$$

$$ \ge 8\sqrt{\frac{\log n}{n}}. \quad \text{(by Claim 25)} $$

If, instead, $\mathbb{E}(Y) < 1$,

$$ 
\begin{aligned}
\mathbb{P}(X > 0) - \mathbb{P}(X < 0) &\ge \mathbb{P}(Y = 1) \cdot [\mathbb{P}(X > 0 | Y = 1) - \mathbb{P}(X < 0 | Y = 1)] \\
&\ge 8\sqrt{\frac{\log n}{n}}. \quad \text{(by Claim 27)}
\end{aligned} 
$$

This concludes the proof of Lemma 23.

<figure><img src="image_9.png" /></figure>

## 5.2 Notation

Before proceeding with the analysis of Algorithms SF and SSF, we establish some notation. Recall that we write $s_i$ to denote the number of sources supporting opinion $i \in \{0, 1\}$, and denote the bias by $s := |s_1 - s_0| \ge 1$. Recall that we assume that

$$ s_0, s_1 \le n/4. \quad (18) $$

Without loss of generality (both our protocols being symmetric), we will assume throughout this section that the correct opinion is 1, i.e., that $s_1 > s_0$. Recall that $Y_t^{(i)}$ and $\tilde{Y}_t^{(i)}$ denote respectively the opinion and weak-opinion of Agent $i$ in round $t$. In what follows, we introduce a few other random variables that we will use in the analysis.

• For $\ell \in \{1, \dots, h\}$, let $S_{t,\ell}^{(i)} \in I^h$ be the index of the $\ell$th agent sampled by Agent $i$ in round $t$. Following our model, sampling occurs uniformly at random with replacement, therefore $S_{t,\ell}^{(i)}$ is uniformly distributed in $I = \{1, \dots, n\}$.
* For $\ell \in \{1, \dots, h\}$, let $N_{t,\ell}^{(i)}$ be the noise affecting the $\ell^{th}$ message received by Agent $i$ in round $t$. Formally, we define $N_{t,\ell}^{(i)}$ as a random map from $\Sigma$ to $\Sigma$, with the understanding that if the $\ell^{th}$ message was originally displayed as $\sigma$, then Agent $i$ receives $N_{t,\ell}^{(i)}(\sigma)$.

* Let $C_t^{(i)} \in \{0, 1\}$ be the value of the coin toss performed by Agent $i$ to break ties when performing a majority operation in round $t$. By definition, $C_t^{(i)}$ is uniformly distributed in $\{0, 1\}$.

Moreover, we write $S_t^{(i)} := (S_{t,\ell}^{(i)})_{\ell \in \{1, \dots, h\}}$ and $N_t^{(i)} := (N_{t,\ell}^{(i)})_{\ell \in \{1, \dots, h\}}$. Since sampling, noise and coin tosses are independent, all variables $\{S_t^{(i)}, N_t^{(i)}, C_t^{(i)}\}_{i \in I, t \in \mathbb{N}}$ are mutually independent.

## 5.3 Analysis of Algorithm SF

In this section, we present the proof of Theorem 4. Consequently, we will always assume that the parameter $m$ used in Algorithm SF satisfies

$$m \ge c_1 \left( \frac{n \delta \log n}{\min\{s^2, n\}(1 - |\Sigma|\delta)^2} + \frac{\sqrt{n} \log n}{s} + \frac{(s_0 + s_1) \log n}{s^2} + h \log n \right), \quad (19)$$

for a sufficiently large constant $c_1$. Recall that we assume the noise matrix $N$ to be $\delta$-uniform. This assumption will be relaxed in Section 5.3.3 when proving Theorem 4, by using the results of Section 4.

### 5.3.1 Correctness of weak-opinions in Algorithm SF

**Lemma 28.** The weak-opinion of each agent $i$, computed after Phase 1 in Algorithm SF, satisfies

$$\mathbb{P}(\tilde{Y}^{(i)} = 1) \ge \frac{1}{2} + 4\sqrt{\frac{\log n}{n}}.$$

Moreover, all $\{\tilde{Y}^{(i)}\}_{i \in I}$ are mutually independent.

*Proof.* Let $i \in I$. Recall that it each of the first two phases of Algorithm SF, Agent $i$ receives at least $m$ messages. Let $A^{(i)}, B^{(i)} \in \{0, 1\}^m$ be a random vector containing the first $m$ messages received in Phase 0 and Phase 1, respectively. By construction, Agent $i$ observes a 0 in Phase 0 if and only if it received a corrupted message from a 1-source, or an uncorrupted message from either a 0-source or a non-source agent. By applying a similar reasoning to Phase 1, we compute for every $k \in \{1, \dots, m\}$,

$$\begin{aligned}
\mathbb{P}(A_k^{(i)} = 0) &= \frac{s_1}{n}\delta + \left(1 - \frac{s_1}{n}\right)(1 - \delta) & \mathbb{P}(B_k^{(i)} = 0) &= \frac{s_0}{n}(1 - \delta) + \left(1 - \frac{s_0}{n}\right)\delta \\
\mathbb{P}(A_k^{(i)} = 1) &= \frac{s_1}{n}(1 - \delta) + \left(1 - \frac{s_1}{n}\right)\delta & \mathbb{P}(B_k^{(i)} = 1) &= \frac{s_0}{n}\delta + \left(1 - \frac{s_0}{n}\right)(1 - \delta).
\end{aligned}$$

Let us define the random variables $\{X_k^{(i)}\}_{k \in \{1, \dots, m\}}$ s.t.

$$X_k^{(i)} = \begin{cases} 1 & \text{if } (A_k^{(i)}, B_k^{(i)}) = (1, 1) \\ 0 & \text{if } (A_k^{(i)}, B_k^{(i)}) = (0, 1), \text{ or } (A_k^{(i)}, B_k^{(i)}) = (1, 0) \\ -1 & \text{if } (A_k^{(i)}, B_k^{(i)}) = (0, 0). \end{cases}$$

Let $X^{(i)} := \sum_{k=1}^m X_k^{(i)}$. Informally, each $X_k^{(i)}$ is assigned value +1 or -1 if the corresponding pair of messages tends to indicate that the correct opinion is respectively 1 or 0, and it is assigned value 0 otherwise. Recall that $C_t^{(i)}$ denotes the value of the coin toss performed by Agent $i$ in round $t$. By definition of Algorithm SF, we have

$$\tilde{Y}^{(i)} = 1 \iff \begin{cases} X^{(i)} > 0, & \text{or} \\ X^{(i)} = 0 \text{ and } C_t^{(i)} = 1. \end{cases} \quad (20)$$
Note that the value of the messages received in Phases 0 and 1 only depends on the identity of the sampled agents, and on the realization of the noise. As a consequence, each $A_k^{(i)}$ and each $B_k^{(i)}$ is a deterministic function of a corresponding pair $(N_{t,\ell}^{(i)}, S_{t,\ell}^{(i)})$, and so is each $X_k^{(i)}$. Therefore, since the variables $\{S_t^{(i)}, N_t^{(i)}, C_t^{(i)}\}_{i \in I, t \in \mathbb{N}}$ are mutually independent, it follows that all $\{\tilde{Y}^{(i)}\}_{i \in I}$ are also mutually independent. Moreover, we can write

$$ 
\begin{aligned}
\mathbb{P}(X_k^{(i)} = 1) &= \mathbb{P}(A_k^{(i)} = 1) \cdot \mathbb{P}(B_k^{(i)} = 1), \\
\mathbb{P}(X_k^{(i)} = 0) &= \mathbb{P}(A_k^{(i)} = 0) \cdot \mathbb{P}(B_k^{(i)} = 1) + \mathbb{P}(A_k^{(i)} = 1) \cdot \mathbb{P}(B_k^{(i)} = 0), \\
\mathbb{P}(X_k^{(i)} = -1) &= \mathbb{P}(A_k^{(i)} = 0) \cdot \mathbb{P}(B_k^{(i)} = 0).
\end{aligned}
$$

In order to apply Lemma 23 to $X^{(i)}$, we first verify that all its conditions are satisfied.

**Claim 29.** We have

$$ \mathbb{P}(X_k^{(i)} \neq 0) \geq (1-2\delta)^2 \cdot \frac{s_0 + s_1}{2n} + \delta \quad (21) $$

Moreover, if $\delta \geq \frac{s_0+s_1}{2n}(1-2\delta)$,

$$ \mathbb{P}(X_k^{(i)} = 1 | X_k^{(i)} \neq 0) \geq \frac{1}{2} + \frac{s(1-2\delta)}{n} \quad (22) $$

while if $\delta < \frac{s_0+s_1}{2n}(1-2\delta)$,

$$ \mathbb{P}(X_k^{(i)} = 1 | X_k^{(i)} \neq 0) \geq \frac{1}{2} + \frac{s}{4(s_0 + s_1)} \quad (23) $$

**Proof of Claim 29.** We first prove Eq. (21).

$$ 
\begin{aligned}
\mathbb{P}(X_k^{(i)} \neq 0) &= \mathbb{P}(A_k^{(i)} = 1) \cdot \mathbb{P}(B_k^{(i)} = 1) + \mathbb{P}(A_k^{(i)} = 0) \cdot \mathbb{P}(B_k^{(i)} = 0) \\
&= \left(\frac{s_1}{n}(1-\delta) + \left(1-\frac{s_1}{n}\right)\delta\right) \cdot \left(\frac{s_0}{n}\delta + \left(1-\frac{s_0}{n}\right)(1-\delta)\right) \\
&\quad + \left(\frac{s_1}{n}\delta + \left(1-\frac{s_1}{n}\right)(1-\delta)\right) \cdot \left(\frac{s_0}{n}(1-\delta) + \left(1-\frac{s_0}{n}\right)\delta\right) \\
&= \frac{s_0+s_1}{n} - 2\frac{s_0s_1}{n^2} + 2\delta \left[1 - 2\frac{s_0+s_1}{n} + 4\frac{s_0s_1}{n^2}\right] + 2\delta^2 \left[-1 + 2\frac{s_0+s_1}{n} - 4\frac{s_0s_1}{n^2}\right] \\
&= 2\delta(1-\delta) + (1-2\delta)^2 \left(\frac{s_0+s_1}{n} - 2\frac{s_0s_1}{n^2}\right).
\end{aligned}
\quad (24) $$

Since $2\delta(1 - \delta) \geq \delta$ whenever $\delta \in [0, 1/2]$, we obtain

$$ \mathbb{P}(X_k^{(i)} \neq 0) \geq \delta + (1-2\delta)^2 \frac{s_0 + s_1}{2n}, $$

where we also used the fact that $s_0, s_1 \leq \frac{n}{4}$ (Eq. (18)) and therefore $\frac{s_0s_1}{n^2} \leq \frac{s_0+s_1}{4n}$. This establishes Eq. (21). From Eq. (24), since $1 - 2\delta \leq 1 - \delta \leq 1$, we have

$$ \mathbb{P}(X_k^{(i)} \neq 0) \leq 2\delta + (1-2\delta) \frac{s_0 + s_1}{n}. \quad (25) $$

Moreover,

$$ 
\begin{aligned}
\mathbb{P}(X_k^{(i)} = 1) - \mathbb{P}(X_k^{(i)} = -1) &= \mathbb{P}(A_k^{(i)} = 1) \cdot \mathbb{P}(B_k^{(i)} = 1) - \mathbb{P}(A_k^{(i)} = 0) \cdot \mathbb{P}(B_k^{(i)} = 0) \\
&= \left(\frac{s_1}{n}(1-\delta) + \left(1-\frac{s_1}{n}\right)\delta\right) \cdot \left(\frac{s_0}{n}\delta + \left(1-\frac{s_0}{n}\right)(1-\delta)\right) \\
&\quad - \left(\frac{s_1}{n}\delta + \left(1-\frac{s_1}{n}\right)(1-\delta)\right) \cdot \left(\frac{s_0}{n}(1-\delta) + \left(1-\frac{s_0}{n}\right)\delta\right) \\
&= (1-2\delta) \frac{s_1 - s_0}{n} = (1-2\delta) \frac{s}{n}.
\end{aligned}
\quad (26) $$
We have

$$ \mathbb{P}(X_k^{(i)} = 1 | X_k^{(i)} \neq 0) - \mathbb{P}(X_k^{(i)} = -1 | X_k^{(i)} \neq 0) = \frac{\mathbb{P}(X_k^{(i)} = 1) - \mathbb{P}(X_k^{(i)} = -1)}{\mathbb{P}(X_k^{(i)} \neq 0)}, $$

therefore, if $\delta \ge \frac{s_0+s_1}{2n}(1-2\delta)$, by Eqs. (25) and (26), we obtain

$$ \mathbb{P}(X_k^{(i)} = 1 | X_k^{(i)} \neq 0) - \mathbb{P}(X_k^{(i)} = -1 | X_k^{(i)} \neq 0) \geq \frac{(1-2\delta)\frac{s}{n}}{2\delta + (1-2\delta)\frac{s_0+s_1}{n}} \geq \frac{(1-2\delta)\frac{s}{n}}{4\delta}. $$

Instead, if $\delta < \frac{s_0+s_1}{2n}(1-2\delta)$, we have

$$ \mathbb{P}(X_k^{(i)} = 1 | X_k^{(i)} \neq 0) - \mathbb{P}(X_k^{(i)} = -1 | X_k^{(i)} \neq 0) \geq \frac{(1-2\delta)\frac{s}{n}}{2\delta + (1-2\delta)\frac{s_0+s_1}{n}} \geq \frac{(1-2\delta)\frac{s}{n}}{2(1-2\delta)\frac{s_0+s_1}{n}} = \frac{s}{2(s_0+s_1)}. $$

We have proven that, depending on the value of $\delta$, for $x = \frac{s}{n}\frac{(1-2\delta)}{4\delta}$ or $x = \frac{s}{2(s_0+s_1)}$, we have

$$ \mathbb{P}(X_k^{(i)} = 1 | X_k^{(i)} \neq 0) - \mathbb{P}(X_k^{(i)} = -1 | X_k^{(i)} \neq 0) \geq x. $$

Since $\mathbb{P}(X_k^{(i)} = -1 | X_k^{(i)} \neq 0) = 1 - \mathbb{P}(X_k^{(i)} = 1 | X_k^{(i)} \neq 0)$, we obtain

$$ 2\mathbb{P}(X_k^{(i)} = 1 | X_k^{(i)} \neq 0) - 1 \geq x. $$

Eqs. (22) and (23) follow from rearranging the inequality, which concludes the proof of Claim 29. $\square$

Finally, we have

$$ \begin{aligned} \mathbb{P}(\tilde{Y}^{(i)} = 1) &= \mathbb{P}(X^{(i)} > 0) + \frac{1}{2}\mathbb{P}(X^{(i)} = 0) && (\text{by Eq. (20)}) \\ &= \mathbb{P}(X^{(i)} > 0) + \frac{1}{2}(1 - \mathbb{P}(X^{(i)} > 0) - \mathbb{P}(X^{(i)} < 0)) \\ &= \frac{1}{2} + \frac{\mathbb{P}(X^{(i)} > 0) - \mathbb{P}(X^{(i)} < 0)}{2}. \end{aligned} $$

Eq. (19) and Claim 29 together imply that we can apply Lemma 23, in order to obtain

$$ \mathbb{P}(\tilde{Y}^{(i)} = 1) \geq \frac{1}{2} + 4\sqrt{\frac{\log n}{n}}, $$

which concludes the proof of Lemma 28. $\square$

### 5.3.2 Correctness of the majority boosting phase in Algorithm SF

Let $L := 10 \log n$ be the number of sub-phases lasting for $\lceil w/h \rceil$ rounds, within the Majority Boosting phase (Phase 2) of Algorithm SF. For $\ell \in \{0, \dots, L\}$, we write:

$$ \Delta_{\ell} := \left| \left\{ i \in I, Y_t^{(i)} = 1, \text{ where } t \text{ is the } \ell^{\text{th}} \text{ update round} \right\} \right| - \frac{n}{2}. $$

Informally, $\Delta_{\ell}$ denotes the number of agents holding the correct opinion “beyond half of the population”, during the $\ell^{th}$ sub-phase.

**Claim 30.** We have that

$$ m \geq c_1 \frac{7}{16} \cdot \frac{\log n}{(1 - 2\delta)^2}. $$
*Proof.* The minimum value attained by the function $x \to x+(1-2x)^2$ on the interval $[0, 1/2]$ is equal to 7/16. By Eq. (19),

$$m \ge c_1 \left( \frac{\delta \log n}{(1-2\delta)^2} + \log n \right) = c_1 \frac{(\delta + (1-2\delta)^2) \log n}{(1-2\delta)^2} \ge c_1 \frac{7}{16} \cdot \frac{\log n}{(1-2\delta)^2}.$$

□

**Lemma 31.** *The Majority Boosting phase lasts at most $2\lceil m/h \rceil$ rounds.*

*Proof.* By the definition of Algorithm SF, the Majority Boosting phase is made up of $L$ short sub-phases which last for $\lceil w/h \rceil$ rounds each, where $w := 100/(1-2\delta)^2$, and a longer sub-phase which lasts for $\lceil m/h \rceil$ rounds. To prove the statement, we therefore need to verify that $L \cdot \lceil w/h \rceil \le \lceil m/h \rceil$.

If $h \ge w$, then $L \cdot \lceil w/h \rceil = L = 10 \log n$, which is less than $m/h$ by Eq. (19). Now, consider the case that $h < w$. Then,

$$\lceil \frac{w}{h} \rceil < \frac{w}{h} + 1 < \frac{2w}{h}. \qquad (27)$$

Moreover,

$$m \ge c_1 \frac{7}{16} \cdot \frac{\log n}{(1-2\delta)^2} \qquad (\text{by Claim 30})$$

$$\Rightarrow m \ge \frac{2000}{(1-2\delta)^2} \log n \qquad (\text{as long as } c_1 \ge \frac{16}{7} \cdot 2000)$$

$$\Rightarrow \frac{m}{h} \ge \frac{2w}{h} \cdot 10 \log n.$$

By Eq. (27), this implies that $\lceil m/h \rceil \ge \lceil w/h \rceil \cdot 10 \log n$, which concludes the proof of Lemma 31.

□

**Lemma 32.** *We have that*

$$\mathbb{P} \left( \Delta_0 \ge 2 \sqrt{n \log n} \right) \ge 1 - \frac{1}{n^8}$$

*Proof.* Recall that the opinion of each agent before the first update round is equal to its weak-opinion. Therefore, by Lemma 28, $\mathbb{E}(\Delta_0) = 4\sqrt{n \log n}$. The result follows from applying the Chernoff-Hoeffding's bound.

□

**Lemma 33.** *There exists a constant $c_2 > 2$ s.t.*

$$\mathbb{P} \left( \Delta_{\ell+1} \ge \min \left( 1.2 \Delta_{\ell}, \frac{n}{\sqrt{8\pi e}} \right) \mid \Delta_{\ell} \ge 2\sqrt{n \log n} \right) \ge 1 - \frac{1}{n^8}.$$

*Proof.* Let $M$ be the multi-set of all messages received by Agent $i$ between the $\ell^{th}$ and $(\ell+1)^{th}$ update rounds, and let $t$ be the round number of the latter. By construction of Algorithm SF, $|M| \ge \frac{100}{(1-2\delta)^2}$. Moreover, the opinion of Agent $i$ in round $t$, $Y_t^{(i)}$, corresponds to the majority opinion in $M$. Formally, let $X_k = +1$ (resp. $-1$) if the $k^{th}$ message in $M$ is 1 (resp. 0), and let $X = \sum_k X_k$. Recall that $C_t^{(i)}$ denotes the coin toss performed by Agent $i$ to break ties in round $t$. We have that

$$Y_t^{(i)} = 1 \iff \begin{cases} X > 0, & \text{or} \\ X = 0 \text{ and } C_t^{(i)} = 1. \end{cases} \qquad (28)$$

Conditioning on $\Delta_{\ell} = x$, all $\{X_k\}$ are mutually independent and identically distributed. Specifically, they follow a Rademacher distribution with parameter $p$, where

$$p := \left(\frac{1}{2} + \frac{x}{n}\right) (1 - \delta) + \left(\frac{1}{2} - \frac{x}{n}\right) \delta = \frac{1}{2} + (1 - 2\delta) \cdot \frac{x}{n}.$$
Thus, by Lemma 22,

$$
\begin{align*}
\mathbb{P}(X > 0 | \Delta_{\ell} = x) - \mathbb{P}(X < 0 | \Delta_{\ell} = x) &\ge \sqrt{\frac{2}{\pi e}} \cdot \min\{\sqrt{|M|}(1 - 2\delta) \cdot \frac{x}{n}, 1\} \\
&\ge \sqrt{\frac{2}{\pi e}} \cdot \min\{10 \cdot \frac{x}{n}, 1\}. \quad \text{(since } |M| \ge \frac{100}{(1-2\delta)^2}\text{)}
\end{align*}
$$

Using the fact that $\mathbb{P}(X = 0) = 1 - \mathbb{P}(X > 0) - \mathbb{P}(X < 0)$, we obtain

$$
\begin{align*}
\mathbb{P} (Y_t^{(i)} = 1 | \Delta_t = x) &= \mathbb{P} (X > 0 | \Delta_t = x) + \frac{1}{2} \cdot \mathbb{P} (X = 0 | \Delta_t = x) \quad \text{(by Eq. (28))} \\
&= \frac{1}{2} + \frac{\mathbb{P} (X > 0 | \Delta_t = x) - \mathbb{P} (X < 0 | \Delta_t = x)}{2} \\
&\ge \frac{1}{2} + \sqrt{\frac{1}{2\pi e}} \cdot \min\{10 \cdot \frac{x}{n}, 1\} := \frac{1}{2} + A.
\end{align*}
$$

Therefore, the expected number of agents with opinion 1 in round $t$ is greater than $n/2 + An$, and by the Chernoff-Hoeffding's bound,

$$
\begin{align*}
\mathbb{P} \left( \Delta_{\ell+1} \le \frac{1}{\sqrt{8\pi e}} \cdot \min\{10x, n\} \mid \Delta_{\ell} = x \right) &= \mathbb{P} \left( \Delta_{\ell+1} \le \frac{An}{2} \mid \Delta_{\ell} = x \right) \\
&\le \exp \left( -2 \cdot \frac{A^2 n}{4} \right) \\
&= \exp \left( -\frac{1}{4\pi e} \cdot \min\{100 \frac{x^2}{n}, n\} \right) \\
&\le \exp \left( -\frac{1}{4\pi e} \cdot \min\{400 \log n, n\} \right) \quad \text{(since } x \ge 2\sqrt{n \log n} \text{)} \\
&= \exp \left( -\frac{400}{4\pi e} \cdot \log n \right).
\end{align*}
$$

This concludes the proof of Lemma 33 by noting that $\frac{10}{\sqrt{8\pi e}} > 1.2$, and $\frac{400}{4\pi e} > 8$. $\square$

**Lemma 34.** We have that

$$
\mathbb{P} \left( \Delta_L \ge \frac{n}{\sqrt{8\pi e}} \right) \ge 1 - \frac{1}{n^7}.
$$

*Proof.* Let $\mathcal{E}_\ell$ the event

$$
\mathcal{E}_{\ell} = \left\{ \Delta_{\ell+1} \geq \min \left( 1.2 \Delta_{\ell}, \frac{n}{\sqrt{8\pi e}} \right) \right\}.
$$

We have

$$
\begin{align*}
\mathbb{P} \left( \bigcap_{\ell=0}^{L-1} \mathcal{E}_\ell \mid \Delta_0 \ge 2\sqrt{n \log n} \right) &\ge \prod_{\ell=0}^{L-1} \left(1 - \frac{1}{n^8}\right) \tag{by Lemma 33} \\
&\ge 1 - L \cdot \frac{1}{n^8} \tag{union bound} \\
&= 1 - 10 \log n \cdot \frac{1}{n^8} \\
&\ge 1 - \frac{1}{n^7}. \tag{for $n$ large enough}
\end{align*}
$$

By Lemma 32, $\Delta_0 \ge 2\sqrt{n \log n}$ w.p. $1 - \frac{1}{n^8}$, and so $\cap_{\ell=0}^{L-1} \mathcal{E}_\ell$ happens w.p. $1 - \frac{1}{n^7}$. This implies that

$$
\Delta_L \ge \min\{2 \cdot 1.2^L \sqrt{n \log n}, \frac{n}{\sqrt{8\pi e}}\}.
$$

Since $1.2^L = 1.2^{10 \log n} = n^{\log 12} > n$, we have $\Delta_L \ge \frac{n}{\sqrt{8\pi e}}$, which concludes the proof of Lemma 34. $\square$
**Lemma 35.** At the end of the Majority Boosting phase, all agents have the correct opinion w.h.p.

*Proof.* Let $T$ be the last round of the execution of Algorithm SF, which follows the last sub-phase of length $[m/h]$. Let $i \in I$, and let $M$ be the memory of Agent $i$ in this round, which contains $m$ messages. Let $X_k$ be the $k$-th message stored in $M$, and $X = \sum_k X_k$. Conditioning on $\Delta_L \ge \frac{n}{\sqrt{8\pi e}}$, each message is equal to 1 with probability at least $1/2 + \frac{1}{\sqrt{8\pi e}}(1-2\delta)$. Therefore, for every agent $i$, the expectation of the number of messages equal to 1 is equal to

$$ \mu := \mathbb{E}(X) = m \cdot \left( \frac{1}{2} + \frac{1-2\delta}{\sqrt{8\pi e}} \right). $$

Note that

$$ m \cdot \frac{(1-2\delta)^2}{8\pi e} \stackrel{\text{Claim 30}}{\ge} c_1 \frac{7}{16} \cdot \frac{\log n}{(1-2\delta)^2} \cdot \frac{(1-2\delta)^2}{8\pi e} = c_1 \cdot \frac{7}{16} \cdot \frac{\log n}{8\pi e}. \quad (29) $$

Moreover,

$$ \begin{aligned} \mathbb{P} \left( X \le \frac{m}{2} \mid \Delta_L \ge \frac{n}{\sqrt{8\pi e}} \right) &= \mathbb{P} \left( X \le \mu + \frac{m}{2} - \mu \mid \Delta_L \ge \frac{n}{\sqrt{8\pi e}} \right) \\ &\le \mathbb{P} \left( X \le \mu - m \frac{1-2\delta}{\sqrt{8\pi e}} \mid \Delta_L \ge \frac{n}{\sqrt{8\pi e}} \right) \\ &\le \exp \left( -2m \left( \frac{1-2\delta}{\sqrt{8\pi e}} \right)^2 \right) \quad \text{(by Chernoff-Hoeffding's bound)} \\ &\le \exp \left( c_1 \cdot \frac{7}{8} \cdot \frac{\log n}{8\pi e} \right) \quad \text{(by Eq. (29))} \\ &\le \frac{1}{n^3}, \end{aligned} $$

where we used that $c_1$ is big enough. We obtain

$$ \begin{aligned} \mathbb{P} \left( X > \frac{m}{2} \right) &\ge \mathbb{P} \left( \Delta_L \ge \frac{n}{\sqrt{8\pi e}} \right) \cdot \mathbb{P} \left( X \le \frac{m}{2} \mid \Delta_L \ge \frac{n}{\sqrt{8\pi e}} \right) \\ &\ge \left( 1 - \frac{1}{n^7} \right) \cdot \left( 1 - \frac{1}{n^3} \right) \ge 1 - \frac{1}{n^3}. \quad \text{(by Lemma 34)} \end{aligned} $$

Since $\{X > m/2\} \implies Y_T^{(i)} = 1$, this implies that $\mathbb{P}(Y_T^{(i)} = 1) \ge 1 - \frac{1}{n^3}$, i.e., the opinion of Agent $i$ is correct w.h.p. We conclude the proof of Lemma 35 by a union bound over all agents. $\square$

### 5.3.3 Proof of Theorem 4

Let $N$ be an arbitrary $\delta$-upper bounded noise matrix of size $d=2$, and let

$$ m \ge c_1 \left( 6 \cdot \frac{n\delta \log n}{\min\{s^2, n\}(1 - |\Sigma|\delta)^2} + \frac{\sqrt{n} \log n}{s} + \frac{(s_0 + s_1) \log n}{s^2} + h \log n \right), $$

where $c_1$ is the constant from Eq. (19). By Theorem 8, there exists a matrix $P$ s.t. the simulation of Algorithm SF with artificial noise $P$ under $N$ is equivalent to Algorithm SF under a $\delta'$-uniform noise, where

$$ \delta' = \left( 2 + \frac{1}{2} \cdot \frac{(1-2\delta)}{\delta} \right)^{-1}. $$

Writing $A = \delta'^{-1}$, we have

$$ \frac{(1-2\delta')^2}{\delta'} = A \cdot \left(1 - \frac{2}{A}\right)^2 = \frac{(A-2)^2}{A} = \frac{\left[\frac{1}{2} - \frac{1-2\delta}{\delta}\right]^2}{2 + \frac{1}{2} \frac{1-2\delta}{\delta}} = \frac{1}{4\delta} \cdot \frac{(1-2\delta)^2}{2\delta + \frac{1}{2}(1-2\delta)} \ge \frac{1}{6} \cdot \frac{(1-2\delta)^2}{\delta}, $$
where in the last inequality we have used the fact that $\delta \in [0, 1/2)$ and so $2\delta + \frac{1}{2}(1 - 2\delta) \le 1$. Hence,

$$ \frac{n\delta' \log n}{s^2(1 - 2\delta')^2} \le 6 \cdot \frac{n\delta \log n}{s^2(1 - 2\delta)^2}. $$

Therefore, $m$ satisfies Eq. (19) with $\delta'$, and Theorem 4 follows from our analysis under uniform noise (see Lemma 35).

## 5.4 Analysis of Algorithm SSF

In this section, we prove Theorem 5. Accordingly, we assume that the parameter $m$ used by the protocol satisfies the following condition:

$$ m \ge c_1 \cdot \left( \frac{\delta n \log n}{(1 - 4\delta)^2} + n \right), \qquad (30) $$

for a large enough constant $c_1$. Recall that we assume the noise matrix $N$ to be $\delta$-uniform. This assumption will be relaxed later in Section 5.4.3 when concluding the proof of Theorem 5, by using the results of Section 4.

Agents and rounds are indexed solely for analysis purposes; agents themselves do not require identifiers or knowledge of the current time. In addition to the notations already introduced in Section 5.2, we will write $\mathcal{R}_{t_1:t_2}^{(i)}$ to denote all the randomness (noise, samples, and coin tosses) linked to Agent $i$, between rounds $t_1$ and $t_2$. Formally,

$$ \mathcal{R}_{t_1:t_2}^{(i)} := \{ (N_t^{(i)}, S_t^{(i)}, C_t^{(i)}), \text{ for every } t \in \{t_1+1, \dots, t_2\} \}. $$

### 5.4.1 Correctness of weak-opinions in Algorithm SSF

In this section, we prove that at any time in the execution after at least $2\lceil m/h \rceil$ rounds, the weak-opinion of any non-source agent is correct with a probability slightly larger than $1/2$. Moreover, we show that all weak-opinions are mutually independent.

**Lemma 36.** For every $t \ge 2\lceil m/h \rceil$ and $i \in I$,

(i) $\tilde{Y}_t^{(i)}$ is a deterministic function of $\mathcal{R}_{t_1:t_2}^{(i)}$, where $t_2 \le t$ is the last update round of Agent $i$ up to round $t$, and $t_1 = t_2 - \lceil m/h \rceil$. As a consequence, all $\{\tilde{Y}_t^{(i)}\}_{i \in I}$ are mutually independent.

(ii) We have

$$ \mathbb{P}(\tilde{Y}_t^{(i)} = 1) \ge \frac{1}{2} + 4\sqrt{\frac{\log n}{n}}. $$

*Proof.* We prove each statement in Lemma 36 separately.

**Proof of (i).** Fix a round $T \ge 2\lceil m/h \rceil$, let $t_2$ be the last update round of Agent $i$ before round $T$, and let $t_1 = t_2 - \lceil m/h \rceil$. Since there are $\lceil m/h \rceil$ rounds between two consecutive updates, $t_2 \ge T - \lceil m/h \rceil$, and hence $t_1 \ge 0$. Moreover, the fact that the memory of Agent $i$ has been emptied in round $t_1$ implies that in round $t_2$ (when $\tilde{Y}_T^{(i)}$ is computed), it does not contain any adversarially generated messages. Consider the multi-set $\{\sigma_k^{(i)}, k \in \{1, \dots, m\}\}$ of all $m$ messages received by Agent $i$ between round $t_1$ and $t_2$. Define

$$ X_k^{(i)} := \begin{cases} 1 & \text{if } \sigma_k^{(i)} = (1, 1), \\ -1 & \text{if } \sigma_k^{(i)} = (1, 0), \\ 0 & \text{otherwise.} \end{cases} $$

Recall that formally, each $N_{t,\ell}^{(i)}$ is a random function from $\Sigma$ to $\Sigma$, with the convention that the $\ell^{th}$ message sampled by Agent $i$ in round $t$ is modified by noise according to $\sigma \to N_{t,\ell}^{(i)}(\sigma)$. We can assume, without loss
of generality, that $N_{t,\ell}^{(i)}$ is distributed explicitly as follows:

$$ N_{t,\ell}^{(i)} := \left\{ \begin{array}{ll} \begin{bmatrix} (0,0) & \to & (0,0) \\ (0,1) & \to & (0,1) \\ (1,1) & \to & (1,1) \\ (1,0) & \to & (1,0) \end{bmatrix} & \text{(uncorrupted message)} \quad \text{w.p. } 1 - 3\delta, \\ \begin{bmatrix} (0,0) & \to & (0,1) \\ (0,1) & \to & (0,0) \\ (1,1) & \to & (0,0) \\ (1,0) & \to & (0,0) \end{bmatrix} & \text{or} \\ \begin{bmatrix} (0,0) & \to & (1,0) \\ (0,1) & \to & (1,0) \\ (1,1) & \to & (0,1) \\ (1,0) & \to & (0,1) \end{bmatrix} & \text{or} \\ \begin{bmatrix} (0,0) & \to & (1,1) \\ (0,1) & \to & (1,1) \\ (1,1) & \to & (1,0) \\ (1,0) & \to & (1,1) \end{bmatrix} & \text{w.p. } \delta. \end{array} \right. \tag{31} $$

Indeed, with this definition, one can check that the noise is $\delta$-uniform: for every $\sigma, \sigma' \in \Sigma$, we have

$$ \mathbb{P}(N_{t,\ell}^{(i)}(\sigma) = \sigma') = \begin{cases} (1-3\delta) & \text{if } \sigma = \sigma', \\ \delta & \text{otherwise.} \end{cases} $$

It is clear from Eq. (31) that whenever the original message has a first bit equal to 0, and this bit is flipped to 1 under the effect of noise, then the second bit of the modified message is independent of the second bit of the original message. Consequently, each $k \in \{1, \dots, m\}$ corresponds to a different pair $(t, \ell) \in \{t_1 + 1, \dots, t_2\} \times \{1, \dots, h\}$, such that $X_k^{(i)}$ is a deterministic function of $S_{t,\ell}^{(i)}$ and $N_{t,\ell}^{(i)}$. Specifically, $S_{t,\ell}^{(i)}$ determines whether the sampled agent is a source or not, while $N_{t,\ell}^{(i)}$ determines how the message is affected by noise, and no other information is needed to compute the value of $X_k^{(i)}$. Note that this argument relies heavily on the fact that the noise matrix $N$ is $\delta$-uniform. Now, let

$$ X^{(i)} = \sum_{k=1}^{m} X_{k}^{(i)}. $$

Informally, $X^{(i)}$ measures the bias towards the correct opinion, corresponding to the messages observed by Agent $i$. Recall that $C_{t_2}^{(i)}$ represents the coin used by Agent $i$ in round $t_2$ to break ties when computing $\tilde{Y}_T^{(i)}$. By definition of Algorithm SSF,

$$ \tilde{Y}_T^{(i)} = 1 \iff \begin{cases} X^{(i)} > 0, & \text{or} \\ X^{(i)} = 0 \text{ and } C_{t_2}^{(i)} = 1. \end{cases} \tag{32} $$

Together with the reasoning above, this implies that $\tilde{Y}_T^{(i)}$ is a deterministic function of $\mathcal{R}_{t_1:t_2}^{(i)}$. Since all $\{\mathcal{R}_{t_1:t_2}^{(i)}\}_{i \in I}$ are mutually independent, it follows that all $\{\tilde{Y}_T^{(i)}\}_{i \in I}$ are also mutually independent, which establishes Lemma 36.(i).

**Proof of (ii).** There are two ways in which $X_k^{(i)}$ can be equal to 1 (resp. -1): either Agent $i$ samples a source with opinion 1 (resp. 0) and the noise does not modify the message, or they sample any other agent and the noise changes the message into (1, 1) (resp. (1, 0)). Therefore,

$$ \begin{align} \mathbb{P}(X_k^{(i)} = 1) &= \frac{s_1}{n}(1 - 3\delta) + \left(1 - \frac{s_1}{n}\right)\delta, \quad \text{and} \tag{33} \\ \mathbb{P}(X_k^{(i)} = -1) &= \frac{s_0}{n}(1 - 3\delta) + \left(1 - \frac{s_0}{n}\right)\delta. \notag \end{align} $$

**Claim 37.** For every $k \in \{1, \dots, m\}$, we have

$$ \mathbb{P}(X_k^{(i)} \neq 0) \geq (1 - 4\delta)^2 \cdot \frac{s_0 + s_1}{2n} + \delta \tag{34} $$

Moreover, if $\delta \geq \frac{s_0+s_1}{2n}(1-4\delta)$,

$$ \mathbb{P}(X_k^{(i)} = 1 | X_k^{(i)} \neq 0) \geq \frac{1}{2} + \frac{s(1-4\delta)}{n(8\delta)}, \tag{35} $$
while if $\delta < \frac{s_0+s_1}{2n}(1-4\delta)$,

$$ \mathbb{P}(X_k^{(i)} = 1 | X_k^{(i)} \neq 0) \geq \frac{1}{2} + \frac{s}{4(s_0 + s_1)}. \qquad (36) $$

*Proof of Claim 37.* By Eq. (33), we have

$$ \begin{aligned} \mathbb{P}(X_k^{(i)} \neq 0) &= \frac{s_1}{n}(1-3\delta) + \left(1 - \frac{s_1}{n}\right)\delta + \frac{s_0}{n}(1-3\delta) + \left(1 - \frac{s_0}{n}\right)\delta \\ &= 2\delta + (1-4\delta)\left(\frac{s_0+s_1}{n}\right) \end{aligned} \qquad (37) $$

Eq. (34) follows from Eq. (37) and the fact that $0 < 1 - 4\delta \leq 1$. Moreover, we have

$$ \begin{aligned} \mathbb{P}(X_k^{(i)} = 1) - \mathbb{P}(X_k^{(i)} = -1) &= \frac{s_1}{n}(1-3\delta) + \left(1 - \frac{s_1}{n}\right)\delta - \frac{s_0}{n}(1-3\delta) - \left(1 - \frac{s_0}{n}\right)\delta \\ &= \frac{s_1 - s_0}{n}(1-4\delta). \end{aligned} \qquad (38) $$

Then, if $\delta \geq \frac{s_0+s_1}{2n}(1-4\delta)$, we have

$$ \begin{aligned} & \mathbb{P}(X_k^{(i)} = 1 | X_k^{(i)} \neq 0) - \mathbb{P}(X_k^{(i)} = -1 | X_k^{(i)} \neq 0) \\ &= \frac{\mathbb{P}(X_k^{(i)} = 1) - \mathbb{P}(X_k^{(i)} = -1)}{\mathbb{P}(X_k^{(i)} \neq 0)} \\ &= \frac{\frac{s_1-s_0}{n}(1-4\delta)}{2\delta + (1-4\delta)\left(\frac{s_0+s_1}{n}\right)} \qquad \text{(by Eqs. (37) and (38))} \\ & \geq \frac{\frac{s_1-s_0}{n}(1-4\delta)}{4\delta} = \frac{s}{n} \cdot \frac{1-4\delta}{4\delta}. \end{aligned} $$

Instead, if $\delta < \frac{s_0+s_1}{2n}(1-4\delta)$, we have

$$ \begin{aligned} & \mathbb{P}(X_k^{(i)} = 1 | X_k^{(i)} \neq 0) - \mathbb{P}(X_k^{(i)} = -1 | X_k^{(i)} \neq 0) \\ &= \frac{\frac{s_1-s_0}{n}(1-4\delta)}{2\delta + (1-4\delta)\left(\frac{s_0+s_1}{n}\right)} \\ & \geq \frac{s_1 - s_0}{2(s_0 + s_1)} = \frac{s}{2(s_0 + s_1)}. \end{aligned} $$

In both cases, since $\mathbb{P}(X_k^{(i)} = -1 | X_k^{(i)} \neq 0) = 1 - \mathbb{P}(X_k^{(i)} = 1 | X_k^{(i)} \neq 0)$,

$$ \begin{aligned} \mathbb{P}(X_k^{(i)} = 1 | X_k^{(i)} \neq 0) - \mathbb{P}(X_k^{(i)} = -1 | X_k^{(i)} \neq 0) &\geq A \implies 2\mathbb{P}(X_k^{(i)} = 1 | X_k^{(i)} \neq 0) - 1 \geq A \\ &\implies \mathbb{P}(X_k^{(i)} = 1 | X_k^{(i)} \neq 0) \geq \frac{1}{2} + \frac{A}{2}, \end{aligned} $$

and Eqs. (35) and (36) follow when replacing $A$ by $\frac{s}{n} \cdot \frac{1-4\delta}{4\delta}$ and $\frac{s}{2(s_0+s_1)}$, respectively. $\square$

Because of our assumption in Eq. (30), and since $s \geq 1$, $m$ satisfies Eq. (9). Together with Claim 37, this allows us to use Lemma 23. More precisely, we have

$$ \begin{aligned} \mathbb{P}(\tilde{Y}_T^{(i)} = 1) &= \mathbb{P}(X^{(i)} > 0) + \frac{1}{2} \cdot \mathbb{P}(X^{(i)} = 0) \qquad \text{(by Eq. (32))} \\ &= \frac{1}{2} + \frac{\mathbb{P}(X^{(i)} > 0) - \mathbb{P}(X^{(i)} < 0)}{2} \quad \text{(since } \mathbb{P}(X^{(i)} = 0) = 1 - \mathbb{P}(X^{(i)} > 0) - \mathbb{P}(X^{(i)} < 0)) \\ &\geq \frac{1}{2} + 4\sqrt{\frac{\log n}{n}}, \quad \text{(by Claim 37, Eq. (30) and Lemma 23)} \end{aligned} $$

which concludes the proof of Lemma 36. $\square$
### 5.4.2 Correctness of opinions in Algorithm SSF

In this section, we show that the small advantage established in Lemma 36 implies that all agents have a correct opinion with high probability. First, we prove that in every round, the number of agents with a correct weak-opinion is sufficiently large with high probability.

**Lemma 38.** For every $t \ge 2[m/h]$,

$$ \mathbb{P}\left(\bigcap_{s=t+1}^{t+[m/h]} \left\{ \sum_{j \in I} \tilde{Y}_s^{(j)} > \frac{n}{2} + 2\sqrt{n \log n} \right\} \right) \ge 1 - \frac{1}{n^7}. $$

*Proof.* Let $t_1 \ge 2[m/h]$, and $t_2 = t_1 + [m/h]$. By construction of Algorithm SSF, each non-source agent updates its weak-opinion exactly once between rounds $t_1+1$ and $t_2$ (included). For every $j \in I$, let $Z_j$ (resp. $Z'_j$) be the weak-opinion of Agent $j$ before (resp. after) its update.

Without loss of generality, we consider the case that the ordering of the updates respects the indices of the agents, i.e., $i < j$ if and only if Agent $i$ updates before Agent $j$ (or in the same round). With this assumption, for every $s \in \{t_1+1, \dots, t_2\}$, there exists $k \in \{0, \dots, n\}$ such that

$$ \sum_{j \in I} \tilde{Y}_s^{(j)} = \sum_{j=1}^{k} Z'_{j} + \sum_{j=k+1}^{n} Z_j =: \mathcal{Z}_k. \qquad (39) $$

By Lemma 36.(ii), for every $k \in \{0, \dots, n\}$,

$$ \mathbb{E}(\mathcal{Z}_k) \ge \frac{n}{2} + 4\sqrt{n \log n}. $$

By Lemma 36.(i), all $\{\tilde{Y}_s^{(j)}\}_{j \in I}$ are mutually independent, so we can apply Chernoff-Hoeffding's bound to obtain

$$ \mathbb{P} \left( \mathcal{Z}_k \le \frac{n}{2} + 2\sqrt{n \log n} \right) \le \exp(-8 \log n). \qquad (40) $$

Finally, we have

$$ \mathbb{P} \left( \bigcup_{s=t+1}^{t+[m/h]} \left\{ \sum_{j \in I} \tilde{Y}_s^{(j)} \le \frac{n}{2} + 2\sqrt{n \log n} \right\} \right) = \mathbb{P} \left( \bigcup_{k=0}^{n} \left\{ \mathcal{Z}_k \le \frac{n}{2} + 2\sqrt{n \log n} \right\} \right) \quad (\text{by Eq. (39)}) $$

$$ \le \sum_{k=0}^{n} \mathbb{P} \left( \mathcal{Z}_k \le \frac{n}{2} + 2\sqrt{n \log n} \right) \quad (\text{union bound}) $$

$$ \le n \exp(-8 \log n). \qquad (\text{by Eq. (40)}) $$

This concludes the proof of Lemma 38. □

Next, we demonstrate that combining the previous result with the majority operation ensures, with very high probability, the correctness of all opinions.

**Lemma 39.** Let $t \ge 3[m/h]$. For every $i \in I$,

$$ \mathbb{P} (Y_t^{(i)} = 1) \ge 1 - \frac{1}{n^6}. $$

*Proof.* Let $t \ge 3[m/h]$ and $i \in I$. Let $t_2 < t$ be the index of the last update round of Agent $i$ before round $t$, and let $t_1 = t_2 - [m/h]$. By definition, $Y_t^{(i)}$, was computed based on the second bit of all messages observed by Agent $i$ between rounds $t_1+1$ and $t_2$. Since the second bit of the message of a non-source agent always correspond to its weak opinion, $Y_t^{(i)}$ is a deterministic function of $\mathcal{R}_{t_1:t_2}^{(i)}$ and the set of all weak opinions between rounds $t_1$ and $t_2$, namely,

$$ \{\tilde{Y}_s^{(j)}, \text{ for } j \in I, s \in \{t_1+1, \dots, t_2\} \}. $$
Let A be the following event:

$$A := \bigcap_{s=t_1+1}^{t_2} \left\{ \sum_{j \in I} \tilde{Y}_s^{(j)} > \frac{n}{2} + 2\sqrt{n \log n} \right\},$$

where $c_1$ is given by Lemma 38. Note that:

(i) Let $s \in \{t_1+1, \dots, t_2\}$ and $t_0 = t_1 - \lfloor m/h \rfloor$. By Lemma 36.(i), $\tilde{Y}_s^{(i)}$ is a deterministic function of $\mathcal{R}_{t_0:t_1}^{(i)}$. Therefore, since $\{t_0+1, \dots, t_1\} \cap \{t_1+1, \dots, t_2\} = \emptyset$, $\mathcal{R}_{t_1:t_2}^{(i)}$ is independent from $\tilde{Y}_s^{(i)}$.

(ii) Let $j \neq i$ and $s \in \{t_1+1, \dots, t_2\}$. By Lemma 36.(i), there are two rounds $t'_1, t'_2$ s.t. $\tilde{Y}_s^{(j)}$ is a deterministic function of $\mathcal{R}_{t'_1:t'_2}^{(j)}$. Therefore, since $i \neq j$, $\mathcal{R}_{t_1:t_2}^{(i)}$ is independent from $\tilde{Y}_s^{(j)}$.

Together, (i) and (ii) imply that $\mathcal{R}_{t_1:t_2}^{(i)}$ is independent from A. Therefore, conditioning on A, the probability that a given message received by Agent i between rounds $t_1$ and $t_2$ has a second bit equal to 1, is at least (after noise is applied)

$$p := (1 - 2\delta) \left( \frac{1}{2} + c_1 \sqrt{\frac{\log n}{n}} \right) + 2\delta \left( \frac{1}{2} - 2\sqrt{\frac{\log n}{n}} \right) = \frac{1}{2} + 2\sqrt{\frac{\log n}{n}} (1 - 4\delta).$$

Denoting by $B_{m,p}$ a binomial random variable with parameters $m$ and $p$, this implies that

$$
\begin{align*}
\mathbb{P} (Y_t^{(i)} = 1 | A) &\ge \mathbb{P} (B_{m,p} > \frac{m}{2}) \\
&= \mathbb{P} \left( B_{m,p} > \mathbb{E}(B_{m,p}) - m \cdot 2\sqrt{\frac{\log n}{n}} (1 - 4\delta) \right) \\
&\ge 1 - \exp \left( -\frac{2}{n} \left( m \cdot 2\sqrt{\frac{\log n}{n}} (1 - 4\delta) \right)^2 \right) \quad \text{(by Chernoff-Hoeffding's bound)} \\
&\ge 1 - \exp(-8 \log n). \quad \text{(}m \ge \frac{n}{1-4\delta} \text{ by assumption in Eq. (30)}
\end{align*}
$$

Finally, by Lemma 38 and since $t_1 \ge 2\lfloor m/h \rfloor$,

$$\begin{align*}
\mathbb{P} (Y_t^{(i)} = 1) &= \mathbb{P}(A) \cdot \mathbb{P} (Y_t^{(i)} = 1 | A) \\
&\ge \left(1 - \frac{1}{n^7}\right) \cdot \left(1 - \frac{1}{n^8}\right) \\
&\ge 1 - \frac{1}{n^6}
\end{align*}$$

for $n$ large enough, which concludes the proof of Lemma 39. $\square$

<figure><img src="image_10.png" /></figure>

Finally, we can check that a consensus on the correct opinion happens for polynomially many rounds with high probability.

**Lemma 40.** For every $t_0 \ge 3\lfloor m/h \rfloor$, and any polynomial $P = O(n^3)$, all opinions are correct between rounds $t_0$ and $t_0 + P(n)$ w.h.p., i.e., for $n$ large enough:

$$\mathbb{P} \left( \bigcap_{t=t_0}^{t_0+P(n)} \bigcap_{i \in I} Y_t^{(i)} = 1 \right) \ge 1 - \frac{1}{n^2}.$$

*Proof.* The statement follows directly from Lemma 39 and a union bound over all agents and all rounds between $t_0$ and $t_0 + P(n)$, given that for $n$ large enough,

$$1 - n \cdot P(n) \cdot \frac{1}{n^6} \ge 1 - \frac{1}{n^2}.$$

<figure><img src="image_11.png" /></figure>
### 5.4.3 Proof of Theorem 5

Let $N$ be an arbitrary $\delta$-upper bounded noise matrix of size $d = 4$, and let

$$m = 2916 c_1 \cdot \frac{\delta n \log n}{(1 - 4\delta)^2} + n,$$

where $c$ is the constant in Eq. (30). Note that no attempt was made to optimize the additional constant factor of 2916; our focus is primarily on the asymptotic behavior of the dynamics. By Theorem 8, there exists a matrix $P$ s.t. the simulation of Algorithm SSF with artificial noise $P$ under $N$ is equivalent to Algorithm SSF under a $\delta'$-uniform noise, where

$$\delta' = \left( 4 + \frac{1}{54} \cdot \frac{1 - 4\delta}{\delta} \right)^{-1}.$$

Writing $A = \delta'^{-1}$, we have

$$\frac{(1 - 4\delta')^2}{\delta'} = A \cdot \left(1 - \frac{4}{A}\right)^2 = \frac{(A - 4)^2}{A} = \frac{\left[\frac{1}{54} - \frac{4\delta}{\delta}\right]^2}{4 + \frac{1}{54}\frac{1 - 4\delta}{\delta}} = \frac{1}{54^2\delta} \cdot \frac{(1 - 4\delta)^2}{4\delta + \frac{1}{54}(1 - 4\delta)} \ge \frac{1}{2916} \cdot \frac{(1 - 4\delta)^2}{\delta},$$

where in the last inequality we have used the fact that $\delta \in [0, 1/4)$ and so $4\delta + \frac{1}{54}(1 - 4\delta) \le 1$. Hence,

$$m \ge c_1 \cdot \frac{\delta' n \log n}{(1 - 4\delta')^2} + n.$$

Therefore, $m$ satisfies Eq. (30) with $\delta'$, and Theorem 5 follows from our analysis under uniform noise (see Lemma 40).
# Appendix

## A Pseudo-codes

**Algorithm 1:** Source Filter (SF) for Agent *i*

Communication alphabet $\Sigma := \{0,1\}$;

**Input:** Sample size $h$, Parameter $m$, phase duration $T := \lfloor m/h \rfloor$, sub-phase duration $w = \frac{100}{(1-2\delta)^2}$

$\text{Counter}_0, \text{Counter}_1 \leftarrow 0$;

**Phase 0:** for $t = 1, \dots, T$ do

```
    if Agent i is a source then Display preference else Display 0;
    S $\leftarrow$ observe the messages of h random agents;
    $\text{Counter}_1 \leftarrow \text{Counter}_1 + \text{Number of 1-messages in } S$;
```

**Phase 1:** for $t = T + 1, \dots, 2T$ do

```
    if Agent i is a source then Display preference else Display 1;
    S $\leftarrow$ observe the messages of h random agents;
    $\text{Counter}_0 \leftarrow \text{Counter}_0 + \text{Number of 0-messages in } S$;
```

$\tilde{Y}^{(i)} \leftarrow 1\{\text{Counter}_1 > \text{Counter}_0\}$ (breaking ties randomly); // Weak opinion

$Y^{(i)} \leftarrow \tilde{Y}^{(i)}$; // Opinion

$M \leftarrow \emptyset$; // Memory

$\ell \leftarrow 0$; // Index of the sub-phase

**Majority Boosting phase:** while $\ell \le 10 \log n + 1$ do

```
    Display opinion $Y^{(i)}$;
    S $\leftarrow$ observe the messages of h random agents;
    Add all messages of S into M;
    if $\ell \le 10 \log n$ and $|M| \ge w$ or $\ell = 10 \log n + 1$ and $|M| \ge m$ then
        // All sub-phases (except the final one) last $\lfloor w/h \rfloor$ rounds
        $Y^{(i)} \leftarrow$ majority opinion in M (breaking ties randomly);
        $M \leftarrow \emptyset$;
        $\ell \leftarrow \ell + 1$;
```
**Algorithm 2:** Self-stabilizing Source Filter (SSF) for Agent *i* in round *t*

Communication alphabet $\Sigma := \{0, 1\}^2$;

**Input:** Sample size *h*, Parameter *m*

$S \leftarrow$ observe the messages of *h* random agents;

$$M_{t+1}^{(i)} \leftarrow M_t^{(i)} + S;$$

**if** $|M_{t+1}^{(i)}| \ge m$ **then**
$$ \left\{
\begin{array}{l}
\tilde{Y}_{t+1}^{(i)} \leftarrow \underset{x \in \{0,1\}}{\operatorname{argmax}} \{ \text{Number of occurrences of } (1, x) \text{ in } M_{t+1}^{(i)} \} \quad \text{(Breaking ties randomly)} \\
Y_{t+1}^{(i)} \leftarrow \underset{x \in \{0,1\}}{\operatorname{argmax}} \{ \text{Number of occurrences of } (*, x) \text{ in } M_{t+1}^{(i)} \} \quad \text{(Breaking ties randomly)} \\
M_{t+1}^{(i)} \leftarrow \emptyset;
\end{array}
\right. $$

**else**

$$ \left\{
\begin{array}{l}
\tilde{Y}_{t+1}^{(i)} \leftarrow \tilde{Y}_t^{(i)}; \\
Y_{t+1}^{(i)} \leftarrow Y_t^{(i)};
\end{array}
\right. $$

**if** Agent *i* is a source **then** Display (1, preference) **else** Display $(0, \tilde{Y}_t^{(i+1)})$;

Variables are indexed by *i* and *t* for analysis purposes, but agents do not need to know the round number, nor do they need identifiers.

## B Probabilistic Tools

**Theorem 41** (Multiplicative Chernoff's bound). Let $X_1, \dots, X_n$ be i.i.d. random variables taking values in $\{0, 1\}$, let $X = \sum_{i=1}^n X_i$ and $\mu = \mathbb{E}(X) = n\mathbb{P}(X_1 = 1)$. Then it holds for all $\delta \in (0, 1)$ that

$$ \mathbb{P}(X \le (1 - \delta)\mu) \le \exp\left(-\frac{\delta^2 \mu}{2}\right). $$

The proof of the following result can be found in, e.g., [57].

**Theorem 42** (Chernoff-Hoeffding's bound). Let $X_1, \dots, X_n$ be independent random variables such that $a_i \le X_i \le b_i$ almost surely, let $X = \sum_{i=1}^n X_i$ and $\mu = \mathbb{E}(X)$. Then, for all $\delta > 0$,

$$ \mathbb{P}(X \le \mu - \delta), \mathbb{P}(X \ge \mu + \delta) \le \exp\left(-\frac{2\delta^2}{\sum_{i=1}^n (b_i - a_i)^2}\right) $$

In particular, if $X_1, \dots, X_n$ take values in $\{0, 1\}$, then

$$ \mathbb{P}(X \le \mu - \delta), \mathbb{P}(X \ge \mu + \delta) \le \exp\left(-\frac{2\delta^2}{n}\right). $$

## References

[1] Jon M Kleinberg. Navigation in a small world. Nature, 406(6798):845–845, 2000.

[2] Ofer Feinerman and Amos Korman. The ANTS problem. Distributed Computing, 30(3):149–168, 2017.

[3] Richard M Karp. Understanding science through the computational lens. Journal of Computer Science and Technology, 26(4):569–577, 2011.

[4] Emily Zhang, Jiajia Zhao, and Nancy A. Lynch. An upper and lower bound for the convergence time of house-hunting in Temnothorax ant colonies. J. Comput. Biol., 29(4):344–357, 2022.
[5] Brieuc Guinard and Amos Korman. Intermittent inverse-square lévy walks are optimal for finding targets of all sizes. *Science advances*, 7(15):eabe8211, 2021.

[6] Ehud Fonio, Yael Heyman, Lucas Boczkowski, Aviram Gelblum, Adrian Kosowski, Amos Korman, and Ofer Feinerman. A locally-blazed ant trail achieves efficient collective navigation despite limited information. *Elife*, 5:e20185, 2016.

[7] Yehuda Afek, Noga Alon, Omer Barad, Eran Hornstein, Naama Barkai, and Ziv Bar-Joseph. A biological solution to a fundamental distributed computing problem. *science*, 331(6014):183–185, 2011.

[8] Lucas Boczkowski, Emanuele Natale, Ofer Feinerman, and Amos Korman. Limits on reliable information flows through stochastic populations. *PLoS computational biology*, 14(6):e1006195, 2018.

[9] Nancy A. Lynch, Cameron Musco, and Merav Parter. Computational tradeoffs in biological neural networks: Self-stabilizing winner-take-all networks. In Christos H. Papadimitriou, editor, *8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA*, volume 67 of *LIPIcs*, pages 15:1–15:44. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.

[10] Yuval Emek and Roger Wattenhofer. Stone age distributed computing. In *Proceedings of the 2013 ACM symposium on Principles of distributed computing*, pages 137–146, 2013.

[11] Moses Charikar, Shivam Garg, Deborah M. Gordon, and Kirankumar Shiragur. A model for ant trail formation and its convergence properties (extended abstract). In James R. Lee, editor, *12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference*, volume 185 of *LIPIcs*, pages 85:1–85:2. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.

[12] Aviram Gelblum, Itai Pinkoviczky, Ehud Fonio, Abhijit Ghosh, Nir Gov, and Ofer Feinerman. Ant groups optimally amplify the effect of transiently informed individuals. *Nature communications*, 6(1):7729, 2015.

[13] Aviram Gelblum, Itai Pinkoviczky, Ehud Fonio, Nir S Gov, and Ofer Feinerman. Emergent oscillations assist obstacle negotiation during ant cooperative transport. *Proceedings of the National Academy of Sciences*, 113(51):14615–14620, 2016.

[14] Aviram Gelblum, Ehud Fonio, Yoav Rodeh, Amos Korman, and Ofer Feinerman. Ant collective cognition allows for efficient navigation through disordered environments. *Elife*, 9:e55195, 2020.

[15] James Aspnes and Eric Ruppert. An introduction to population protocols. *Middleware for Network Eccentric and Mobile Applications*, pages 97–120, 2009.

[16] Richard Karp, Christian Schindelhauer, Scott Shenker, and Berthold Vocking. Randomized rumor spreading. In *Proceedings 41st Annual Symposium on Foundations of Computer Science*, pages 565–574. IEEE, 2000.

[17] Pierre Fraigniaud and Emanuele Natale. Noisy rumor spreading and plurality consensus. *Distributed Computing*, 32(4):257–276, 2019.

[18] Ofer Feinerman, Bernhard Haeupler, and Amos Korman. Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication. *Distributed Computing*, 30(5):339–355, 2017.

[19] Andrea Clementi, Luciano Gualà, Emanuele Natale, Francesco Pasquale, Giacomo Scornavacca, and Luca Treisan. Consensus vs Broadcast, with and without Noise. In *ITCS 2020 - 11th Annual Innovations in Theoretical Computer Science*, 11th Innovations in Theoretical Computer Science Conference, pages 42–43, Seattle, United States, January 2020.

[20] Luca Becchetti, Andrea Clementi, Amos Korman, Francesco Pasquale, Luca Treisan, and Robin Vacus. On the role of memory in robust opinion dynamics. In *Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence*, IJCAI '23, pages 29–37, Macao, P.R.China, August 2023.
[21] Tamás Vicsek and Anna Zafeiris. Collective motion. *Physics Reports*, 517(3):71 – 140, 2012. Collective motion.

[22] Craig W Reynolds. *Flocks, herds and schools: A distributed behavioral model*, volume 21. ACM, 1987.

[23] Iain D Couzin, Jens Krause, Nigel R Franks, and Simon A Levin. Effective leadership and decision-making in animal groups on the move. *Nature*, 433(7025):513–516, 2005.

[24] Nitzan Razin, Jean-Pierre Eckmann, and Ofer Feinerman. Desert ants achieve reliable recruitment across noisy interactions. *Journal of the Royal Society Interface*, 10(82):20130079, 2013.

[25] Iain D Couzin. Collective cognition in animal groups. *Trends in cognitive sciences*, 13(1):36–43, 2009.

[26] Andrea Cavagna, Alessio Cimarelli, Irene Giardina, Giorgio Parisi, Raffaele Santagati, Fabio Stefanini, and Massimiliano Viale. Scale-free correlations in starling flocks. *Proceedings of the National Academy of Sciences*, 107(26):11865–11870, 2010.

[27] Stefano Marras, Robert S Batty, and Paolo Domenici. Information transfer and antipredator maneuvers in schooling herring. *Adaptive Behavior*, 20(1):44–56, 2012.

[28] Luc-Alain Giraldeau, Thomas J Valone, and Jennifer J Templeton. Potential disadvantages of using socially acquired information. *Philosophical Transactions of the Royal Society of London. Series B: Biological Sciences*, 357(1427):1559–1566, 2002.

[29] Amos Korman, Efrat Greenwald, and Ofer Feinerman. Confidence sharing: an economic strategy for efficient information flows in animal groups. *PLoS computational biology*, 10(10):e1003862, 2014.

[30] Edsger W. Dijkstra. Self-stabilizing systems in spite of distributed control. *Commun. ACM*, 17(11):643–644, 1974.

[31] Marco Schneider. Self-stabilization. *ACM Computing Surveys (CSUR)*, 25(1):45–67, 1993.

[32] Lucas Boczkowski, Emanuele Natale, Ofer Feinerman, and Amos Korman. Supplementary Information: Limits on reliable information flows through stochastic populations. *PLOS Computational Biology*, 14(8):e1006404, August 2018. Available at https://doi.org/10.1371/journal.pcbi.1006404.s001.

[33] Dana Angluin, James Aspnes, and David Eisenstat. A simple population protocol for fast robust approximate majority. *Distributed Computing*, 21(2):87–102, 2008.

[34] Anne Condon, Monir Hajiaghayi, David Kirkpatrick, and Ján Maňuch. Simplifying analyses of chemical reaction networks for approximate majority. In *International Conference on DNA-Based Computers*, pages 188–209. Springer, 2017.

[35] Talley Amir, James Aspnes, Petra Berenbrink, Felix Biermeier, Christopher Hahn, Dominik Kaaser, and John Lazarsfeld. Fast convergence of k-opinion undecided state dynamics in the population protocol model. In Rotem Oshman, Alexandre Nolin, Magnús M. Halldórsson, and Alkida Balliu, editors, *Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, PODC 2023, Orlando, FL, USA, June 19-23, 2023*, pages 13–23. ACM, 2023.

[36] David JT Sumpter, Jens Krause, Richard James, Iain D Couzin, and Ashley JW Ward. Consensus decision making by fish. *Current Biology*, 18(22):1773–1777, 2008.

[37] Oran Ayalon, Yigal Sternklar, Ehud Fonio, Amos Korman, Nir S Gov, and Ofer Feinerman. Sequential decision-making in ants and implications to the evidence accumulation decision model. *Frontiers in applied mathematics and statistics*, 7:672773, 2021.

[38] Alan Demers, Dan Greene, Carl Hauser, Wes Irish, John Larson, Scott Shenker, Howard Sturgis, Dan Swinehart, and Doug Terry. Epidemic algorithms for replicated database maintenance. In *Proceedings of the 6th ACM Symposium on Principles of Distributed Computing (PODC)*, 1987.
[39] Flavio Chierichetti, George Giakkoupis, Silvio Lattanzi, and Alessandro Panconesi. Rumor spreading and conductance. *Journal of the ACM (JACM)*, 65(4):1–21, 2018.

[40] David Kempe, Alin Dobra, and Johannes Gehrke. Gossip-based computation of aggregate information. In *44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.*, pages 482–491. IEEE, 2003.

[41] M. Mobilia, A. Petersen, and S. Redner. On the role of zealotry in the voter model. *Journal of Statistical Mechanics: Theory and Experiment*, 2007(08):P08029, 2007.

[42] Lucas Boczkowski, Amos Korman, and Emanuele Natale. Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits. In *Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*, Proceedings, pages 2540–2559. Society for Industrial and Applied Mathematics, January 2017.

[43] Francesco d'Amore, Andrea Clementi, and Emanuele Natale. Phase transition of a nonlinear opinion dynamics with noisy interactions. *Swarm Intelligence*, 16(4):261–304, December 2022.

[44] Petra Berenbrink, Felix Biermeier, and Christopher Hahn. Undecided State Dynamics with Stubborn Agents. *arXiv preprint arXiv:2406.07335*, June 2024.

[45] Dana Angluin, James Aspnes, Zoë Diamadi, Michael J Fischer, and René Peralta. Computation in networks of passively mobile finite-state sensors. *Distributed Computing*, 4(18):235–253, 2006.

[46] Petra Berenbrink, George Giakkoupis, and Peter Kling. Optimal time and space leader election in population protocols. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, *Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020*, pages 119–129. ACM, 2020.

[47] Luca Becchetti, Andrea Clementi, and Emanuele Natale. Consensus dynamics: An overview. *ACM SIGACT News*, 51(1):58–104, 2020.

[48] Petra Berenbrink, Colin Cooper, Cristina Gava, David Kohan Marzagão, Frederik Mallmann-Trenn, Tomasz Radzik, and Nicolas Rivera. Distributed averaging in opinion dynamics. In Rotem Oshman, Alexandre Nolin, Magnús M. Halldórsson, and Alkida Balliu, editors, *Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, PODC 2023, Orlando, FL, USA, June 19-23, 2023*, pages 211–221. ACM, 2023.

[49] Paul Bastide, George Giakkoupis, and Hayk Saribekyan. Self-stabilizing clock synchronization with 1-bit messages. In Dániel Marx, editor, *Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021*, pages 2154–2173. SIAM, 2021.

[50] Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan, Robin Vacus, and Isabella Ziccardi. The minority dynamics and the power of synchronicity. In David P. Woodruff, editor, *Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024*, pages 4155–4176. SIAM, 2024.

[51] Amos Korman and Robin Vacus. Early adapting to trends: Self-stabilizing information spread using passive communication. In Alessia Milani and Philipp Woelfel, editors, *PODC '22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25 - 29, 2022*, pages 235–245. ACM, 2022.

[52] Dan Gorbonos, Reuven Ianconescu, James G Puckett, Rui Ni, Nicholas T Ouellette, and Nir S Gov. Long-range acoustic interactions in insect swarms: an adaptive gravity model. *New Journal of Physics*, 18(7):073042, 2016.

[53] Raphaël Sarfati, Julie C Hayes, and Orit Peleg. Self-organization in natural swarms of photinus carolinus synchronous fireflies. *Science Advances*, 7(28):eabg9259, 2021.
[54] Amos Korman, Oran Ayalon, Yigal Sternklar, Ehud Fonio, Nir Gov, and Ofer Feinerman. Sequential decision-making in ants and implications to the evidence accumulation decision model. *Frontiers in Applied Mathematics and Statistics*, 7:37, 2021.

[55] Mohsen Ghaffari, Cameron Musco, Tsvetomira Radeva, and Nancy A. Lynch. Distributed house-hunting in ant colonies. In Chryssis Georgiou and Paul G. Spirakis, editors, *Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain*, July 21 - 23, 2015, pages 57-66. ACM, 2015.

[56] Stephen C Pratt, Eamonn B Mallon, David J Sumpter, and Nigel R Franks. Quorum sensing, recruitment, and collective decision-making during colony emigration by the ant leptothorax albipennis. *Behavioral Ecology and Sociobiology*, 52:117-127, 2002.

[57] Devdatt P Dubhashi and Desh Ranjan. Balls and bins: A study in negative dependence. *BRICS Report Series*, 3(25), 1996.