Two-Orbit Packing for Exact State Complexity of Explicit Binary Consensus in Anonymous Dynamic Networks with Periodic Time

Abstract

We study deterministic binary consensus with explicit termination in anonymous synchronous 1-interval-connected dynamic networks under one-bit broadcast-counting communication with a free globally aligned phase φ_t = t mod P. For known dynamic diameter D and unknown network size, we prove the exact persistent-state complexity S_D(D,P) = ceil(D/P) + 2, equivalently P(S - 2) >= D. The three-state threshold is exactly P >= D. The same two-orbit packing argument strengthens the known-size lower bound to 2 + ceil(floor(n/2)/P). This record is a preprint and has not been peer reviewed.