Fast and Robust Information Spreading in the Noisy 𝒫 ​ 𝒰 ​ ℒ ​ ℒ \mathcal{PULL} Model

Niccolò D’Archivio, Amos Korman, Emanuele Natale, Robin Vacus · 2024

Read Fast and Robust Information Spreading in the Noisy 𝒫 ​ 𝒰 ​ ℒ ​ ℒ \mathcal{PULL} Model by Niccolò D’Archivio, Amos Korman, Emanuele Natale, Robin Vacus (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-02560.txt.

Description

Abstract Efficient information spreading in stochastic multi agent systems is a core challenge when communication is noisy, bandwidth limited, and agents lack global coordination. Yet biological systems, including ant colonies and fish schools, routinely overcome these constraints. A small number of informed individuals can reliably guide large, uncoordinated populations using minimal, noisy signals.

Catalog record

CREATORNiccolò D’Archivio, Amos Korman, Emanuele Natale, Robin Vacus
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE122 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2411-02560

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Fast and Robust Information Spreading in the Noisy 𝒫 ​ 𝒰 ​ ℒ ​ ℒ \mathcal{PULL} Model Niccolò D’Archivio, Amos Korman, Emanuele Natale, Robin Vacus Abstract Efficient information spreading in stochastic multi agent systems is a core challenge when communication is noisy, bandwidth limited, and agents lack global coordination. Yet biological systems, including ant colonies and fish schools, routinely overcome these constraints. A small number of informed individuals can reliably guide large, uncoordinated populations using minimal, noisy signals. Motivated by these observations, we study how reliable information dissemination can be achieved in such bio inspired settings. A population of n n agents, each with a binary preference, includes a designated subset of source agents, and the goal is to converge to the majority preference among the sources. In the noisy 𝒫 ​ 𝒰 ​ ℒ ​ ℒ ​ ( h ) \mathcal{PULL}(h) model, each agent observes noisy messages from h h randomly sampled peers in every round. Prior work shows that convergence requires Ω ⁡ ( n / h ) \Omega(n/h) rounds even under favorable conditions. We ask how far we can push simplicity, with no synchronization at the start time and minimal message size, without compromising convergence speed. We present a quasi self-stabilizing protocol using only 2-bit messages that converges from arbitrary initial states despite severe noise and initial asynchrony. It achieves optimal convergence time O ⁡ ( ( n / h ) ​ log ⁡ n ) O((n/h)\log n) with high probability, and in particular O ⁡ ( log ⁡ n ) O(\log n) time in the snapshot regime h = Θ ⁡ ( n ) h=\Theta(n) . A key subroutine is an even simpler 1-bit protocol assuming simultaneous start, based on a natural two phase listen then amplify mechanism. Together, our results show that simple, biologically inspired protocols can achieve optimal and robust information dissemination even in highly unreliable and uncoordinated systems. Keywords. Information Spreading; Noisy Communication; Zealot Consensus; Self-Stabilization; Cooperative Transport; Crazy Ants; Natural Algorithms. 1 Introduction Designing artificial multi-agent systems is challenging when agents must achieve distributed coordination and consensus under local, asynchronous, and noisy communication constraints. Yet, nature offers inspiration: for example, in ant colonies and fish schools, a few informed individuals can lead an entire uncoordinated group using minimal, noisy signals [ 31 , 42 , 32 , 19 ] . Further details on the biological motivation are provided in the Section 12 . This motivates the study of simple, fault-tolerant algorithms for information spreading in settings with unreliable communication and severe bandwidth limits [ 29 , 14 ] . In the spirit of opinion dynamics , designed to model information propagation and consensus formation in multi-agent systems [ 9 , 20 , 21 , 38 , 30 ] , we consider a population of n agents, each holding a binary opinion ( 0 or 1 ). We assume that a subset of agents, called sources , hold initial preferences. We define the correct opinion as the one supported by the majority of sources. The goal is for the entire population to converge on this correct opinion. This formulation generalizes the standard rumor spreading problem (where sources agree on the correct opinion) to include majority consensus (where all agents are sources). We refer to this broader problem as majority rumor spreading for simplicity. Noise in communication To capture random, unpredictable, and noisy communication, we adopt the noisy PULL( h ) model [ 26 , 29 , 17 , 14 ] . In this model, time proceeds in synchronous rounds, and in each round every agent pulls messages from h randomly chosen peers (neighbors) in the network. Each message is drawn from a fixed alphabet \Sigma . Crucially, the channel is noisy: the received symbol may be corrupted randomly. We assume the noise is biased, i.e. it retains the original message with probability slightly greater than 1/|\Sigma| . Despite this slight reliability, without further algorithmic design the information can easily get lost in the noise. This raises a central question: How can the agents quickly and reliably agree on the correct opinion under such extreme noise, using small |\Sigma| ? One difficulty that arises in the noisy PULL( h ) model is that sources cannot safely signal the fact that they are sources using a designated bit, since this bit itself would be noisy. As a consequence, the majority of messages perceived as originating from a source would in fact be artifacts of noise, rather than genuine source messages. Conversely, without the ability to identify sources, non-sources must somehow extract information from multiple samples, most of which are unreliable. Notably, prior work established a fundamental time barrier: even under relatively favorable conditions, any protocol requires on the order of \Omega(n/h) rounds to spread the information with constant success probability [ 14 ] . In other words, if each agent communicates with only a constant number of others per round ( h=O(1) ), it takes linear time \Omega(n) in the population size to reliably propagate a rumor; larger h may potentially linearly speed this up, but no algorithm can circumvent this bound. Our goal is to approach this optimal convergence speed using the smallest alphabet \Sigma , and to do so under minimal assumptions about coordination among agents. Quasi self-stabilization To model the lack of global coordination, we consider a variant of the self-stabilization framework [ 1 ] . A self-stabilizing protocol ensures convergence from any initial state—potentially set by an adversary—without assuming synchronized clocks or a common start time. However, the traditional model assumes complete adversarial control over all initial internal states, which may be unnecessarily strong for modeling real systems. We therefore introduce a relaxed version – quasi self-stabilization – that allows reliable access to certain information, such as the size of the population n , the distribution of the noise, or whether an agent is a source (see more details in Section 1.2 ). When agents start the execution at different times, several technical challenges arise. First, without synchronous counters, it is difficult to implement phase-based strategies. Early transmissions from sources may occur before some agents have even begun executing the protocol, rendering those messages effectively lost. Moreover, if agents reset their state upon “wake-up,” they risk disrupting ongoing consensus dynamics, since different subsets of the population may be at different logical times. This asynchrony complicates both correctness and efficiency guarantees: protocols must ensure convergence despite arbitrary misalignment of agents’ clocks, while simultaneously tolerating noisy communication. Previous studies have explored self-stabilizing rumor spreading in the \mathcal{PULL} model, focusing on minimizing message size [ 13 , 7 , 37 , 8 ] , but without addressing noisy communication. Conversely, Boczkowski et al. [ 14 ] analyzed the noisy \mathcal{PULL}(h) model and showed that with any constant-size alphabet, convergence still requires \tilde{\Omega}(n/h) rounds, even assuming synchronized start. In this work, we address both dimensions of unreliability: noisy messages and arbitrary, uncoordinated initial configurations. Main contribution We answer the above challenge by designing protocols for noisy majority rumor spreading, emphasizing a tiny message alphabet and robustness to communication noise and/or arbitrary start conditions. Our main result is a quasi self-stabilizing majority rumor spreading algorithm, called SSF, that uses a 4-symbol alphabet (only 2 bits of

Read the complete text