Amos Korman

Robin Vacus

Early Adapting to Trends: Self-Stabilizing Information Spread using Passive Communication *

How to efficiently and reliably spread information in a system is one of the most fundamental problems in distributed computing. Recently, inspired by biological scenarios, several works focused on identifying the minimal communication resources necessary to spread information under faulty conditions. Here we study the self-stabilizing bit-dissemination problem, introduced by Boczkowski, Korman, and Natale in [SODA 2017]. The problem considers a fully-connected network of n agents, with a binary world of opinions, one of which is called correct. At any given time, each agent holds an opinion bit as its public output. The population contains a source agent which knows which opinion is correct. This agent adopts the correct opinion and remains with it throughout the execution. We consider the basic PULL model of communication, in which each agent observes relatively few randomly chosen agents in each round. The goal of the non-source agents is to quickly converge on the correct opinion, despite having an arbitrary initial configuration, i.e., in a self-stabilizing manner. Once the population converges on the correct opinion, it should remain with it forever. Motivated by biological scenarios in which animals observe and react to the behavior of others, we focus on the extremely constrained model of passive communication, which assumes that when observing another agent the only information that can be extracted is the opinion bit of that agent. We prove that this problem can be solved in a poly-logarithmic in n number of rounds with high probability, while sampling a logarithmic number of agents at each round. Previous works solved this problem faster and using fewer samples, but they did that by decoupling the messages sent by agents from their output opinion, and hence do not fit the framework of passive communication. Moreover, these works use complex recursive algorithms with refined clocks that are unlikely to be used by biological entities. In contrast, our proposed algorithm has a natural appeal as it is based on letting agents estimate the current tendency direction of the dynamics, and then adapt to the emerging trend.

Introduction 1.Background and motivation

Disseminating information from one or several sources to the whole population is a fundamental building block in a myriad of distributed systems [START_REF] Censor-Hillel | Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance[END_REF]; [START_REF] Demers | Epidemic algorithms for replicated database maintenance[END_REF]; [START_REF] Karp | Randomized rumor spreading[END_REF]; [START_REF] Chierichetti | Rumor spreading and conductance[END_REF]; [START_REF] Giakkoupis | On the randomness requirements of rumor spreading[END_REF], including in multiple natural systems [START_REF] David | Consensus decision making by fish[END_REF]; [START_REF] Razin | Desert ants achieve reliable recruitment across noisy interactions[END_REF]; [START_REF] Feinerman | Individual versus collective cognition in social insects[END_REF]. This task becomes particularly challenging when the system is prone to faults Boczkowski et al. (2018b); [START_REF] Georgiou | Asynchronous gossip[END_REF][START_REF] Georgiou | Meeting the deadline: on the complexity of fault-tolerant continuous gossip[END_REF]; [START_REF] Dutta | On the complexity of information spreading in dynamic networks[END_REF], or when the agents or their interactions are constrained [START_REF] Boczkowski | Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits[END_REF]; [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF]. These issues find relevance in a variety of systems, including insect populations [START_REF] Razin | Desert ants achieve reliable recruitment across noisy interactions[END_REF], chemical reaction networks [START_REF] Ho-Lin Chen | Speed faults in computation by chemical reaction networks[END_REF], and mobile sensor networks [START_REF] Yick | Wireless sensor network survey[END_REF]. In particular, in many biological systems, the internal computational abilities of individuals are impressively diverse, whereas the communication capacity is highly limited [START_REF] Robert Mr | Interindividual use of echolocation calls: eavesdropping by bats[END_REF]; [START_REF] Razin | Desert ants achieve reliable recruitment across noisy interactions[END_REF]; [START_REF] Feinerman | Individual versus collective cognition in social insects[END_REF]. An extreme situation, often referred to as passive communication [START_REF] Gerald S Wilkinson | Information transfer at evening bat colonies[END_REF], is when information is gained by observing the behavior of other animals, which, in some cases, may not even intend to communicate [START_REF] Cvikel | Bats aggregate to improve prey search but might be impaired when their density becomes too high[END_REF]; [START_REF] Giraldeau | Social foraging theory[END_REF]. Such public information can reflect on the quality of possible behavioral options, hence allowing to improve fitness when used properly [START_REF] Danchin | Public information: from nosy neighbors to cultural evolution[END_REF].

Consider, for example, the following scenario that serves as an inspiration for our model. A group of n animals is scattered around an area searching for food. Assume that one side of the area, say, either the eastern side or the western side, is preferable (e.g., because it contains more food or because it is less likely to attract predators). However, only a few animals know which side is preferable. These knowledgeable animals will therefore spend most of their time in the preferable side of the area. Other animals would like to exploit the knowledge held by the knowledgeable animals, but they are unable to distinguish them from others. Instead, what they can do, is to scan the area in order to roughly estimate how many animals are on each side, and, if they wish, move between the two sides. Can the group of non-knowledgeable animals manage to locate themselves on the preferable side relatively fast, despite initially being spread in an arbitrary way while being completely uncorrelated?

The scenario above illustrates the notion of passive communication. The decision that an animal must make at any given time is to specify on which side of the area it should forage. This choice would be visible by others, and would in fact be the only information that an animal could reveal. Moreover, it cannot avoid revealing it. In particular, even the knowledgeable animals, who do not necessarily wish to communicate intentionally, cannot avoid revealing their "correct" choice. Assuming these animals do not actively try to harm others, they would simply reside on the preferable side, and promote this choice passively. The unknowledgeable animals, on the other hand, have a clearer incentive to cooperate, and they could, in principle, manipulate their choices to enhance the convergence process towards the correct choice. However, if their algorithm is also required to self-stabilize, then such a manipulation would be highly limited because, eventually, the choices should converge on one particular choice.

The problem

This paper studies the self-stabilizing bit-dissemination problem, introduced by Boczkowski, Korman, and Natale in [START_REF] Boczkowski | Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits[END_REF], with the aim of solving it using passive communication. The problem considers a fully-connected network of n agents, and a binary world of opinions, say {0, 1}. One of these opinions is called correct and the other is called wrong. Execution proceeds in synchronous rounds (though agents do not have knowledge about the round number). At any given round t, each agent i holds an opinion bit Y (i) t ∈ {0, 1} (viewed as its output variable). The population contains one source agent which knows which opinion is correct. This agent adopts the correct opinion and remains with it throughout the execution. Each agent knows whether or not it is the source, which can be formalized by assuming a designated source-bit in the state of an agent indicating this fact. We study the basic PU LL model of communication [START_REF] Demers | Epidemic algorithms for replicated database maintenance[END_REF]; [START_REF] Karp | Randomized rumor spreading[END_REF]; Boczkowski et al. (2018b), in which in each round, each agent sees the information held by other agents, chosen uniformly at random (with replacement), where is small compared to n. We consider the passive communication model which assumes that the only information that can be obtained by sampling an agent is its opinion bit. Hence, sampling agents is equivalent to receiving an integer between 0 and corresponding to the number of agents with opinion 1 among the sampled agents.

In the self-stabilizing framework, the goal of the non-source agents is to quickly converge on the correct opinion, despite having an arbitrary initial configuration, that is set by an adversary (and despite not being able to distinguish the source from non-sources). We note that although the initial states of agents are arbitrary, we assume that their source-bit is not corrupted, and therefore, they reliably know whether or not they are the source. Moreover, by our assumption, it is guaranteed that there is only one source agent in the system1 . The adversary may initially set a different opinion to the source, but then the value of the correct bit would change, and the convergence should be guaranteed with respect to the new value.

The running time of the protocol corresponds to the first round t con that the configuration of opinions reached a consensus on the correct opinion, and remained unchanged forever after. We say that a protocol converges in time T with high probability (w.h.p) if t con ≤ T with probability at least 1 -1/n c , for some constant c > 1. Note that we do not require agents to irrevocably commit on their final opinion, but rather that they eventually converge on the correct opinion without necessarily being aware that convergence has happened.

On the difficulties resulting from using passive communication. Previous works on the selfstabilizing bit-dissemination problem focused on identifying the minimal number of bits per interaction (message size) that need to be revealed in order to solve the problem in a short time. Boczkowski, Korman, and Natale showed in [START_REF] Boczkowski | Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits[END_REF] that the problem can efficiently be solved in Õ(log n) rounds w.h.p, by sampling = 2 agents at each round and using messages of size 3 bits. The protocol therein is based on agents having clocks that tick at each round. However, because of the self-stabilizing setting, the values of these clocks may initially be completely uncorrelated. The idea in that paper was to use 3 auxiliary bits in the messages to synchronize the clocks of agents in a self-stabilizing manner. These clocks were then used to facilitate the convergence of the opinion bit, which encapsulated another bit in the message. These 4 bits were then compressed to 3 bits using a recursive message-size-reduction mechanism. By reducing the message size of that clock-synchronization scheme to 1, and using a version of the aforementioned recursive message-size-reduction mechanism, a recent work by Bastide, Giakkoupis, and Saribekyan allows to reduce the message size of the self-stabilizing bit-dissemination problem to 1 bit [START_REF] Bastide | Self-Stabilizing Clock Synchronization with 1bit Messages[END_REF]. Moreover, stabilization is achieved in O(log n) rounds w.h.p., by sampling a single agent at each round. Importantly, however, both of these works decoupled the opinion of an agent from the message it uses, and hence, do not fit the framework of passive communication. Moreover, these works use complex recursive algorithms with refined clocks that are unlikely to be used by biological entities. Instead, we are interested in identifying algorithms that have a more natural appeal.

To illustrate the difficulty of self-stabilizing information spread under passive communication, let us consider a more generalized problem than bit-dissemination called majority bit-dissemination. In this problem, the population contains k ≥ 1 source agents which may not necessarily agree on which opinion is correct. Specifically, in addition to its opinion, each source-agent stores a preference bit ∈ {0, 1}. Let k i be the number of source agents whose preference is i. Assume that sufficiently more source agents share a preference i over 1 -i (e.g., at least twice as many), and call i the correct bit. Then, w.h.p., all agents (including the sources that might have the opposite preference) should converge their opinions on the correct bit in poly-logarithmic time, and remain with that opinion for polynomial time2 . The authors of [START_REF] Boczkowski | Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits[END_REF] showed that the self-stabilizing majority bit-dissemination problem can be solved in logarithmic time, using messages of size 3 bits, and the authors of [START_REF] Bastide | Self-Stabilizing Clock Synchronization with 1bit Messages[END_REF] showed how to reduce the message size to 1. As mentioned, the messages in these protocols were different than the opinions, which were stored as internal variables, and hence the protocols in [START_REF] Boczkowski | Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits[END_REF]; [START_REF] Bastide | Self-Stabilizing Clock Synchronization with 1bit Messages[END_REF] are not based on passive communication. In fact, the following simple argument implies that this problem could not be solved in poly-logarithmic time under the model of passive communication, even if the sample size is n (i.e., all agents are being observed in each round)! Assume by contradiction that there exists a self-stabilizing algorithm that solves the majority bitdissemination problem using passive communication. Let us run this algorithm on a scenario with k 1 = n/2 and k 0 = n/4. Since k 1 k 0 , then after a poly-logarithmic time, w.h.p., all agents would have opinion 1, and would remain with that opinion for polynomial time. Denote by t 0 the first time after convergence, and let s denote the internal state of one of the n/4 non-source agents at time t 0 . Similarly, let s denote the internal state at time t 0 of one of the n/4 source agents with preference 0. Now consider a second scenario, where we have k 0 = n/4 and k 1 = 0. An adversary sets the internal states of agents (including their opinions) as follows. The internal states of the k 0 source agents (with preference 0) are all set to be s . Moreover, their opinions (that these sources must publicly declare on) are all 1. Next, the adversary sets the internal states of all non-source agents to be s, and their opinions to be 1. We now compare the execution of the algorithm in the first scenario (starting at time t 0 ) with the execution in the second scenario (starting at time 0, i.e., after the adversary manipulated the states). Note that both scenarios start with all opinions being 1. Hence, since we consider the passive communication model, all observations in the first round of the corresponding executions, would be unanimously 1. Moreover, as long as no agent changes its opinion in both scenarios, all observations would continue to be unanimously 1. Furthermore, it is given that from time t 0 , w.h.p., all agents in the first scenario remain with opinion 1 for a polynomially long period. Therefore, using a union bound argument, it is easy to see that also in the second scenario, w.h.p., all agents would remain with opinion 1 for polynomial time. This contradicts the fact that in the second scenario, w.h.p., the agents should converge on the opinion 0 in poly-logarithmic time.

Note that the aforementioned impossibility result does not preclude the possibility of solving the selfstabilizing bit dissemination problem in the passive communication model, which does not involve a conflict between sources. Indeed, the authors of [START_REF] Boczkowski | Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits[END_REF] have suggested several candidate protocols which worked well in simulations3 , however, as mentioned therein, their analysis appears to be beyond the reach of currently known techniques regarding randomly-interacting agent systems in self-stabilizing contexts.

Our results

We propose a simple algorithm that efficiently solves the self-stabilizing bit-dissemination problem in the passive communication model. The algorithm has a natural appeal as it is based on letting agents estimate the current tendency direction of the dynamics, and then adapt to the emerging trend. More precisely (but still, informally), each non-source agent counts the number of agents with opinion 1 it observes in the current round and compares it to the number observed in the previous round. If more 1's are observed now, then the agent adopts the opinion 1, and similarly, if more 0's are observed now, then it adopts the opinion 0 (if the same number of 1's is observed in both rounds then the agent does not change its opinion). Intuitively, on the global level, this behavior creates a persistent movement of the average opinion of the non-source agents towards either 0 or 1, which "bounces" back when hitting the wrong opinion.

More formally, we first describe the following algorithm. In addition to the opinion bit, the algorithm at an agent uses two internal variables at round t, called count t and count t-1 . The former variable aims to store the number of 1's observe in the previous round, while the latter aims to store the number of 1's observe in the current round. Hence, both encode a number in {0, . . . , }, and can be stored using O(log ) bits of memory. The following procedure is executed at each round separately by each agent. As an input, a given agent observes the opinions of randomly chosen agents. Let J t denote the set of agents it sampled at round t, and let S t (J t ) = {Y (j) t } j∈Jt denote the set containing their opinions at round t. Finally, for any set A of opinions, let COUNT(A) denote the number of 1-opinions in A.

Input: S t (J t ) count t ← COUNT(S t (J t )) ; if count t > count t-1 then Y t+1 ← 1 ; else if count t < count t-1 then Y t+1 ← 0 ; else Y t+1 ← Y t ;
As it turns out, one feature of the aforementioned protocol will make the analysis difficult -that is, that Y t and Y t+1 are dependent, even when conditioning on (x t-1 , x t ). This is because count t-1 is used to compute both Y t and Y t+1 . For example, if the set J t-1 sampled at round t -1 happens to contain more 1's, then count t-1 is larger. In this case, Y t has a higher chance of being 1, and Y t+1 has a higher chance of being 0. For this reason we introduce a modified version of the protocol that solves this dependence issue. The idea is to partition the set of opinions sampled at round t into 2 sets of equal size. One subset will be used to compare with a subset of round t -1, and the other subset will be used to compare with a subset of round t + 1. Note that this implies that the set of agents sampled in a round is 2 rather than , however, since we are interested in the case = O(log n), this does not cause a problem. This modified protocol, called Follow the Emerging Trend (FET), is the one we shall actually analyze. Note that, although we used time indices for clarity, the protocol does not require the agents to know t. The following consists of the main result in the paper.

Protocol 1: Follow the Emerging Trend (FET) at round t Input: S t (J t ) Partition S t (J t ) into two sets S t , S t of equal size uniformly at random ;

count t ← COUNT(S t ) ; count t ← COUNT(S t ) ; if count t > count t-1 then Y t+1 ← 1 ; else if count t < count t-1 then Y t+1 ← 0 ; else Y t+1 ← Y t ;
Theorem 1. Algorithm FET solves the self-stabilizing bit-dissemination problem in the passive communication model. It converges in O(log 5/2 n) rounds on the correct opinion, with high probability, while relying on = O(log n) samples in each round, and using O(log ) bits of memory per agent.

Related works

In recent years, the study of population protocols has attracted significant attention in the distributed computing community Alistarh andGelashvili (2018, 2015); [START_REF] Alistarh | Time-Space Trade-offs in Population Protocols[END_REF]; [START_REF] Angluin | A simple population protocol for fast robust approximate majority[END_REF]; [START_REF] Aspnes | An Introduction to Population Protocols[END_REF]. These models often consider agents that interact under random meeting patterns while being restricted in both their memory and communication capacities. By now, we understand the computational power of such systems rather well, but apart from a few exceptions, this understanding is limited to non-faulty scenarios.

The framework of opinion dynamics corresponds to settings of multiple agents, where in each round, each agent samples one or more agents at random, extracts their opinions, and employs a certain rule for updating its opinion. The study of opinion dynamics crosses disciplines, and is highly active in physics and computer science, see review e.g., in [START_REF] Becchetti | Consensus dynamics: An overview[END_REF]. Many of the models of opinion dynamics can be considered as following passive communication, since the information an agent reveals coincides with its opinion. Generally speaking, however, the typical scientific approach in opinion dynamics is to start with some simple update rule, and analyze the resulting dynamics, rather than tailoring an updating rule to solve a given distributed problem. For example, perhaps the most famous dynamics in the context of interacting particles systems concerns the voter model [START_REF] Milton | Interacting particle systems[END_REF]. In theoretical computer science, extensive research has been devoted to analyzing the time to reach consensus, following different updating rules including the 3-majority [START_REF] Doerr | Stabilizing consensus with the power of two choices[END_REF], Undecided-State Dynamics [START_REF] Angluin | A simple population protocol for fast robust approximate majority[END_REF], and others. In these works, consensus should be reached either on an arbitrary value, or on the majority (or plurality) opinion, as evident in the initial configuration.

In many natural settings, however, the group must converge on a particular consensus value that is a function of the environment. Moreover, agents have different levels of knowledge regarding the desired value, and the system must utilize the information held by the more knowledgeable individuals [START_REF] David | Consensus decision making by fish[END_REF]; [START_REF] Ayalon | Sequential Decision-Making in Ants and Implications to the Evidence Accumulation Decision Model[END_REF]; [START_REF] Korman | Confidence Sharing: An Economic Strategy for Efficient Information Flows in Animal Groups[END_REF][START_REF] Harikrishnan Rajendran | Ants resort to majority concession to reach democratic consensus the presence of a persistent minority[END_REF]. As explained in more detail below, when communication is restricted, and the system is prone to faults, this task can become challenging.

Propagating information from one or more sources to the rest of the population has been the focus of a myriad of works in distributed computing. This dissemination problem has been studied under various models taking different names, including rumor spreading, information spreading, gossip, broadcast, and others, see e.g., [START_REF] Giakkoupis | Tight bounds for rumor spreading with vertex expansion[END_REF]; [START_REF] Censor-Hillel | Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance[END_REF]; [START_REF] Demers | Epidemic algorithms for replicated database maintenance[END_REF]; [START_REF] Karp | Randomized rumor spreading[END_REF]; [START_REF] Chierichetti | Rumor spreading and conductance[END_REF]; [START_REF] Giakkoupis | On the randomness requirements of rumor spreading[END_REF]. A classical algorithm in the PU LL model spreads the opinion of the source to all others in 2 log n rounds, by letting each uninformed agent copy the opinion of an informed agent whenever seeing one for the first time [START_REF] Karp | Randomized rumor spreading[END_REF]. Unfortunately, this elegant algorithm does not suit all realistic scenarios, since its soundness crucially relies on the absence of misleading information. To address such issues, rumor spreading has been studied under different models of faults. One line of research investigates the case that messages may be corrupted with some fixed probability [START_REF] Feinerman | Individual versus collective cognition in social insects[END_REF]; Boczkowski et al. (2018a). Another model of faults is self-stabilization Dijkstra (1974), where the system must eventually converge on the opinion of the source regardless of the initial configuration of states [START_REF] Edsger | Self-stabilizing Systems in Spite of Distributed Control[END_REF]. For example, the algorithm in [START_REF] Karp | Randomized rumor spreading[END_REF] fails in this setting, since non-source agents may be initialized to "think" that they have already been informed by the correct opinion, while they actually hold the wrong opinion.

More details on previous works regarding the self-stabilizing bit-dissemination problem. The self-stabilizing bit-dissemination problem was introduced in [START_REF] Boczkowski | Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits[END_REF], with the aim of minimizing the message size. As mentioned therein, if all agents share the same notion of global time, then convergence can be achieved in O(log n) time w.h.p. even under passive communication. The idea is that agents divide the time horizon into phases of length T = 4 log n, and that each phase is further subdivided into 2 subphases of length 2 log n each. In the first subphase of each phase, if a non-source agent observes an opinion 0, then it copies it as its new opinion, but if it sees 1 it ignores it. In the second subphase, it does the opposite, namely, it adopts the output bit 1 if and only if it sees an opinion 1. Now, consider the first phase. If the source supports opinion 0 then at the end of the first subphase, every output bit would be 0 w.h.p., and the configuration would remain that way forever. Otherwise, if the source supports 1, then at the end of the second subphase all output bits would be 1 w.h.p., and remain 1 forever.

The aforementioned protocol indicates that the self-stabilizing bit-dissemination problem could be solved efficiently by running a self-stabilizing clock-syncronization protocol in parallel to the previous example protocol. This parallel execution amounts to adding one bit to the message size of the clock synchronization protocol. The main technical contribution of [START_REF] Boczkowski | Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits[END_REF], as well as the focus of subsequent work in [START_REF] Bastide | Self-Stabilizing Clock Synchronization with 1bit Messages[END_REF], was solving the self-stabilizing clock-synchronization using as few as possible bits per message. In fact, the authors in [START_REF] Bastide | Self-Stabilizing Clock Synchronization with 1bit Messages[END_REF] managed to do so using 1-bit messages. This construction thus implies a solution to the self-stabilizing bit-dissemination problem using 2 bits per message. A recursive procedure, similar to the one established in [START_REF] Boczkowski | Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits[END_REF], then allowed to further compress the 2 bits into 1-bit messages. Importantly, however, the 1-bit message revealed by an agent is different from its opinion bit, which is kept in the protocols of [START_REF] Boczkowski | Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits[END_REF]; [START_REF] Bastide | Self-Stabilizing Clock Synchronization with 1bit Messages[END_REF] as an internal variable. At first glance, to adhere to the passive communication model, one may suggest that agents simply choose their opinion to be this 1-bit message used in [START_REF] Bastide | Self-Stabilizing Clock Synchronization with 1bit Messages[END_REF], just for the purpose of communication, until a consensus is reached, and then switch the opinion to be the correct bit, once it is identified. There are, however, two difficulties to consider regarding this approach. First, in our setting, the source agent does not change its opinion (which, in the case of [START_REF] Bastide | Self-Stabilizing Clock Synchronization with 1bit Messages[END_REF], may prevent the protocol from reaching a consensus at all). Second, even assuming that the protocol functions properly despite the source having a stable opinion, it is not clear how to transition from the "communication" phase (where agents use their opinion to operate the protocol, e.g., for synchronizing clocks) to the "consensus" phase (where all opinions must be equal to the correct bit at every round). For instance, the first agents to make the transition may disrupt other agents still in the first phase.

Proof of Theorem 1: General Overview

The goal of this section is to prove Theorem 1. The O(log ) bits upper bound on the memory complexity clearly follows from the fact that the only variables kept by the FET algorithm (Protocol 1) are count and count , which are used to count the number of 1's in a sample (of size ).

Since the protocol is symmetric with respect to the opinion of the source, we may assume without loss of generality that the source has opinion 1. Our goal would therefore be to show that the FET algorithm converges to 1 fast, w.h.p., regardless of the initial configuration of non-source agents. Note that in order to achieve running time of O(T ) w.h.p guarantee, is it sufficient to show that the algorithm stabilizes in T rounds with probability at least 1 -1/n , for some > 0. Indeed, because of the self-stabilizing property of the algorithm, the probability that the algorithm does not stabilize within 2T / rounds is at most

(1/n ) 2/ = 1/n 2 .
For the sake of analysis, let x t denote the fraction of agents with opinion 1 at round t among the whole population of agents (including the source). We shall extensively use the two dimensional grid

G := {0, 1 n , . . . , n-1 n , 1} 2 .
When analyzing what happens at round t + 2, the x-axis of G would represent x t , and the y-axis would represent x t+1 .

Observation 1. For any round t, conditioning on x t = x t , and x t+1 = x t+1 , the probability that a non-source agent i has opinion 1 on round t + 2 is

P Y (i) t+2 = 1 x t = x t x t+1 = x t+1 = P (B (x t+1 ) > B (x t )) + 1 {Y (i) t+1 =1} • P (B (x t+1 ) = B (x t )) .
(1)

Moreover, there are independent binary random variables X 1 , . . . , X n such that x t+2 is distributed as

1 n n i=1 X i . Eventually, E x t+2 x t = x t x t+1 = x t+1 = P (B (x t+1 ) > B (x t ))+x t+1 •P (B (x t+1 ) = B (x t ))+ 1 n (1-P (B (x t+1 ) ≥ B (x t ))).
(2)

The proof of Observation 1 is deferred to Appendix B. A consequence of Observation 1, is that the execution of the algorithm induces a Markov chain on G. This Markov chain has a unique absorbing state, (1, 1), since we assumed the source to have opinion 1. To prove Theorem 1 we therefore only need to bound the time needed to reach (1, 1).

Partitioning the grid into domains

Let us fix 0 < δ < 1/2 and λ n = 1 log 1/2+δ n . We partition G into domains as follows (see illustration on Figure 1a).

Green 1 = (x t , x t+1 ) s.t. x t+1 ≥ x t + δ , Purple 1 = (x t , x t+1 ) s.t. 1 log n ≤ x t < 1 2 -3δ and (1 -λ n ) • x t ≤ x t+1 < x t + δ , Red 1 = (x t , x t+1 ) s.t. 1 log n ≤ x t+1 and x t < 1 2 -3δ and x t -δ ≤ x t+1 < (1 -λ n ) • x t , Cyan 1 = (x t , x t+1 ) s.t. 0 ≤ min(x t , x t+1 ) < 1 log n and x t -δ < x t+1 < x t + δ , Yellow = (x t , x t+1 ) s.t. 1 2 -3δ ≤ x t < 1 2 ≤ 3δ and 1 2 -4δ ≤ x t+1 ≤ 1 2 + 4δ and |x t+1 -x t | < δ .
Similarly, for the former 4 domains, we define Green 0 , Purple 0 , Red 0 and Cyan 0 to be their symmetric equivalents (w.r.t the point ( 1 2 , 1 2 )), and finally define: Green = Green 0 ∪ Green 1 , Purple = Purple 0 ∪ Purple 1 , Red = Red 0 ∪ Red 1 , and Cyan = Cyan 0 ∪ Cyan 1 . We shall analyze each area separately, conditioning on the Markov chain to be at any point in that area, and focusing on the number of rounds required to escape the area, and the probability that this escape is made to a particular other area. Figure 1b represents a sketch of the proof of Theorem 1, which may help to navigate the intermediate results.

As it happens, the dynamics starting from a point (x t , x t+1 ) highly depends on the difference between x t and x t+1 . Roughly speaking, the larger |x t+1 -x t | is the faster is the convergence. For this reason, we refer to |x t+1 -x t | as the speed of the point (x t , x t+1 ). (This could also be viewed as the "derivative" of the process at time t.)

Analyzing the Markov chain at different domains

Due to lack of space, most proofs are deferred to the appendix. We have decided to include in the extended abstract the core of the proof of the main lemma that concerns the Yellow domain (Section 3.2), which was one of the more challenging results obtained in this paper. In addition, we also provide the core of the proof of the main lemma that concerns the Cyan domain (Section 4), because this part of the state-space is essential for understanding the dynamics of the protocol.

Let us now give an overview of the intermediate results. First we consider Green, in which the speed of points is large. In Lemma 1 we show that from points in that domain, non-source agents reach a consensus in just one round w.h.p. In particular, if the Markov chain is at some point in Green 1 , then the consensus (1) . The numbers next to the self-loops indicate that the process stays in the corresponding domain for this number of rounds w.p. at least 1 -1/n Ω(1) . The source is assumed to have opinion 1. will be on 1, and we are done. If, on the other hand, the Markov chain is in Green 0 , then the consensus of non-source agents would be on 0. As we show later, in that case the Markov chain would reach Cyan 1 in one round w.h.p.

Lemma 1 (Green area). Assume that c is sufficiently large. If (x t , x t+1 ) ∈ Green 1 , then w.h.p., for every non-source agent i, Y (t+2) i = 1. Similarly, if (x t , x t+1 ) ∈ Green 0 , then w.h.p., for every non-source agent i, Y

(t+2) i = 0.
The proof of Lemma 1 follows from a simple application of Hoeffding's inequality, and is deferred to Appendix C.1. Next, we consider the area Purple, and show that the population goes from Purple to Green in just one round, w.h.p. In Purple, the speed is relatively low, and x t and x t+1 are quite far from 1/2. On the next round, we expect x t+2 to be close to 1/2, thus gaining enough speed in the process to join Green. The proof of the following lemma is rather straightforward, and is deferred to Appendix C.2.

Lemma 2 (Purple area). Assume that c is sufficiently large. If (x t , x t+1 ) ∈ Purple 1 , then (x t+1 , x t+2 ) ∈ Green 1 w.h.p. Similarly, if (x t , x t+1 ) ∈ Purple 0 , then (x t+1 , x t+2 ) ∈ Green 0 w.h.p.
Next, we bound the time that can be spent in Red, by using the fact that as long as the process is in Red 1 (resp., Red 0 ), x t (resp., (1 -x t )) decreases (deterministically) by at least a multiplicative factor of (1 -λ n ) at each round. After a poly-logarithmic number of rounds, the Markov chain must leave Red and in this case, we can show that it cannot reach Yellow right away. The proof of the following lemma is again relatively simple, and is deferred to Appendix C.3.

Lemma 3 (Red area). Consider the case that (x t0 , x t0+1 ) ∈ Red for some round t 0 , and let t 1 = min{t ≥ t 0 , (x t , x t+1 ) / ∈ Red}. Then t 1 < t 0 + log 1/2+2δ n, and (x t1 , x t1+1 ) / ∈ Yellow ∪ Red.

Next, we bound the time that can be spent in Cyan 1 . (A similar result holds for Cyan 0 .) Roughly speaking, this area corresponds to the situation in which, over the last two consecutive rounds, the population is in an almost-consensus over the wrong opinion. In this case, many agents (a constant fraction) see only 0 in their corresponding samples in the latter round. As a consequence, everyone of them who will see at least one opinion 1 in the next round, will adopt opinion 1. We can expect this number to be of order = O(log n). This means that, as long as the Markov chain is in Cyan 1 , the value of x t would grow by a logarithmic factor in each round. This implies that within log(n)/ log(log n) rounds, the Markov chain will leave the Cyan 1 area and go to Green 1 ∪ Purple 1 . Informally, this phenomenon can be viewed as a form of "bouncing" -the population of non-sources reaches an almost consensus on the wrong opinion, and "bounces back", by gradually increasing the fraction of agents with the correct opinion, up to an extent that is sufficient to enter Green 1 ∪ Purple 1 . The proof of the following lemma is given in Section 4.

Lemma 4 (Cyan area). Consider the case that (x t0 , x t0+1 ) ∈ Cyan 1 for some round t 0 , and let t 1 = min{t ≥ t 0 , (x t , x t+1 ) / ∈ Cyan 1 }. Then with probability at least 1 -1/n Ω(1) we have (1)

t 1 < t 0 + log(n)/ log(log n), and (2) (x t1 , x t1+1 ) ∈ Green 1 ∪ Purple 1 .
Eventually, we consider the central area, namely, Yellow, where the speed is very low, and bound the time that can be spent there. The proof of the following lemma is more complex than the previous ones, and it appears in Section 3.

Lemma 5 (Yellow area). Consider the case that (x t0 , x t0+1 ) ∈ Yellow. Then, w.h.p.,

min{t > t 0 s.t. (x t , x t+1 ) / ∈ Yellow} < t 0 + O(log 5/2 n).

Assembling the lemmas

Given the aforementioned lemmas, we have everything we need to prove our main result.

Proof of Theorem 1. Recall that without loss of generality, we assumed the source to have opinion 1. The reader is strongly encouraged to refer to Figure 1b to follow the ensuing arguments more easily.

• Let t 1 = min{t ≥ 0, (x t , x t+1 ) / ∈ Yellow}. If (x 0 , x 1 ) ∈ Yellow, we apply Lemma 5 to get that t 1 < O(log 5/2 n) w.h.p. and (x t1 , x t1+1 ) ∈ Red ∪ Cyan ∪ Purple ∪ Green.

(3)

Else, (x 0 , x 1 ) / ∈ Yellow so t 1 = 0, and Eq. (3) also holds.

• Let t 2 = min{t ≥ t 1 , (x t , x t+1 ) / ∈ Red}. If (x t1 , x t1+1 ) ∈ Red, we apply Lemma 3 to get that

t 2 < t 1 + log 1/2+2δ n w.h.p. and (x t2 , x t2+1 ) ∈ Cyan ∪ Purple ∪ Green. (4)
Else, (x t1 , x t1+1 ) / ∈ Red so t 1 = t 2 , and by Eq. ( 3), it implies that Eq. (4) also holds.

• Let t 3 = min{t ≥ t 2 , (x t , x t+1 ) / ∈ Cyan}. If (x t2 , x t2+1
) ∈ Cyan, we apply Lemma 4 to get that t 3 < t 2 + log(n)/ log(log n) and (x t3 , x t3+1 ) ∈ Purple ∪ Green with probability at least 1 -1/n Ω(1) .

(5) Else, (x t2 , x t2+1 ) / ∈ Cyan so t 2 = t 3 , and by Eq. ( 4), it implies that Eq. ( 5) also holds.

• Let t 4 = min{t ≥ t 3 , (x t , x t+1 ) ∈ Green}. By Lemma 2, and by Eq. ( 5), we have that t 4 = t 3 or t 4 = t 3 + 1 w.h.p.

If (x t4 , x t4+1 ) ∈ Green 1 , then by Lemma 1 the consensus is reached on round t 4 +1. Otherwise, if (x t4 , x t4+1 ) ∈ Green 0 , by Lemma 1, we obtain that x t4+2 = 1/n w.h.p. (meaning that all agents have opinion 0 except the source). Therefore, in this case, either (x t4+1 , x t4+2 ) ∈ Green 0 or (x t4+1 , x t4+2 ) ∈ Cyan 1 (because for a point (x t , x t+1 ) to be in any other area, it must be the case that x t+1 ≥ 1/ log(n), by definition). In the former case, we apply Lemma 1 again to get that x t4+3 = 1/n w.h.p., which implies that (x t4+2 , x t4+3 ) = (1/n, 1/n) ∈ Cyan 1 . As we did before, we apply Lemma 4, 2 and 1 to show that, with probability at least 1 -1/n Ω(1) , the system goes successively to Purple 1 ∪ Green 1 , then to Green 1 , and eventually reaches the absorbing state (1, 1) in less than log(n)/ log(log n) + 2 rounds. Altogether, the convergence time is dominated by t 1 , and is hence O(log n) 5/2 with probability at least 1-1/n , for some > 0. As mentioned, this implies that for any given c > 1, the algorithm reaches consensus in O(log n) 5/2 time with probability at least 1 -1/n c . This concludes the proof of Theorem 1.

Escaping the Yellow Area

The goal of this section is to prove Lemma 5. It might be easier for the reader to think of the Yellow area as a square. Formally, let us define Yellow as the following square bounding box around Yellow:

Yellow = (x t , x t+1 ) s.t. 1/2 -4δ ≤ x t , x t+1 ≤ 1/2 + 4δ .
Obviously, Yellow ⊂ Yellow , so in order to prove Lemma 5 it suffices to prove Lemma 6 below. Lemma 6. Consider that (x t0 , x t0+1 ) ∈ Yellow . Then, w.h.p., min{t > t 0 s.t. (x t , x t+1 ) / ∈ Yellow } < t 0 + O(log 5/2 n).

General structure of the proof

In order to prove Lemma 6, we first partition Yellow , as follows (for an illustration, see Figure 2):

A 1 = {(x t , x t+1 ) | (i) x t+1 ≥ 1/2 and (ii) x t+1 -x t ≥ x t -1/2} ∩ Yellow , B 1 = {(x t , x t+1 ) | (i) x t+1 ≥ x t and (ii) x t+1 -x t < x t -1/2} ∩ Yellow , C 1 = {(x t , x t+1 ) | (i) x t+1 < 1/2 and (ii) x t+1 ≥ x t } ∩ Yellow .
Similarly, we define A 0 , B 0 , C 0 their symmetric equivalents (w.r.t the point ( 12 , 1 2 )), and Remark 1. At various times throughout our analysis, we would like to calculate different statistical properties of the system at round t + 2, conditioning on (x t , x t+1 ) ∈ G, as was done in e.g., Observation 1. For the sake of clarity of presentation, in all subsequent cases, we shall omit the conditioning notation. The reader should therefore keep in mind, that whenever such properties are calculated, they are actually done while conditioning on x t = x t and x t+1 = x t+1 , where the point (x t , x t+1 ) would always be clear from the context. For example, in Lemma 7 below, the probability P ((x t+1 , x t+2 ) / ∈ Yellow ) is calculated conditioning on x t = x t , x t+1 = x t+1 , where (x t , x t+1 ) ∈ A, yet this conditioning is omitted.

A = A 0 ∪ A 1 , B = B 0 ∪ B 1 , and C = C 0 ∪ C 1 .
In the next lemma, we study the distribution of the future location of any point (x t , x t+1 ) ∈ A. This area happens to be ideal to escape Yellow , because it allows the Markov chain to quickly build up "speed". Item (a) in the next lemma says that, with some probability that depends on the current speed the following occur: (1) the speed in the following round increases by a factor of two, and (2) the process in the next round either remains in A, or goes outside of Yellow . Note that when the current speed is not too low, that is, when x t+1 -x t > 1/ √ n, this combined event happens with constant probability. Item (b) says that with constant probability, (1) the speed in the next round would not be too low, and (2) the process either remains in A, or goes outside of Yellow .

Lemma 7. If (x t , x t+1 ) ∈ A, and provided that δ is small enough and n is large enough, (a) We have P

(x t+1 , x t+2 ) / ∈ Yellow \ A ∩ |x t+2 -x t+1 | > 2|x t+1 -x t | > 1-exp -3n • (x t+1 -x t ) 2 . (b) There exists a constant c 2 = c 2 (c) > 0 s.t. P (x t+1 , x t+2 ) / ∈ Yellow \ A ∩ |x t+2 -x t+1 | > 1/ √ n > c 2 .
Now, we can iteratively use the previous result to prove that any state in A has a reasonable chance to escape Yellow . The proofs of both Lemmas 7 and 8 are deferred to Appendix C.5.1.

Lemma 8. There is a constant c 3 = c 3 (c) s.t. if (x t0 , x t0+1 ) ∈ A, then P (∃t 1 < t 0 + log n, (x t1 , x t1+1 ) / ∈ Yellow ) > c 3 .

We are left with proving that the system cannot be stuck in B or C for too long. We start with B. The analysis of this area is relatively complex, because it is difficult to rule out the possibility that the Markov chain remains there at a low speed. We prove that any state in B must either make a step towards escaping Yellow , or have a good chance of leaving B. The proof of the following lemma is given in Section 3.2.

Lemma 9. There are constants c 4 , c 5 > 0 such that if (x t , x t+1 ) ∈ B, then either

(a) |x t+1 -1/2| > 1 + c 4 / √ |x t -1/2|, or (b) P ((x t+1 , x t+2 ) / ∈ B) > c 5 .
Now, we can iteratively use the previous result to prove that any state in B either leaves B or escapes Yellow' in a reasonable amount of time. The proof of Lemma 10 is deferred to Section C.5.2.

Lemma 10. If (x t0 , x t0+1 ) ∈ B, then, w.h.p., min{t ≥ t 0 , (x t , x t1 ) / ∈ B} < t 0 + √ c c4 • log 3/2 n.
We are left with proving that the system cannot stay in C for too long. Fortunately, from this area, the Markov chain is naturally pushed towards A, which makes the analysis simple. The proof of Lemma 11 is deferred to Section C.5.3.

Lemma 11. There is a constant c 6 > 0 such that if (x t , x t+1 ) ∈ C, then max P ((x t+1 , x t+2 ) / ∈ Yellow \ A) , P ((x t+2 , x t+3 ) / ∈ Yellow \ A) > c 6 .

Eventually, we have all the necessary results to conclude the proof regarding the Yellow area.

Proof of Lemma 6. By Lemma 8, if (x t0 , x t0+1 ) ∈ A, then P (∃t 1 < t 0 + log n, (x t1 , x t1+1 ) / ∈ Yellow ) > c 3 > 0. By Lemma 11, this implies that if (x t0 , x t0+1 ) ∈ A ∪ C,

P (∃t 1 < t 0 + log n + 2, (x t1 , x t1+1 ) / ∈ Yellow ) > min(c 3 , c 3 • c 6 ) = c 3 • c 6 > 0. (6)
By Lemma 10, w.h.p., whenever the process is at B, it does not spend more than ( √ c/c 4 )•log 3/2 n consecutive rounds there. This means, that for any constant c > 0, during c log 5/2 n consecutive rounds, w.h.p., we must either leave Yellow or be at A ∪ C on at least 6), the probability that the system fails to escape Yellow in each of these occasions is at most (1 -

c log 5/2 n ( √ c/c4)•log 3/2 n = c c4 √ c • log n distinct rounds. By Eq. (
c 3 • c 6 ) (c c4/ √ c)•log n .
Taking c to be sufficiently large concludes the proof of Lemma 6.

Proof of Lemma 9 -The main lemma regarding area B

The goal of this section is to prove Lemma 9, which concerns Area B inside the Yellow domain. Without loss of generality, we may assume that (x t , x t+1 ) ∈ B 1 (the same arguments apply to B 0 symmetrically).

The proof shall use the following lemma which concerns competition between two coins, both being tossed k times. One coin has a probability of p to be "heads", and the other has probability q. We assume that p < q, although the difference is very small, q -p ≤ 1/ √ k. The lemma upper bounds the probability that the more likely coin wins, that is, that the coin with parameter q falls on "heads" more times than the other coin. The proof is deferred to Appendix A.2.2. Lemma 12. There exists a constant α > 1, s.t. for every integer k, every p, q ∈ [1/3, 2/3] with p < q and q -p ≤ 1/ √ k, we have

P (B k (p) < B k (q)) < 1 2 + α(q -p) √ k - 1 2 P (B k (p) = B k (q)) .
Next, let us define

g(x, y) = P (B (y) > B (x)) + y • P (B (y) = B (x)) + 1 n (1 -P (B (y) ≥ B (x))) , (7)
so that, conditioning on (x t , x t+1 ), E(x t+2 ) = g(x t , x t+1 ) by Observation 1. We start with the following claim, which will be used to prove the subsequent claim. The proof of Claim 1 is deferred to Appendix A.3.

Claim 1. Let x ∈ [1/3, 2/3]. On the interval [x, x + 1/ √ ],
and for large enough, y → g(x, y) -y is a strictly increasing function of y.

The next claim concerns the fixed points of g(x, y) as a function of y.

Claim 2. For any given x ∈ [1/2 + 4/n, 1/2 + 4δ], as a function of y, the equation y = g(x, y) has at most one solution on the interval [x, x+1/ √ ]. Moreover, in the case that it has no solution, then g(x, x+1/ √ ) < x + 1/ √ .

Proof. First, we claim that g(x, x) < x. Let p = P(B (x) > B (x)) and q = P(B (x) = B (x)). We rearrange the definition of g slightly to obtain g(x, x)

= p + x • q + p n . Moreover, x = x • (2p + q) ≥ (1 + 8/n) • p + x • q > g(x, x)
, where the first inequality is because x ≥ 1/2 + 4/n. Next, let h(y) = g(x, y) -y. Function h is continuous, and what we just showed implies h(x) < 0. Moreover, by Claim 1, we know that h is strictly increasing on

[x, x + 1/ √ ]. Therefore, either h(x + 1/ √ ) ≥ 0, in which case there is a unique y ∈ [x, x + 1/ √ ] such that h(y ) = 0; or h(x + 1/ √ ) < 0, i.e., g(x, x + 1/ √ ) < x + 1/ √
, in which case the equation y = g(x, y) has no solution on the interval.

For every x ∈ [1/2+4/n, 1/2+4δ], let f (x) be the solution of the equation y = g(x, y) in the interval [x, x+ 1/ √ ] if it exists, and f (x) = x + 1/ √ otherwise. Note that by Claim 2, with this definition we always have

g(x, f (x)) ≤ f (x). ( 8
)
Claim 3. For any x ∈ [1/2 + 4/n, 1/2 + 4δ], it holds that

f (x) -x > 1 2α √ x - 1 2 ,
where α > 1 is the constant stated in Lemma 12.

Proof. If f (x) is not a solution to y = g(x, y), then by definition f (

x) = x + 1/ √ , i.e., f (x) -x = 1 √ > 1 2α √ x - 1 2 ,
and so the statement holds. Otherwise, then f (x) = g(x, f (x)) and belongs to [x, x + 1/ √ ]. By Lemma 12, there exists α > 0 s.t.

P (B (f (x)) > B (x)) < 1 2 + α(f (x) -x) √ - 1 2 P (B (f (x)) = B (x)) .
This can be plugged into the definition of f (Eq. ( 7)) to give

f (x) < 1 2 + α(f (x) -x) √ + f (x) - 1 2 P (B (f (x)) = B (x)) + 1 n which we can rewrite, (1 -P (B (f (x)) = B (x))) f (x) - 1 2 < α(f (x) -x) √ + 1 n .
This gives

f (x) -x > 1 -P (B (f (x)) = B (x)) α √ f (x) - 1 2 - 1 α • n √ > 1 2α √ x - 1 2 - 2 n ,
where the last inequality comes from the upper bound P (B (f (x)) = B (x)) < 1/2 (which is true when is large enough), and from the fact that f (x) > x. Since (x -1/2) ≥ 4/n, this implies

f (x) -x > 1 4α √ x - 1 2 ,
as desired. This completes the proof of Claim 3.

Next, rewriting f (x) -x = (f (x) -1/2) -(x -1/2), we get from Claim 3 that for every x ∈ [1/2 + 4/n, 1/2 + 4δ], f (x) - 1 2 > 1 + 1 4α √ • x - 1 2 . ( 9
)
We are now ready to conclude the proof of Lemma 9. Let c 4 = 1/4α. • Otherwise, if x t ∈ [1/2 + 4/n, 1/2 + 4δ] and x t+1 > f (x t ), then by Eq. ( 9),

x t+1 - 1 2 > f (x t ) - 1 2 > 1 + c 4 √ x t - 1 2 ,
and so (a) holds.

• Else, f (x t ) ≥ x t+1 . Moreover, by the definitions of f and B 1 , we have the following relation:

x t + 1/ √ ≥ f (x t ) ≥ x t+1 ≥ x t . ( 10
)
By Eq. ( 8), g(x t , f (x t )) ≤ f (x t ), i.e., g(x t , f (x t )) -f (x t ) ≤ 0. By Claim 1, for large enough, function y → g(x t , y) -y is strictly increasing on [x t , x t + 1/ √ ]. Eq. ( 10) ensures that x t+1 and f (x t ) are within this interval, so g(x t , x t+1 ) -x t+1 ≤ g(x t , f (x t )) -f (x t ) ≤ 0, i.e., g(x t , x t+1 ) ≤ x t+1 . Recall that E(x t+2 ) = g(x t , x t+1 ) -therefore, E(x t+2 ) ≤ x t+1 . By Lemma 16 (see Appendix B.2), there is a constant probability c 5 that x t+2 < x t+1 . If this the case, since x t+1 > 1/2 and by the definition of B, we get that (x t+1 , x t+2 ) / ∈ B and (b) holds.

This concludes the proof of Lemma 9.

Proof of Lemma -Cyan area

The goal of this section is to prove Lemma 4, which concerns Area Cyan. We distinguish between two cases. Case 1. x t0 ≥ 1/ log(n). In this case, by definition of Cyan 1 , we must have x t0+1 < 1/ log(n). Note that in this case, for n large enough, x t0+1 -δ < 1/ log(n) -δ < 0. Then,

• either x t0+2 < x t0+1 + δ. In this case, x t0+1 -δ < 0 < x t0+2 < x t0+1 + δ, and so (x t0+1 , x t0+2 ) ∈ Cyan 1 (but this time Case 2 applies).

• or x t0+2 ≥ x t0+1 + δ, and so (x t0+1 , x t0+2 ) ∈ Green 1 .

• (We can't have x t0+2 = 0 because the source is assumed to have opinion 1.) 2c) /2. We will study separately three ranges of value for x t+1 . Claim 4 below concerns small values of x t+1 , Claim 5 concerns intermediate values of x t+1 , and Claim 6 concerns large values of x t+1 . Their proofs follow from simple applications of Chernoff's bound, and so they are deferred to Appendix C.4.

Case 2. x t0 < 1/ log(n). Let γ = γ(c) = (1 -1/e) • exp(-2c)/2 and let K = K(c) = c • exp (-
Claim 4. If x t < 1/ log(n), and if 0 < x t+1 ≤ 1/ , then P x t+2 > K 2 x t+1 log n > 1 -exp -K 8 log n . Claim 5. If x t < 1/ log(n), and if 1/ < x t+1 ≤ γ, then P (x t+2 > γ) > 1-exp -γn 8 > 1-exp -K 8 log n . Claim 6. If x t < 1/ log(n), and if x t+1 > γ, then P x t+2 > 1 2 > 1 -exp -n 18 > 1 -exp -K 8 log n .
We say that a round t is successful if (x t , x t+1 ) ∈ Cyan 1 , and the event of either Claim 4, 5 or 6 happens. Formally,     

x t+1 ≤ 1/ and x t+2 > Kx t+1 log n (corresponding to Claim 4), or 1/ < x t+1 ≤ γ and x t+2 > γ (corresponding to Claim 5), or γ < x t+1 and (x t+1 , x t+2 ) / ∈ Cyan 1 (corresponding to Claim 6).

Let X be the number of successful rounds starting from t 0 . This definition implies that necessarily,

X < log(n/ ) log(K • log n/2) + 2 := X max .
Indeed, since x t0+1 > 1/n (by definition of Cyan 1 ),

• log(n/ )/ log(K • log(n)/2) rounds are always enough to get x t+1 > 1/

• one more round is enough to get x t+1 > γ

• one more round is enough to get x t+1 > 1/2, in which case (x t , x t+1 ) / ∈ Cyan 1 .

Therefore, by Claims 4, 5 and 6, the probability that, starting from t 0 , all rounds are successful until the system is out of Cyan 1) . Moreover, for any successful round t, x t+2 > x t+1 (by definition of a successful round) and x t+1 < δ+1/ log(n) (this is a straightforward consequence of the definition of Cyan 1 ). Thus, by construction of the partition, we must have (x t+1 , x t+2 ) ∈ Cyan 1 ∪ Green 1 ∪ Purple 1 . This implies that (x t1 , x t1+1 ) ∈ Green 1 ∪ Purple 1 , which concludes the proof of Lemma 4.

1 is at least 1 -exp -K 8 log n Xmax ≥ 1 -X max • exp -K 8 log n = 1 -1/n Ω(

Discussion and Future Work

This paper considers a natural problem of information spreading in a self-stabilizing context, where it is assumed that a source agent has useful knowledge about the environment, and others would like to learn this information without being able to distinguish the source from non-source agents. Motivated by biological scenarios, our focus is on solutions that utilize passive communication. We identify an extremely simple algorithm, called FET (Protocol 1), which has a natural appeal: In each round, each (non-source) agent estimates the current tendency direction of the dynamics, and then adapts to the emerging trend. The correct operation of the algorithm does not require that the source actively cooperates with the algorithm, and instead, only assumes that it maintains its correct option throughout the execution.

Different performance parameters may be further optimized in future work. For example, our analysis uses O(log n) samples per round, and it would be interesting to see whether the problem can be solved in poly-logarithmic time w.h.p, by using only a constant number of samples per round. Also, we do not exclude the possibility that a tighter analysis of Algorithm FET would reduce our bound on the running time. In addition, our framework assumes the presence of a single source agent, but as mentioned, it can also allow for a constant number of sources, as long as it is guaranteed that all sources agree on the correct opinion. No attempt has been made to consider a larger regime of sources (beyond a constant), although we believe that such a framework is also manageable.

Finally, as a more philosophical remark, we note that early adapting to emerging trends is a common strategy in humans, which is, in some sense, encouraged by modern economic systems. For example, investing in a successful company can yield large revenues, especially if such an investment is made before others notice its high potential. On a global scale, the collective benefits of this strategy are typically associated with economic growth. This paper shows that such a strategy can also have a collective benefit that traces back to basic aspects of collective decision-making, suggesting the possibility that it may have evolved via groupselection. With this in mind, it would be interesting to empirically check whether such a strategy exists also in other animal groups, e.g., fish schools [START_REF] David | Consensus decision making by fish[END_REF] or ants [START_REF] Harikrishnan Rajendran | Ants resort to majority concession to reach democratic consensus the presence of a persistent minority[END_REF].

Proof. Let Y i , i ∈ {1, . . . , k} be i.i.d. random variables with

Y i =      1 w.p. p(1 -q), 0 w.p. pq + (1 -p)(1 -q), -1 w.p. (1 -p)q. Then P (B k (p) ≥ B k (q)) = P k i=1 Y i ≥ 0 = P 1 k k i=1 (Y i -(p -q)) ≥ (q -p) .
Since each Y i is bounded, and E(Y i ) = (p -q), we can apply Hoeffding's inequality (Theorem 3) to get

P (B k (p) ≥ B k (q)) ≤ exp - 2k 2 (q -p) 2 4k = exp - 1 2 k(q -p) 2 .
Lemma 13 is not particularly effective when p and q are close to each other. For such cases, we shall use the following lemma.

Lemma 14. Let λ > 0. There exist = (λ) and K = K(λ), s.t. for every p, q ∈ [1/2-, 1/2+ ] with p < q, and every k > K,

P (B k (p) < B k (q)) > 1 2 + λ • (q -p) - 1 2 P (B k (p) = B k (q)) .
Proof. For every p, q ∈ [0, 1], we have

P (B k (q) < B k (p)) = k d=1 P (B k (q) = B k (p) -d) = k d=1 P (|B k (q) -B k (p)| = d) • P (B k (q) = B k (p) -d) P (|B k (q) -B k (p)| = d) = k d=1 P (|B k (q) -B k (p)| = d) • P (B k (q) = B k (p) -d) P (B k (q) = B k (p) -d) + P (B k (p) = B k (q) -d) , so P (B k (p) < B k (q)) -P (B k (q) < B k (p)) = k d=1 P (|B k (q) -B k (p)| = d) • P (B k (p) = B k (q) -d) -P (B k (q) = B k (p) -d) P (B k (p) = B k (q) -d) + P (B k (q) = B k (p) -d) . (11)
Let us compute P (B k (q) = B k (p) -d):

P (B k (q) = B k (p) -d) = k-d i=0 P (B k (q) = i) • P (B k (p) = i + d) = k-d i=0 k i k i + d q i (1 -q) k-i p i+d (1 -p) k-i-d = (p(1 -q)) d k-d i=0 k i k i + d (qp) i ((1 -q)(1 -p)) k-i-d := (p(1 -q)) d A k,d,p,q , where A k,d,p,q := k-d i=0 k i k i + d (qp) i ((1 -q)(1 -p)) k-i-d .
Since A k,d,p,q is symmetric w.r.t. p, q, i.e., A k,d,p,q = A k,d,q,p , we can simplify Eq. ( 11) as

P (B k (p) < B k (q)) -P (B k (q) < B k (p)) = k d=1 P (|B k (q) -B k (p)| = d) • (q(1 -p)) d -(p(1 -q)) d (q(1 -p)) d + (p(1 -q)) d . (12)
Intuitively, the quantity

(q(1 -p)) d -(p(1 -q)) d (q(1 -p)) d + (p(1 -q))
d can be seen as the "advantage" given by playing with the better coin (q) in a k-coin-tossing contest, knowing that one coin hit "head" d times more than the other. Before we continue, we need the following simple claim.

Claim 7. For every a, b ∈ [0, 1] with a > b, the sequence

a n -b n a n + b n , n ∈ N is increasing in n. Proof. Rewrite a n -b n a n + b n = 2a n a n + b n -1 = 2 • 1 1 + (b/a) n -1,
and notice that, since a > b, ((b/a) n ), n ∈ N is a decreasing sequence.

Claim 8. Let 0 < γ < 1 and d ∈ N. There exists = (γ, d), such that for every p, q ∈ [1/2 -, 1/2 + ] with p < q, (q(1 -p))

d -(p(1 -q)) d (q(1 -p)) d + (p(1 -q)) d > (q -p) • 2dγ.
Proof. First, by a telescopic argument:

(q(1 -p)) d -(p(1 -q)) d = (q(1 -p) -p(1 -q)) d-1 i=0 (q(1 -p)) d-1-i • (p(1 -q)) i = (q -p) d-1 i=0 (q(1 -p)) d-1-i • (p(1 -q)) i . Note that lim p,q→1/2 d-1 i=0 (q(1 -p)) d-1-i • (p(1 -q)) i = d-1 i=0 1 4 d-1-i • 1 4 i = d-1 i=0 1 2 2d-2 = d • 1 2 2d-2
, and that lim p,q→1/2

(q(1 -p)) d + (p(1 -q)) d = 1 4 d + 1 4 d = 1 2 2d-1
.

Hence, since γ < 1, and provided that p, q are close enough to 1/2, we obtain

(q(1 -p)) d -(p(1 -q)) d (q(1 -p)) d + (p(1 -q)) d > (q -p) • 2dγ,
which completes the proof of Claim 8.

20

Next, let λ > 0 as in the Lemma's statement, and let λ = λ + 1. Denote D = λ + 1 > λ and γ = λ /D < 1. By Claim 8, there exists = (γ, D) = (λ), s.t. for p, q

∈ [1/2 -, 1/2 + ], (q(1 -p)) D -(p(1 -q)) D (q(1 -p)) D + (p(1 -q)) D > (q -p) • 2λ . (13)
Now we derive a lower bound on Eq. ( 12):

P (B k (p) < B k (q)) -P (B k (q) < B k (p)) = k d=1 P (|B k (q) -B k (p)| = d) • (q(1 -p)) d -(p(1 -q)) d (q(1 -p)) d + (p(1 -q)) d (Eq. (12)) ≥ k d=D P (|B k (q) -B k (p)| = d) • (q(1 -p)) d -(p(1 -q)) d (q(1 -p)) d + (p(1 -q)) d ≥ k d=D P (|B k (q) -B k (p)| = d) • (q(1 -p)) D -(p(1 -q)) D (q(1 -p)) D + (p(1 -q)) D (by Claim 7) > (q -p) • 2λ k d=D P (|B k (q) -B k (p)| = d)
(by Eq. ( 13))

= (q -p) • 2λ • (1 -P (|B k (q) -B k (p)| < D)) .
Since λ > λ, and since P (|B k (q) -B k (p)| < D) tends to 0 as k tends to +∞, there exists

K = K(λ) s.t. for all k > K, P (B k (p) < B k (q)) -P (B k (q) < B k (p)) > (q -p) • 2λ. (14)
Eventually, we write

P (B k (p) < B k (q)) = 1 -P (B k (q) < B k (p)) -P (B k (p) = B k (q)) > 1 -P (B k (p) < B k (q)) + 2λ(q -p) -P (B k (p) = B k (q)) .
(by Eq. ( 14))

Hence,

P (B k (p) < B k (q)) > 1 2 + λ(q -p) - 1 2 P (B k (p) = B k (q)) ,
which concludes the proof of Lemma 14.

A.2.2 Lower bounds on the probability that the worse coin wins

We now deal with the opposite problem, that is, to lower bound the probability that the underdog coin wins. Formally, Lemma 15. For every p, q ∈ [0, 1] s.t. p < q and every integer k, we have

P (B k (p) > B k (q)) ≥ 1 -Φ √ k(q -p) σ - C σ √ k ,
where C = 0.4748 and σ = p(1 -p) + q(1 -q).

Proof. Let Y i , i ∈ {1, . . . , k} be i.i.d. random variables with

Y i =      1 w.p. p(1 -q), 0 w.p. pq + (1 -p)(1 -q), -1 w.p. (1 -p)q.
Let µ = E(Y 1 ) = (p -q), σ = Var(Y 1 ) = p(1 -p) + q(1 -q), and ρ = E(|Y 1 -µ| 3 ). We have

P (B k (p) > B k (q)) = P k i=1 Y i > 0 = P 1 √ k k i=1 (Y i -(p -q)) > √ k(q -p) = P 1 σ √ k k i=1 (Y i -(p -q)) > √ k(q -p) σ = P Z > √ k(q -p) σ ,
where

Z = 1 σ √ k k i=1 (Y i -(p -q)) .
By the Berry-Esseen theorem (Theorem 5),

P Z < √ k(q -p) σ -Φ √ k(q -p) σ < Cρ σ 3 √ k , implying that 1 -Φ √ k(q -p) σ -P Z > √ k(q -p) σ < Cρ σ 3 √ k ,
and so

P Z > √ k(q -p) σ > 1 -Φ √ k(q -p) σ - Cρ σ 3 √ k ,
where, e.g., C = 0.4748. Since ρ < σ 2 , we end up with

P (B k (p) > B k (q)) ≥ 1 -Φ √ k(q -p) σ - C σ √ k ,
which concludes the proof.

Just as Lemma 14 was a version of Lemma 13 optimized for cases where p and q are close to each other, Lemma 12 (stated in Section 3.2) complements Lemma 15 in such situations.

Proof of Lemma 12. Recall that (see Eq. ( 12) in the proof of Lemma 14):

P (B k (p) < B k (q)) -P (B k (q) < B k (p)) = k d=1 P (|B k (q) -B k (p)| = d) • (q(1 -p)) d -(p(1 -q)) d (q(1 -p)) d + (p(1 -q)) d . ( 15
)
The following claim is analogous to Claim 8, but this time we are looking for an upper bound (instead of a lower bound) on the same quantity.

Claim 9. There exists a constant α > 1, s.t. for every integer k, every p, q ∈ [1/3, 2/3] with p < q, and all d ∈ N,

(q(1 -p)) d -(p(1 -q)) d (q(1 -p)) d + (p(1 -q)) d < αd • (q -p).
Proof. First, we use a well-known identity:

(q(1 -p)) d -(p(1 -q)) d = (q(1 -p) -p(1 -q)) d-1 i=0 (q(1 -p)) d-1-i • (p(1 -q)) i = (q -p) d-1 i=0 (q(1 -p)) d-1-i • (p(1 -q)) i ≤ d • (q -p) (q(1 -p)) d-1 ≤ αd • (q -p) (q(1 -p)) d ,
where α is any upper bound on 1/(q(1 -p)), e.g., α = 9. Hence,

(q(1 -p)) d -(p(1 -q)) d (q(1 -p)) d + (p(1 -q)) d ≤ αd • (q -p) • (q(1 -p)) d (q(1 -p)) d + (p(1 -q)) d ≤ αd • (q -p),
which concludes the proof of Claim 9.

Using Claim 9 on Eq. ( 15), we obtain

P (B k (p) < B k (q)) -P (B k (q) < B k (p)) ≤ α • (q -p) k d=1 d • P (|B k (q) -B k (p)| = d) . ( 16
)
Claim 10. For every p, q ∈ [1/3, 2/3] with p < q, and every integer k,

E (|B k (p) -B k (q)|) ≤ 2kq(1 -q) + k • (q -p).
Proof. For i ∈ {1, . . . , k}, let X

i , X

(2) i ∼ B(q) and Y i ∼ B(1 -p/q) be independent random variables. Let

X (1) = k i=1 X (1) i , X (2) = k i=1 X (2) i , Z = k i=1 X (2) i • Y i , and X(2) = k i=1 X (2) i • (1 -Y i ) = X (2) -Z.
Clearly, X (1) ∼ B k (q) and X (2) ∼ B k (q). Since for every i, X

(2) i

• (1 -Y i ) = 1 if X (2) i = 1 and Y i = 0, 0 otherwise, we obtain that X(2) ∼ B k (q • (1 -(1 -p/q))) = B k (p). Similarly, for every i, X (2) i • Y i = 1 if X (2) i
= 1 and Y i = 1, 0 otherwise, hence, we obtain that Z ∼ B k (q • (1 -p/q)) = B k (q -p). We notice that (X (1) , X (2) ) are independent, as well as (X (1) , X(2) ). Hence

E (|B k (q) -B k (p)|) = E |X (1) -X(2) | = E |X (1) -X (2) + Z| ≤ E |X (1) -X (2) | + Z = E |X (1) -X (2) | + E(Z).
We have E(Z) = k(q -p), and

E |X (1) -X (2) | = E X (1) -X (2) 2 ≤ E X (1) -X (2) 2
(by Jensen inequality, and the fact that g 1) , X (2) ∼ B k (q) and are independent).

(x) = x 2 is convex) = Var X (1) -X (2) (since E X (1) -X (2) = 0) = 2kq(1 -q), (X (
which concludes the proof of Claim 10.

We note that

k d=1 d • P (|B k (q) -B k (p)| = d) = E (|B k (q) -B k (p)|) ≤ 2kq(1 -q) + k • (q -p) (by Claim 10) ≤ 2kq(1 -q) + √ k (since q -p ≤ 1/ √ k) ≤ 2 √ k.
Eventually, Eq. ( 16) becomes

P (B k (p) < B k (q)) -P (B k (q) < B k (p)) ≤ 2α • (q -p) √ k. (17)
To conclude, we write

P (B k (p) < B k (q)) = 1 -P (B k (q) < B k (p)) -P (B k (p) = B k (q)) < 1 -P (B k (p) < B k (q)) + 2α • (q -p) √ k -P (B k (p) = B k (q)) .
(by Eq. ( 17))

Hence,

P (B k (p) < B k (q)) < 1 2 + α • (q -p) √ k - 1 2 P (B k (p) = B k (q)) ,
which concludes the proof of Lemma 12.

A.3 Proof of Claim 1

The goal of this section is to prove Claim 1, whose statement can be found in Section 3.2. For this purpose, the key observation is that the derivative, w.r.t. x, of P (B k (x) > B k (p)) in the neighborhood of p is relatively high. The following claim formalizes this idea.

Claim 11. There exists a constant β > 0 such that for every k large enough, and every p, x ∈ [1/3, 2/3]

satisfying p ≤ x ≤ p + 1/ √ k, d dx P (B k (x) > B k (p)) ≥ β • √ k.
Proof. Let h > 0. We will proceed by using a coupling argument. Let X i , i ∈ {1, . . . , k}, be i.i.d. random variables uniformly distributed over the interval [0

, 1]. Let Y 1 = |{i s.t. X i ≤ x}| and Y 2 = |{i s.t. X i ≤ x + h}|. By construction, Y 1 ∼ B k (x) and Y 2 ∼ B k (x + h). Next, let H = |{i s.t. x < X i ≤ x + h}|. By construction, Y 2 = Y 1 + H ≥ Y 1 . Let Z ∼ B k (
p) be a binomially distributed random variable, independent from Y 1 and Y 2 . Now, we have:

P (B k (x + h) > B k (p)) -P (B k (x) > B k (p)) = P (Y 2 > Z) -P (Y 1 > Z) (by definition of Y 1 , Y 2 and Z) = P Y 1 ≤ Z ∩ Y 2 > Z (because Y 1 > Z ⇒ Y 2 > Z) = k j=0 P (Z = j) • P Y 1 ≤ j ∩ Y 2 > j .
Let J = {j ∈ N s.t. kp ≤ j ≤ kp + √ k}. We can rewrite the last equation as

P (B k (x + h) > B k (p)) -P (B k (x) > B k (p)) ≥ j∈J P (Z = j) • P Y 1 ≤ j ∩ Y 2 > j . (18)
The following result is a well-known fact.

Observation 2. There exists a constant β > 0 such that for every k large enough, every p ∈ [1/3, 2/3], and every i satisfying |i -kp| ≤ √ k, we have

P (B k (p) = i) ≥ β √ k . Proof.
By the De Moivre-Laplace theorem, for any i ∈ {0, . . . , k},

P (B k (p) = i) = k i p i (1 -p) k-i ≈ 1 2kp(1 -p) exp - (i -kp) 2 2kp(1 -p) , (19)
where we used ≈ in the sense that the ratio between the left-hand side and the right-hand side tends to 1 as k tends to infinity. Since |i -

kp| ≤ √ k, 1 2kp(1 -p) exp - (i -kp) 2 2kp(1 -p) ≥ 1 2kp(1 -p) exp - 1 2p(1 -p) := f (p) √ k .
By Eq. ( 19), we can conclude the proof of Observation 2 for k large enough by taking, e.g.,

β = 1 2 • min p∈[1/3,2/3] f (p).
For j ∈ J, by Observation 2, P (Z = j) ≥ β/ √ k, for some constant β > 0. Moreover,

P Y 1 ≤ j ∩ Y 2 > j ≥ P Y 1 = j ∩ Y 2 > j = P Y 1 = j ∩ H ≥ 1 (because Y 2 = Y 1 + H) = P (Y 1 = j) • P (H ≥ 1 | Y 1 = j) .
By the assumption in the lemma, p ≤ x ≤ p + 1/ √ k, and so kp ≤ kx ≤ kp + √ k. Therefore, for j ∈ J, |j -kx| ≤ √ k, and by Observation 2, we get that P (Y 1 = j) ≥ β/ √ k. Hence, we can rewrite Eq. (18) as

P (B k (x + h) > B k (p)) -P (B k (x) > B k (p)) ≥ β 2 k j∈J P (H ≥ 1 | Y 1 = j) . (20)
Now, let us find a lower bound on P

(H ≥ 1 | Y 1 = j), for j ∈ J. Note that, by definition, Y 1 = j if and only if |{i s.t. X i > x}| = k -j. Since X i , 1 ≤ i ≤ k, is uniformly distributed over [0, 1], P (x < X i ≤ x + h | X i > x) = h 1 -x .
Therefore, for every j ∈ J

P (H = 0 | Y 1 = j) = 1 - h 1 -x k-j ≤ 1 - h 1 -x k-kp- √ k . This implies that j∈J P (H ≥ 1 | Y 1 = j) ≥ √ k • 1 -1 - h 1 -x k-kp- √ k . We have lim h→0 1 h • j∈J P (H ≥ 1 | Y 1 = j) ≥ lim h→0 √ k h • 1 -1 - h 1 -x k-kp- √ k = √ k k -kp - √ k 1 -x .
Eventually, we get from Eq. ( 20)

d dx P (B k (x) > B k (p)) ≥ β 2 (1 -p) 1 -x • √ k + o k→∞ √ k .
We can conclude the proof of Claim 11 for k large enough by taking, e.g., β = β 2 (1-p) 2(1-x) . Now, we are ready to write the proof of Claim 1.

Proof of Claim 1. We can rewrite Eq. ( 7) as

g(x, y) = y - 1 n P (B (y) ≥ B (x)) + (1 -y) • P (B (y) > B (x)) + 1 n .
Hence,

d dy g(x, y) = P (B (y) ≥ B (x)) -P (B (y) > B (x)) + y - 1 n • d dy P (B (y) ≥ B (x)) + (1 -y) • d dy P (B (y) > B (x)) . ( 21
)
The first term in Eq. ( 21) is equal to P (B (y) = B (x)), which is positive. Moreover, P (B (y) ≥ B (x)) is obviously increasing in y, so the second term is also non-negative. By Claim 11, the third term in Eq. ( 21) satisfies

(1 -y) • d dy P (B (y) > B (x)) ≥ (1 -y) • β • √ ≥ β 4 • √ ,
where the last inequality comes from the fact that x ∈ [1/3, 2/3] and y ∈

[x, x + 1/ √ ] ⊆ [1/4, 3/4]. For large enough, this implies that d dy g(x, y) ≥ β 4 • √ > 1,
which concludes the proof of Claim 1.

B Basic Observations regarding Algorithm FET B.1 Proof of Observation 1

Let I be the set of agents (including the source). Let I 1 t ⊂ I be the set of all non-source agents with opinion 1 at round t. Recall that we condition on x t = x t and x t+1 = x t+1 (although we avoid writing this conditioning). In addition, the proof will proceed by conditioning on I 1 t+1 = I 1 t+1 . Since we shall show that the statements are true for every I 1 t+1 , the lemma will hold without this latter conditioning. By definition of the protocol, and because it operates under the PU LL model, count (i) and count (i) are obtained by sampling agents uniformly at random in the population (with replacement) and counting how many have opinion 1. Therefore, conditioning on (x t , x t+1 ) and I 1 t+1 , (i) variables (count t+1 (i) ) i∈I and (count t (i) ) i∈I are mutually independent, thus variables (Y (i) t+2 ) i∈I are mutually independent. (ii) for every i ∈ I, count t+1 (i) ∼ B (x t+1 ), and count t (i) ∼ B (x t ), so we can write for every non-source agent

i ∈ I 1 t+1 , P Y (i) t+2 = 1 = P (B (x t+1 ) ≥ B (x t )) ,
and for every non-source agent i /

∈ I 1 t+1 , P Y (i) t+2 = 1 = P (B (x t+1 ) > B (x t )) .
Let p = P (B (x t+1 ) ≥ B (x t )) and q = P (B (x t+1 ) > B (x t )). By Observation 1,

E(x t+2 ) = E 1 n n i=1 X i = x t+1 • p + (1 -x t+1 ) • q + 1 n (1 -p) .
By assumption on E(x t+2 ), this implies that

x t+1 • p + (1 -x t+1 ) • q ∈ 1 3 - 1 n , 2 3 .
Moreover, we have that p -q = P (B (x t+1 = B (x t )) which tends to 0 as n tends to infinity, i.e., p and q are arbitrarily close. Hence, for n large enough, the last equation implies that p ∈ [1/4, 3/4] and q ∈

[1/4, 3/4]. Let Y p = n•xt+1 i=2 X i and Y q = n i=n•xt+1+1 X i .
These two variables are binomially distributed, and since p, q ∈ [1/4, 3/4], there is a constant probability that Y p ≥ E(Y p ), and there is a constant probability that Y q ≥ E(Y q ) as well. Without loss of generality, we assume that x t+1 ≥ 1/2 and focus on Y p (if x t+1 < 1/2, then we could consider Y q instead). Let m = n • x t+1 -1 be the number of samples of Y p . In this case, m ≥ n/2-1 tends to +∞ as n tends to +∞. Let σ p = p(1 -p). By the central limit theorem (Theorem 4), the random variable

√ m σ p 1 m Y p -p = Y p -E(Y p ) σ p √ m converges in distribution to N (0, 1). Moreover, Var(Y p ) = mσ 2 p = (n • x t+1 -1)p(1 -p) ≥ (n/2 -1)p(1 -p) ≥ np(1 -p)/3
, so for any > 0 and n large enough,

P Y p ≥ E (Y p ) + √ n = P Y p -E (Y p ) σ p √ m ≥ √ n σ p √ m ≥ P Y p -E (Y p ) σ p √ m ≥ 3 p(1 -p) ≥ 1 -Φ 3 p(1 -p) -.
For small enough, and because p is bounded, this probability is bounded away from zero. This concludes the proof of Lemma 16 (the other inequality can be obtained symmetrically).

We can use the previous result to show that the Markov process (x t , x t+1 ) is sufficiently noisy so that it is never too likely to be at any given point (x, y).

Lemma 17. There is a constant c 1 = c 1 (c) > 0 (recall that the sample size is = c • log n), such that for any a ∈ [1/2 -4δ, 1/2 + 4δ], and any round t s.t. (x t , x t+1 ) ∈ Yellow , we have

P |x t+2 -a| > 1 √ n > c 1 .
Proof. Follows directly from Lemma 16.

C Analyzing Domains

C.1 Green area

Proof of Lemma 1. Let us prove the first part and assume (x t , x t+1 ) ∈ Green 1 (the proof of the second part is analogous). By Eq. ( 22) in Remark 2, we have for every agent i

P Y (t+2) i = 0 ≤ P (B (x t+1 ) ≤ B (x t )) .
By Lemma 13, we have

P (B (x t+1 ) ≤ B (x t )) ≤ exp - 1 2 (x t+1 -x t ) 2 ≤ exp - 1 2 δ 2 = exp - cδ 2 2 log n .
Then, by the union bound,

P   i∈I\{source} Y (t+2) i = 0   ≤ (n -1) • exp - cδ 2 2 log n ,
which tends to 0 as n goes to +∞, provided that c > 2/δ 2 .

C.2 Purple area

Proof of Lemma 2. Let us prove the first part and assume (x t , x t+1 ) ∈ Purple 1 (the proof of the second part is analogous). By Eq. ( 23) in Remark 2, E (x t+2 ) ≥ P (B (x t+1 ) > B (x t )) -1 n .

Since (x t , x t+1 ) ∈ Purple 1 , and since in this area x t+1 is at least a factor (1 -λ n ) greater than x t , we have

P (B (x t+1 ) > B (x t )) ≥ P (B ((1 -λ n )x t ) > B (x t )) . Let σ = x t (1 -x t ) + (1 -λ n )x t (1 -(1 -λ n )x t ) > x t (1 -x t ) > x t 2 , (25)
where the last inequality is by the fact that x t < 1/2 which follows from the definition of Purple 1 . By Lemma 15,

P (B ((1 -λ n )x t ) > B (x t )) > 1 -Φ √ λ n x t σ - C σ √ .
We have (Eq. ( 25) and definition of Purple 1 )

σ > x t 2 > 1 2 log n so C σ √ < √ 2C √ c .
If c is large enough (specifically, if c > 32C 2 /δ 2 ), we obtain

P (B ((1 -λ n )x t ) > B (x t )) > 1 -Φ √ λ n x t σ - δ 4 .
We have

0 ≤ √ λ n x t σ ≤ √ λ n √ 2x t ≤ √ λ n = √ c log δ n -→ n→+∞ 0.
where the second inequality is by Eq. ( 25), and the third is because x t < 1/2. So, for n large enough

1 -Φ √ λ n σ - δ 4 > 1 -Φ(0) - δ 2 = 1 -δ 2 .
Overall, we have proved that if n is large enough, then E (x t+2 ) > (1 -δ)/2. By Observation 1, we can apply Chernoff's inequality (Theorem 2) to get that x t+2 > 1/2 -δ w.h.p. Since by definition of Purple 1 we have 1/2 -δ > x t+1 + δ, we obtain x t+2 > x t+1 + δ w.h.p., which concludes the proof of the lemma.

C.3 Red area

Proof of Lemma 3. Without loss of generality, we assume that t 0 = 0. We assume that (x 0 , x 1 ) ∈ Red 1 (the proof in the case that (x 0 , x 1 ) ∈ Red 0 is the same). First we note that for every round t, by definition, if (x t , x t+1 ) ∈ Red 1 then x t+1 < (1 -λ n )x t . So, we can prove by induction on t that for every 1 ≤ t ≤ t 1 ,

x t < x 0 (1 -λ n ) t .
In particular, we have that x t1 < x t0 < 1/2 -3δ, and so (x t1 , x t1+1 ) / ∈ Yellow by definition of Yellow. Also by definition, x 0 < 1/2 and x t > 1/ log(n) for every 0 ≤ t ≤ t 1 , hence, we obtain from the last equation that

1 log n < 1 2 (1 -λ n ) t .
Taking the logarithm and rearranging, we get log 1 2 + log(log n) > t • log 1 1 -λ n .

We know that log(1 -λ n ) < -λ n and thus t • log (1/(1 -λ n )) > tλ n . Together with the above equation, this gives t < 1 λ n log 1 2 + log(log n) = o log 1/2+2δ n , which concludes the proof.

C.4 Cyan area

Proof of Claim 4. We note that, since x t < 1/ log(n), the probability that an agent does not see a 1 in round t is

P (B (x t ) = 0) = (1 -x t ) > 1 - 1 log n = exp c log(n) log 1 - 1 log n > e -2c ,
for n large enough. Moreover,

(1 -x t+1 ) < 1 -x t+1 + 1 2 2 x 2 t+1 , so the probability that an agent sees at least a 1 in round t + 1 is

P(B (x t+1 ) ≥ 1) = 1 -(1 -x t+1 ) > x t+1 1 - 1 2 x t+1 > 1 2 x t+1 ,
where the last inequality comes from the assumption that x t+1 ≤ 1/ . Eventually, we can write

P (B (x t+1 ) > B (x t )) ≥ P (B (x t ) = 0) • P (B (x t+1 ) ≥ 1) ≥ c 2 • e -2c • x t+1 log n = Kx t+1 log n.
Hence, by Eq. ( 23) in Remark 2, E (x t+2 ) ≥ Kx t+1 log n -1/n. By Observation 1, we can apply Chernoff's inequality (Theorem 2) to conclude the proof of Claim 4.

Proof of Claim 5. The proof follows along similar lines as the proof of Claim 4. We note that, since x t < 1/ log(n), the probability that an agent does not see a 1 in round t is

P (B (x t ) = 0) = (1 -x t ) > 1 - 1 log n = exp c log n log 1 - 1 log n > e -2c ,
for n large enough. Moreover, the probability that an agent sees at least a 1 in round t + 1 is

P(B (x t+1 ) ≥ 1) = 1 -(1 -x t+1 ) ≥ 1 -1 - 1 > 1 - 1 e .
Claim 12. If (x t , x t+1 ) ∈ A 1 and x t+2 -x t+1 > 2(x t+1 -x t ), then (x t+1 , x t+2 ) ∈ A 1 or (x t+1 , x t+2 ) / ∈ Yellow .

Proof. If (x t+1 , x t+2 ) / ∈ Yellow , the result holds. Otherwise, (x t+1 , x t+2 ) ∈ Yellow and we have to prove that (x t+1 , x t+2 ) satisfies A 1 .(i) and A 1 .(ii). First we prove that (x t+1 , x t+2 ) satisfies A 1 .(i):

x t+2 > x t+1 + 2(x t+1 -x t ) (by assumption in the claim)

≥ x t+1 (because (x t , x t+1 ) ∈ A 1 ⇒ x t+1 ≥ x t )
≥ 1/2. (because (x t , x t+1 ) ∈ A 1 and by A 1 .(i))

Then we prove that (x t+1 , x t+2 ) satisfies A 1 .(ii):

x t+2 -x t+1 > 2(x t+1 -x t ) (by assumption in the claim)

> (x t+1 -x t ) + (x t -1/2) (because (x t , x t+1 ) ∈ A 1 and by A 1 .(ii))

= x t+1 -1/2, which concludes the proof of Claim 12.

Next, we apply Claim 12 to Eq. ( 27) to establish (a). Eventually, x t+2 > x t+1 + 4(x t+1 -x t ) + 1/ √ n implies x t+2 -x t+1 > +2(x t+1 -x t ) so we can use Claim 12, P (x t+1 , x t+2 ) / ∈ Yellow \ A 1 ∩ x t+2 > x t+1 + 4(x t+1 -x t ) + 1/ √ n = P x t+2 > x t+1 + 4(x t+1 -x t ) + 1/ √ n (by Claim 12)

> P x t+2 > E (x t+2 ) + 1/ √ n (by Eq. ( 26))

> c 2 > 0,
where the existence of c 2 is guaranteed by Lemma 16. This establishes (b).

Proof of Lemma 8. Without loss of generality, we assume that (x t , x t+1 ) ∈ A 1 (the same arguments apply to A 0 symmetrically). Let us define event H t0+1 , that the system is either in A 1 or out of Yellow in round t 0 + 1, and that the "gap" (x t0+2 -x t0+1 ) is not too small. Formally,

H t0+1 : (x t0+1 , x t0+2 ) / ∈ Yellow \ A 1 ∩ x t0+2 -x t0+1 > 1/ √ n.
For t > t 0 + 1, we define event H t , that the system is either in A 1 or out of Yellow in round t, and that the gap (x t+1 -x t ) doubles. Formally, H t : (x t , x t+1 ) / ∈ Yellow \ A 1 ∩ x t+1 -x t > 2(x t -x t-1 ).

We start with the following observation, which results directly from the definition of H t for t ≥ t 0 + 1:

t-1 s=t0+1 H s ⇒ (x t -x t-1 ) > 2 (t-t0-2) (x t0+2 -x t0+1 ) ⇒ (x t -x t-1 ) > 2 (t-t0-2) / √ n. ( 28
)
For every t > t 0 + 1,

P H t t-1 s=t0+1
H s > 1 -exp -3n • (x t -x t-1 ) 2 (By Lemma 7)

> 1 -exp -3 4

• 4 (t-t0-1) .

(by Eq. ( 28))

By Lemma 7 (b), (x t0+1 , x t0+2 ) ∈ A 1 and x t0+2 -x t0+1 > 1/ √ n w.p. c 2 > 0. Together with the last equation and using the union bound, we get

P t1 t=t0+1 H t > c 2 • 1 - t1 t=t0+2 exp - 3 4
• 4 (t-t0-1) .

Figure 1 :

 1 Figure 1: (a) Partitioning the state space into domains. The x-axis (resp., y-axis) represents the proportion of agents with opinion 1 in round t (resp., t + 1). The thick dashed line at the frontier between Purple 1 and Red 1 is defined by x t+1 = (1 -λ n )x t . (b) Sketch of the proof of Theorem 1. All transitions are w.p. at least 1 -1/n Ω(1) . The numbers next to the self-loops indicate that the process stays in the corresponding domain for this number of rounds w.p. at least 1 -1/n Ω(1) . The source is assumed to have opinion 1.

Figure 2 :

 2 Figure 2: Partitioning the Yellow domain.

Our framework and proofs can be extended to allow for a constant number of sources, however, in this case it must be guaranteed that all sources agree on which opinion is the correct one. Indeed, as mentioned below, when there are conflicts between sources, the problem cannot be solved efficiently in the passive communication model, even if significantly more agents support one opinion.

Observe that the case k = 1 consists of a slightly weaker version than the bit-dissemination problem because the latter problem requires that after convergence is guaranteed w.h.p., the configuration remains correct for an indefinite time with probability 1.

Note that simulations results may be deceiving in self-stabilizing contexts, since the worst initial conditions for a given protocol are not always evident.

Acknowledgements

The authors would particularly like to thank Pierre Fraigniaud and Ofer Feinerman for helpful and exciting discussions. In addition, we would like to thank Uriel Feige, Uri Zwick, Bernard Haeupler, and Emanuele Natale for preliminary discussions.

* This work has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement No 648032). located at the French-

Appendix

A Probabilistic tools A.1 Some well-known theorems Theorem 2. [Multiplicative Chernoff 's Bound] Let X 1 , . . . , X n be independent binary random variables, let X = n i=1 X i and µ = E(X). Then it holds for all δ > 0 that

and for all 0 < < 1,

Theorem 3. [Hoeffding's bound] Let X 1 , . . . , X n be independent random variables such that for every 1 ≤ i ≤ n, a i ≤ X i ≤ b i almost surely. Let X = n i=1 X i and µ = E(X). Then it holds for all δ > 0 that

Theorem 4. [Central Limit] Let X 1 , . . . , X n be i.i.d. random variables with E(X 1 ) = µ and Var(X 1 ) = σ 2 < +∞. Then as n tends to infinity, the random variables

Let Φ be the cumulative distribution function (c.d.f.) of the standard normal distribution:

Theorem 5. [Berry-Esseen] Let X 1 , . . . , X n be i.i.d. random variables, with E(X 1 ) = 0, Var(X 1 ) = E(X 2 1 ) > 0, and E(|X

where, e.g., C = 0.4748.

A.2 Competition between coins

Consider two coins such that one coin has a greater probability of yielding "heads", and toss them k times each.

A.2.1 Lower bounds on the probability that the best coin wins

In Lemmas 13 and 14 we aim to lower bound the probability that the more likely coin yields more "heads", or in other words, we lower bound the probability that the favorite coin wins. Lemma 13 is particularly effective when the difference between p and q is sufficiently large. Its proof is based on a simple application of Hoeffding's inequality.

Lemma 13. For every p, q ∈ [0, 1] s.t. p < q and every integer k, we have

This establishes Eq. 1. Now, let us define independent binary random variables (X j ) 1≤j≤n , taking values in {0, 1}, as follows;

• X 1 = 1,

• for every j s.t. 1 < j ≤ n • x t+1 , P (X j = 1) = P (B (x t+1 ) ≥ B (x t )),

• for every j s.t. n • x t+1 < j ≤ n, P (X j = 1) = P (B (x t+1 ) > B (x t )).

We assumed the source agent to have opinion 1, so there are nx t -1 non-source agents with opinion 1 and n(1x t ) non-source agents with opinion 0. Therefore, by (i) and (ii) and by construction of the (X j ) 1≤j≤n ,

t+2 is distributed as 1 n n j=1 X j , which establishes the second statement in Observation 1. Computing the expectation (still conditioning on x t , x t+1 ) is straightforward and does not depend on I 1 t+1 :

This establishes Eq. ( 2), and concludes the proof of Observation 1.

Remark 2. From Observation 1, we obtain the following straightforward bounds: for every non-source agent i,

and

Because of the source agent having opinion 1, the left hand side in Eq. ( 23) is loose (specifically, -1/n is not necessary). Nevertheless, we will use this equation in the proofs, because it has a symmetric equivalent (w.r.t. to the center of G, ( 1 2 , 1 2 )) which will allow our statements about x t+2 to hold symmetrically for 1-x t+2 , despite the asymmetry induced by the source.

Remark 3. Eq. (2) in Observation 1 implies the following convenient bounds:

B.2 Affects of noise

When it comes to the central area, Yellow, we will need the following result to break ties.

Lemma 16. There exists a constant β > 0 s.t. for n large enough, and if E(x t+2 ) ∈ [1/3, 2/3], then

Proof. Consider X 1 , . . . , X n from the statement of Observation 1. We have (see the proof of Observation 1)

• for every j s.t. 1 < j ≤ n • x t+1 , P (X j = 1) = P (B (x t+1 ) ≥ B (x t )),

• for every j s.t. n • x t+1 < j ≤ n, P (X j = 1) = P (B (x t+1 ) > B (x t )).

Eventually, we can write

Hence, by Eq. ( 23) in Remark 2, E (x t+2 ) ≥ 2γ -1/n. By Observation 1, we can apply Chernoff's inequality (Theorem 2) to conclude the proof of Claim 5.

Proof of Claim 6. By assumption, x t+1 -x t ≥ γ -1/ log(n), and so by Lemma 13

for n large enough. Hence, by Eq. ( 23) in Remark 2, E (x t+2 ) ≥ 3/4 -1/n. By Observation 1, we can apply Chernoff's inequality (Theorem 2) to conclude the proof of Claim 6.

C.5 Yellow area

Recall the partitioning of the Yellow domain as illustrated in Figure 2. We analyze each of the resulting areas separately.

C.5.1 Area A

Proof of Lemma 7. Without loss of generality, we assume that (x t , x t+1 ) ∈ A 1 (the same arguments apply to A 0 symmetrically). We have, provided that δ is small enough and n is large enough,

(by the definition of A 1 )

Hence,

and by definition of A 1 , (x t+1 -(2x t -1/2)) ≥ 0 and so

By Observation 1, we can apply Chernoff's inequality (Theorem 2). Taking = 2(x t+1 -x t )/(4(x t+1 -x t ) + x t+1 ), we have

(by Eq. ( 26))

(by Eq. ( 26) and definition of ) Since x t and x t+1 are close to 1/2, we have for δ small enough

Now, we show that the event "x t+2 -x t+1 > 2(x t+1 -x t )" suffices for (x t+1 , x t+2 ) to remain in A 1 or leave Yellow .

We have the following very rough upper bounds

Hence, we have proved that for every t 1 > t 0 + 1,

By Eq. ( 28), it implies that for every t 1 > t 0 + 1,

For t 1 large enough (e.g., t 1 = t 0 + log n), this implies that (x t1-1 , x t1 ) / ∈ Yellow , otherwise the gap (x t1x t1-1 ) would be greater than 8δ which is the diameter of Yellow . This concludes the proof of Lemma 8.

C.5.2 Area B: Proof of Lemma 10

Without loss of generality, we assume that (x t , x t+1 ) ∈ B 1 (the same arguments apply to B 0 symmetrically). For any round t, let H t the event that (x t , x t+1 ) ∈ B and (a) of Lemma 9 holds. Let t max = t 0 + ( √ c/c 4 ) • log 3/2 n, and let X be the number of rounds between t 0 and t max for which H t does not happen. Each time (a) in Lemma 9 doesn't hold, (b) of Lemma 9 holds so there is a constant probability to leave B, so

Note that

This, together with Eq. ( 29), implies that either (i) X < (t max -t 0 )/4, or w.h.p. (ii) there is a time t 0 ≤ t ≤ t max such that (x t , x t+1 ) / ∈ B (in which case Lemma 10 holds). Now, consider case (i). Let u t = x t -1/2. By Lemma 17, u t0 > 1/ √ n with constant probability. Therefore, for the price of waiting up to an additional log n rounds, we can assume that u t0 > 1/ √ n w.h.p. In what follows, we condition on that event.

Note now, that whenever (x t , x t+1 ) ∈ B 1 , by definition x t+1 ≥ x t > 1/2 and so (x t+1 , x t+2 ) cannot be in B 0 . This implies that the system must remain in B 1 until it leaves B. Also by definition of B 1 , if (x t , x t+1 ) ∈ B 1 then x t ≤ x t+1 , and so

Moreover, by the fact that we are in case (i), we have that the number of rounds t 0 ≤ t ≤ t max such that H t happens is at least

• log 3/2 n.

Note that at each such round, by definition of H t and (a) in Lemma 9,

Hence, by Eq. ( 30),

When n is large, this quantity is larger than 1, hence (i) is impossible unless (x t , x t+1 ) / ∈ B. This concludes the proof of Lemma 10.

C.5.3 Area C: Proof of Lemma 11

Without loss of generality, we assume that (x t , x t+1 ) ∈ C 1 (the same arguments apply to C 0 symmetrically). By Observation 1, we have

By Lemma 14 (taking λ > 2), this becomes

Case 1. If (x t+1 -x t ) > 1/2 -x t+1 , then Eq. ( 31) implies

so with constant probability x t+2 > 1/2 and thus (x t+1 , x t+2 ) ∈ A 1 or is not in Yellow .

Case 2. Else, if (x t+1 -x t ) ≤ 1/2 -x t+1 , Eq. ( 31) rewrites

Since (x t , x t+1 ) ∈ C 1 , we have x t+1 ≥ x t and 1/2 > x t+1 . Moreover, for large enough, 1 -2 • P (B (x t+1 ) = B (x t )) > 0. Hence, E(x t+2 ) > 1 2 1 2 + x t+1 , so, by Lemma 16, with constant probability x t+2 > (1/2 + x t+1 ) /2, i.e., x t+2 -x t+1 > 1/2 -x t+2 . If so, Case 1 applies and with constant probability, (x t+2 , x t+3 ) ∈ A 1 or is not in Yellow . This concludes the proof of Lemma 11.