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

We propose a protocol to solve Leader Election within weak communication models such as the beeping model or the stone-age model. Unlike most previous work, our algorithm operates on only six states, does not require unique identifiers, and assumes no prior knowledge of the network's size or topology, i.e., it is uniform. We show that under our protocol, the system converges almost surely to a configuration in which a single node is in a leader state. With high probability, this occurs in fewer than O(D2 log n) rounds, where D is the network diameter. We also show that this can be decreased to O(D log n) when an approximation of D is known. The main drawbacks of our approach are a [EQUATION] overhead in the running time compared to algorithms with stronger requirements, and the fact that nodes are unaware of when a single-leader configuration is reached. Nevertheless, the minimal assumptions and natural appeal of our solution make it particularly well-suited for implementation in the simplest distributed systems, especially biological ones.

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

We study the minority-opinion dynamics over a fully-connected network of n nodes with binary opinions. Upon activation, a node receives a sample of opinions from a limited number of neighbors chosen uniformly at random. Each activated node then adopts the opinion that is least common within the received sample.

International audience

Abstract 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 nagents, 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 $$\mathcal {PULL}$$ 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.

We investigate opinion dynamics in a fully-connected system, consisting of n agents, where one of the opinions, called correct, represents a piece of information to disseminate. One source agent initially holds the correct opinion and remains with this opinion throughout the execution. The goal of the remaining agents is to quickly agree on this correct opinion. At each round, one agent chosen uniformly at random is activated: unless it is the source, the agent pulls the opinions of l random agents and then updates its opinion according to some rule. We consider a restricted setting, in which agents have no memory and they only revise their opinions on the basis of those of the agents they currently sample. This setting encompasses very popular opinion dynamics, such as the voter model and best-of-k majority rules. Qualitatively speaking, we show that lack of memory prevents efficient convergence. Specifically, we prove that any dynamics requires Omega(n^2) expected time, even under a strong version of the model in which activated agents have complete access to the current configuration of the entire system, i.e., the case l=n. Conversely, we prove that the simple voter model (in which l=1) correctly solves the problem, while almost matching the aforementioned lower bound. These results suggest that, in contrast to symmetric consensus problems (that do not involve a notion of correct opinion), fast convergence on the correct opinion using stochastic opinion dynamics may require the use of memory.

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.