Dynamic Regular Witnesses for Near-Exact State Complexity of Explicit Binary Consensus 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 phi_t = t mod P. For every n >= 15, we prove 2 + ceil((n - 13)/P) <= S_n(n,P) <= 2 + ceil((n - 1)/P). For even n >= 12, the lower numerator improves to n - 10. We also prove the exact minimum-state saturation threshold S_n(n,P) = 3 iff P >= n - 1 for n >= 4. The full exact formula for arbitrary state budgets is not claimed. This record is a preprint and has not been peer reviewed.