# Brief Announcement: On the Limits of Information Spread by Memory-less Agents

Niccolò d'Archivio, Robin Vacus

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

## To cite this version:

Niccolò d'Archivio, Robin Vacus. Brief Announcement: On the Limits of Information Spread by Memory-less Agents. PODC 2024: 43rd ACM Symposium on Principles of Distributed Computing, Jun 2024, Nantes (France), France. pp.91 - 94, 10.1145/3662158.3662813. hal-04779986

HAL Id: hal-04779986

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

Submitted on 13 Nov 2024

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published 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_2.png" /></figure>
# Brief Announcement: On the Limits of Information Spread by Memory-less Agents

Niccolò D'Archivio*

COATI, INRIA d'Université Côte d'Azur

Sophia Antipolis, France

niccolo.darchivio@inria.fr

Robin Vacus*

Bocconi Institute for Data Science and Analytics

Milan, Italy

robin.vacus@gmail.com

## ABSTRACT

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

## CCS CONCEPTS

* Theory of computation → Random walks and Markov chains; Distributed algorithms.

## KEYWORDS

Opinion Dynamics, Consensus Protocols, Collective Animal Behavior, Lower Bound

**ACM Reference Format:**

Niccolò D'Archivio and Robin Vacus. 2024. Brief Announcement: On the Limits of Information Spread by Memory-less Agents. In *ACM Symposium on Principles of Distributed Computing (PODC '24), June 17–21, 2024, Nantes, France*. ACM, New York, NY, USA, 4 pages. https://doi.org/10.1145/3662158.3662813

## 1 INTRODUCTION

Exploring the computational power and limits of well-chosen models – ones that are simple enough for analytical tractability, and yet relevant to specific biological scenarios – can lead to insightful conclusion about the functioning of biological distributed systems. In line with this approach, we consider the bit-dissemination problem, introduced in [4] in order to evaluate the possibility to solve two fundamental problems concurrently: reaching agreement efficiently, while ensuring that an information possessed initially by a single individual is propagated to the whole group. In order to fit biological scenarios, the problem features extremely constrained communications. Agents engage in random interactions with just a few individuals at a time, as in the *PULL* model. Furthermore, they can only disclose their current decision and no other information, following an assumption introduced in [10] to model situations in which individuals do not actively communicate [5].

In this paper, we further restrict attention to memory-less entities lacking the ability to perform computations over extended periods of time; or at least not in a sufficiently reliable manner. In particular, this assumption precludes the possibility to maintain clocks and counters, or to estimate the tendency of the dynamics. It is likely to be relevant in several biological ensembles, such as ant colonies [8], slime molds, cells and bacteria [11] or even plants [13]. We acknowledge that it is always hard to rule out the possibility that species make use of memory, especially in the case of social insects. Yet, this modeling choice remains applicable even without presupposing specific cognitive abilities, as many species often stick to simple behavioral rules when attempting to reach a consensus, such as quorum sensing [12] or alignment rules [14].

## 2 DESCRIPTION OF THE PROBLEM

More precisely, we consider a set of *n* agents holding binary opinions in {0, 1}. One of the agents, referred to as the *source*, knows what opinion is “correct” and remains with it at all times. Execution proceeds in discrete rounds. In the *parallel* setting, all non-source agents are activated simultaneously in every round, while in the *sequential* setting, only one non-source agent, selected uniformly at random, is activated. Upon activation, a non-source agent *i* samples *l* other agents’ opinions drawn uniformly at random (with replacement). Then, based only on the sample and on its own opinion, Agent *i* may choose to adopt a new opinion, according to a protocol. Denoting the sample size by *l* (independent from *n*), a protocol $\mathcal{P}$ is defined as a family of functions

$$g_n^{[b]} : \{0, \dots, l\} \mapsto [0, 1].$$

Informally, $g_n^{[b]}(k)$ represents the probability that an agent observing $k$ '1' out of its $l$ samples adopts opinion 1 in the next round,

<footnote>*Both authors contributed equally to this research.</footnote>

<footnote>Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org.</footnote>

<footnote>PODC '24, June 17–21, 2024, Nantes, France</footnote>

<footnote>© 2024 Copyright held by the owner/author(s). Publication rights licensed to ACM.</footnote>

<footnote>ACM ISBN 979-8-4007-0668-4/24/06</footnote>

<footnote>https://doi.org/10.1145/3662158.3662813</footnote>
provided that the total number of agents is $n$, and that this agent has opinion $b$ in the current round. As a consequence of this definition:

* Non-source agents do not know where the opinions that they observe come from. In particular, they do not know if they sampled the source's opinion.

* Non-source agents do not have identifiers, or in other words, all of them must run exactly the same update rule. They are also not aware of the round number.

* However, non-source agents are aware of their current opinion, as well as the exact value of $n$.

* Besides their opinion, non-source agents have no memory, in the sense that their behavior cannot depend on any information from previous rounds different from their current opinion.

Since the agents have no memory and no identifiers, the configuration of the system in round $t \in \mathbb{N}$ can be described simply by a pair $(z, X_t)$, where $z \in \{0, 1\}$ denotes the correct opinion, and $X_t \in \{0, \dots, n\}$ denotes the number of agents with opinion 1. For a given $n \in \mathbb{N}$, and an initial configuration $C = (z, X_0)$, we define the convergence time of protocol $\mathcal{P}$ as the first round for which all agents have adopted the correct opinion and remain with it forever, that is:

$$ \tau_n(\mathcal{P}, C) := \inf\{t \ge 0, \text{ for every } s \ge t, X_s = n \cdot z\}. $$

We say that a protocol $\mathcal{P}$ solves the bit-dissemination problem in time $T(n)$ if for any sequence of initial configurations $\{C_n\}$, $\tau_n(\mathcal{P}, C_n) \le T(n)$ w.h.p.<fnref n="1" />

## 3 PREVIOUS WORKS

To compare protocols across various settings, we express the convergence time in terms of *parallel rounds*: one parallel round corresponds to $n$ activations, which is equivalent to 1 round in the parallel setting, and $n$ rounds in the sequential setting.

The bit-dissemination problem without memory was first studied in [2], in the sequential setting, where nearly matching lower and upper bounds are given. On the one hand, the authors show that no protocol can converge in less than $\Omega(n)$ parallel rounds in expectation, regardless of the sample size. On the other hand, they show that the well-known Voter dynamics achieves consensus in $O(n \log^2 n)$ parallel rounds with high probability. Since the Voter dynamics only needs the sample size to be 1, these results imply that $\ell$ is not a critical parameter in the sequential setting.

Later, the authors of [3] show that the aforementioned lower bound does not hold in the parallel setting. In fact, they show that the minority dynamics converges in $O(\log^2 n)$ parallel rounds w.h.p., as long as the sample size is at least $\Omega(\sqrt{n \log n})$. This finding reveals that the best convergence times achievable in the sequential versus parallel settings differ by an exponential factor. The bit-dissemination problem is all the more interesting to study as it is one of the most natural ones exhibiting this property.

Part of the explanation behind this curious phenomenon is that the stochastic processes involved are of different mathematical natures, in one setting compared to the other. In the sequential setting, the number of agents with opinion 1 may only vary by at

most one unit in every round, since only one agent is activated at a time. Therefore, independently of the protocol being operated, the evolution of the system can always be described by a “birth-death” chain, i.e., a Markov chain whose underlying graph is a path of size $n$. In fact, all proofs in [2] heavily rely on this observation. In contrast, in the parallel setting, the process may jump from any configuration to any other – albeit with extremely small probability.

On the one hand, this characteristic allows for fast convergence. On the other hand, it complicates the analysis of any protocol in the parallel setting, and even more so the task of deriving lower bounds. Following on from these works, we are ultimately interested in the following question:

> Is there a protocol solving the bit-dissemination problem in poly-logarithmic time in the parallel setting, when the sample size is $o(\sqrt{n})$?

As a first step towards an answer, we focus here on the case that the sample size is constant, or in other words, independent from $n$. Beyond analytical tractability, several reasons motivate this assumption. First, many existing opinion dynamics, like Voter and majority dynamics, or Population protocols, operate with a fixed number of samples. In addition, protocols using a sample size that increases with $n$ imply that agents must know the population size, which is often impractical in distributed systems. Finally, real biological scenarios, such as bird flocking or fish schooling, typically involve interactions with only a few nearby entities, rather than the entire group [1, 9].

Others related works. The bit-dissemination problem was also studied under the assumption that agents can use a moderate amount of memory. An efficient protocol is identified in [10], and achieves consensus in $O(\text{polylog } n)$ parallel rounds with high probability. It relies on agents being able to memorize $\log \log n$ bits of information from one round to the next and requires a sample size logarithmic in $n$. Other candidates are mentioned in [4] but are not analysed. The authors of [7] show that the problem can be solved in the context of population protocols with a memory of only constant size. Importantly however, population protocols do not fit the framework of passive communications. Specifically, interaction rules in this model depend on the exact states of the agents, and not just on their binary opinion.

## 4 OUR RESULTS

We show that, when the sample size is bounded, any protocol that does not have access to memory needs almost-linear time to solve the bit-dissemination problem.

**THEOREM 1.** Assume that the sample size $\ell$ is constant. If there exists a function $T: \mathbb{N} \to \mathbb{N}$ and a protocol $\mathcal{P}$ solving the bit-dissemination problem in time $T(n)$, then for every $\varepsilon > 0$, $T(n) = \Omega(n^{1-\varepsilon})$.

To the best of our knowledge, this is the first non-trivial lower-bound for this problem in the parallel setting. Note that it also holds when agents can choose from more than 2 opinions, provided that they may not adopt an opinion that they have never seen or

<footnote n="1">¹Given a sequence of events $\{A_n\}_{n \in \mathbb{N}}$, we say that "$A_n$ happens with high probability (w.h.p.)" if $\mathbb{P}(A_n) = 1 - 1/n^{\Omega(1)}$.</footnote>
adopted<fnref n="2" />. Indeed, in that case, a lower bound could be obtained by assuming a binary initial configuration and reducing to Theorem 1.

In terms of the dependency on $n$, we show that our lower bound is nearly tight (up to a sub-polynomial factor) by adapting a well-known result to our setting.

**THEOREM 2.** *The Voter dynamics solves the bit-dissemination problem in $O(n \log n)$ rounds w.h.p.*

However, when it comes to parameter $\ell$, a gap remains between our lower bound and the upper bound in [3], where it is shown that the minority dynamics solves the problem in $O(\log^2 n)$ rounds w.h.p. when $\ell$ is at least $\Omega(\sqrt{n \log n})$.

On the one hand, we believe that our techniques cannot be used to extend the lower bound to a higher value of $\ell$. Indeed, if $\ell = \Omega(\log n)$, it is already possible for a protocol to converge in just one round w.h.p. from configurations that are arbitrarily far away from the consensus. This observation destroys any hope of restricting the analysis to a small interval of the configuration space. In contrast, this phenomenon does not happen w.h.p. in our setting.

On the other hand, to this day, there is no good reason to think that $\Theta(\sqrt{n \log n})$ is the smallest value of $\ell$ allowing for an efficient protocol (such as the minority dynamics). As previously mentioned, the authors of [3] do not provide any argument supporting this claim, and simulations suggest that its convergence might be fast even when the sample size is qualitatively small (although in general, numerical results shed little light on asymptotic behaviours). Yet, rigorously analysing its convergence time seems highly challenging, and is left for future work.

# 5 SKETCH OF THE PROOF

Among other classical arguments, the proof of Theorem 1 relies on an original idea which can be summarized as follows (some technical details are omitted, see [6] for the full version). For every protocol $\mathcal{P}$, we define the polynomial

$$F_n(p) := -p + \sum_{k=0}^{\ell} \binom{\ell}{k} p^k (1-p)^{\ell-k} \left( p g_n^{[1]}(k) + (1-p) g_n^{[0]}(k) \right). \quad (1)$$

The sum in Eq. (1) corresponds to the probability that a non-source agent, taken uniformly at random, adopts opinion 1, given that the current proportion of agents with opinion 1 is $p$. Informally, $F_n(p)$ measures the “bias” of $\mathcal{P}$ towards opinion 1. In fact, denoting by $X_t$ the number of agents with opinion 1 in round $t$, it is possible to show that [6, Proposition 5]:

$$E\left(\frac{X_{t+1}}{n} \mid X_t = x_t\right) \approx \frac{x_t}{n} + F_n\left(\frac{x_t}{n}\right). \quad (2)$$

For the sake of simplicity, we will assume here that $g_n := g$ and $F_n := F$ do not depend on $n$ (i.e., agents are not aware of the population size).

If $F$ is equal to 0 – that is, if the protocol is equivalent to the Voter dynamics – then the process $\{X_t\}_{t \in \mathbb{N}}$ is more or less a martingale, and we can use Azuma-Hoeffding’s inequality to obtain a lower bound on the convergence time [6, Lemma 11].

Otherwise, the fact that $\ell$ is constant w.r.t. $n$ directly implies that $F$, as a polynomial in $p$, has a constant degree, and therefore a constant number of roots within the interval $[0, 1]$. By definition, 0 and 1 are both roots of $F$. Let $r_0$ be the largest root of $F$ which is strictly smaller than 1:

$$r_0 := \max\{p < 1, F(p) = 0\}.$$

By definition, $F$ has a constant sign on $[r_0, 1]$. If $F$ is negative on this interval, i.e., $\mathcal{P}$ tends to make the proportion of 1-opinions decrease, we show that the process will be slow to reach consensus every time the correct opinion is 1. Conversely, if it is positive, we show that fast convergence fails whenever the correct opinion is 0. In both cases, the proof utilizes the two following ingredients:

(1) It is extremely unlikely that the process “jumps” over the interval in a single step. This is due to the fact that the sample size $\ell = O(1)$ – see, e.g., [6, Proposition 4]. This is illustrated by (a) in Figure 1, in the case that $F$ is negative on $[r_0, 1]$.

(2) Over the interval $[r_0, 1]$, the process is dominated by a martingale. By Azuma-Hoeffding’s inequality, and since $[r_0, 1]$ is of constant length, the martingale needs almost-linear time to escape, which we can use to lower bound the convergence time. This corresponds to (b) in Figure 1.

These two arguments are abstracted into a general result on Markov chain [6, Theorem 6], which is then used as a black box in the proof of Theorem 1.

<figure><img src="image_3.png" /><figcaption>Figure 1: Sketch of the proof.</figcaption></figure>

To relax the assumption that $\{g_n\}$ and $\{F_n\}$ do not depend on $n$, we consider the roots of $F_n$ inside the interval $[0, 1]$:

$$\vec{r}_n := (r_n^{(0)}, \dots, r_n^{(k)}) \in [0, 1]^k,$$

where $k \le \ell+1$. Since $[0, 1]^k$ is compact, we can extract a converging sub-sequence of $\{\vec{r}_n\}_{n \in \mathbb{N}}$. Finally, we are able to adapt the proof presented here to the limit $\vec{r}_\infty$ of this sub-sequence.

# ACKNOWLEDGMENTS

We would like to thank Andrea Clementi for his feedback, Amos Korman for helpful comments and originally coming up with the minority dynamics, and Luca Trevisan for preliminary discussions. This work has been supported by the AID INRIA-DGA project n°2023000872 "BioSwarm".

<footnote n="2">²This is an arguably natural assumption, without which increasing the number of opinions directly increases the amount of information communicated at each interaction.</footnote>
REFERENCES

[1] M. Ballerini, N. Cabibbo, R. Candelier, A. Cavagna, E. Cisbani, I. Giardina, V. Lecomte, A. Orlandi, G. Parisi, A. Procaccini, M. Viale, and V. Zdravkovic. 2008. Interaction Ruling Animal Collective Behavior Depends on Topological Rather than Metric Distance: Evidence from a Field Study. *Proceedings of the National Academy of Sciences of the United States of America* 105, 4 (Jan. 2008), 1232–1237.
https://doi.org/10.1073/pnas.0711437105

[2] Luca Becchetti, Andrea Clementi, Amos Korman, Francesco Pasquale, Luca Trevisan, and Robin Vacus. 2023. On the Role of Memory in Robust Opinion Dynamics. In *Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI-23*, Edith Elkind (Ed.), Vol. 1. International Joint Conferences on Artificial Intelligence Organization, Macao, 29–37.
https://doi.org/10.24963/ijcai.2023/4

[3] Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan, Robin Vacus, and Isabella Ziccardi. 2024. The Minority Dynamics and the Power of Synchronicity. In *Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*. Society for Industrial and Applied Mathematics, Alexandria, Virginia, U.S., 4155–4176. https://doi.org/10.1137/1.9781611977912.144

[4] Lucas Boczkowski, Amos Korman, and Emanuele Natale. 2017. Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 Bits. In *Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*. Society for Industrial and Applied Mathematics, 2540–2559.
https://doi.org/10.1137/1.978161197482168

[5] Étienne Danchin, Luc-Alain Giraldeau, Thomas J. Valone, and Richard H. Wagner. 2004. Public Information: From Nosy Neighbors to Cultural Evolution. *Science* 305, 5683 (July 2004), 487–491. https://doi.org/10.1126/science.1098254

[6] Niccolò D'Archivio and Robin Vacus. 2024. On the Limits of Information Spread by Memory-less Agents. arXiv:2402.11553 [cs.MA]

[7] Bartłomiej Dudek and Adrian Kosowski. 2018. Universal Protocols for Information Dissemination Using Emergent Signals. In *Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018)*. Association for Computing Machinery, New York, NY, USA, 87–99. https://doi.org/10.1145/3188745.3188818

[8] Ofer Feinerman and Amos Korman. 2017. Individual versus Collective Cognition in Social Insects. *Journal of Experimental Biology* 220, 1 (Jan. 2017), 73–82. https://doi.org/10.1242/jeb.143891

[9] Yael Katz, Kolbjørn Tunstrøm, Christos C. Ioannou, Cristián Huepe, and Iain D. Couzin. 2011. Inferring the Structure and Dynamics of Interactions in Schooling Fish. *Proceedings of the National Academy of Sciences* 108, 46 (Nov. 2011), 18720–18725. https://doi.org/10.1073/pnas.1107583108

[10] Amos Korman and Robin Vacus. 2022. Early Adapting to Trends: Self-Stabilizing Information Spread Using Passive Communication. In *Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing (PODC'22)*. Association for Computing Machinery, New York, NY, USA, 235–245. https://doi.org/10.1145/3519270.3538415

[11] Melissa B. Miller and Bonnie L. Bassler. 2001. Quorum Sensing in Bacteria. *Annual Review of Microbiology* 55, 1 (2001), 165–199. https://doi.org/10.1146/annurev.micro.55.1.165

[12] David J. T. Sumpter, Jens Krause, Richard James, Iain D. Couzin, and Ashley J. W. Ward. 2008. Consensus Decision Making by Fish. *Current Biology* 18, 22 (Nov. 2008), 1773–1777. https://doi.org/10.1016/j.cub.2008.09.064

[13] Anthony Trewavas. 2002. Plant Intelligence: Mindless Mastery. *Nature* 415, 6874 (Feb. 2002), 841–841. https://doi.org/10.1038/415841a

[14] Tamás Vicsek and Anna Zafeiris. 2012. Collective Motion. *Physics Reports* 517, 3 (Aug. 2012), 71–140. https://doi.org/10.1016/j.physrep.2012.03.004