  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. This
lower bound 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.
  Beyond the bit-dissemination problem, our result sheds light on the
convergence time of the "minority" dynamics, the counterpart of the well-known
majority rule, whose chaotic behavior is yet to be fully understood despite the
apparent simplicity of the algorithm.
