Scholarlink

<p>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 <i>n</i> agents is required to adopt the correct opinion, initially held by a single individual, choosing from two possible opinions. 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 by Becchetti et al. 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&#xa0;<InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\Omega (\sqrt{n \log n})\)</EquationSource> </InlineEquation>. 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. We demonstrate that any memory-less protocol with constant sample size requires at least an almost-linear number of rounds to converge. This result holds even when agents are aware of both the exact value of <i>n</i> and their own opinion, and encompasses various simple existing dynamics designed to achieve consensus. In particular, our result sheds light on the convergence time of the “Minority” dynamics introduced by Becchetti et al., whose chaotic behavior is yet to be fully understood despite its apparent simplicity.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

On the limits of information spread by memory-less agents

  • 期刊论文

  • 发表日期：

    2026年1月7日

查看全文
  • Niccolò D’Archivio,
  • Robin Vacus

摘要

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 individual, choosing from two possible opinions. 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 by Becchetti et al. 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. We demonstrate that any memory-less protocol with constant sample size requires at least an almost-linear number of rounds to converge. This result holds even when agents are aware of both the exact value of n and their own opinion, and encompasses various simple existing dynamics designed to achieve consensus. In particular, our result sheds light on the convergence time of the “Minority” dynamics introduced by Becchetti et al., whose chaotic behavior is yet to be fully understood despite its apparent simplicity.