Randomization Collapses the Idle-Start Memory Barrier for Anonymous Dynamic Broadcast

We study stabilizing broadcast in anonymous, port-indistinguishable, synchronous, 1-interval-connected dynamic networks. For deterministic idle-start algorithms, prior work establishes a superconstant local-memory lower bound, while the Countdown algorithm uses O(log n) memory. We show that private randomization changes the idle-start picture qualitatively. Our protocol, Bernoulli Reactivation Flooding (BRF), uses exactly two persistent protocol states in the standard broadcast abstraction, one non-silent message symbol, and no knowledge of n. It is Las Vegas: it never stabilizes before every node is informed, stabilizes almost surely, and has finite expected stabilization time. Thus private-coin randomized idle-start stabilizing broadcast admits a one-bit control-memory upper bound, in contrast with the known deterministic superconstant lower bound. For fair-coin BRF against the causal state-adaptive topology adversary defined in the paper, the worst-case expected stabilization time satisfies E[T] ~ c0 2n(n+1)/2, where c0 = productr>=1(1-2⁻ʳ) ≈ 0.288788095. The result concerns stabilizing termination, not termination detection, and does not claim that one bit is the randomized minimum. Preprint v1.0.0. Not peer reviewed.