New Bounds for the Flock-of-Birds Problem

In this paper, we continue a line of work on obtaining succinct population protocols for Presburger-definable predicates. More specifically, we focus on threshold predicates. These are predicates of the form $n\ge d$, where $n$ is a free variable and $d$ is a constant. For every $d$, we establish a 1-aware population protocol for this predicate with ${\log }_{2}d+\min \{e,z\}+O(1)$ states, where $e$ (resp., $z$) is the number of $1$’s (resp., $0$’s) in the binary representation of $d$ (resp., $d - 1$)\mathrm{.}Thisimprovesuponanupperbound$4\log_2 d + O(1)$ due to Blondin et al. We also show that any 1-aware protocol for our problem must have at least ${\log }_2(d)$ states. This improves upon a lower bound ${\log }_{3}d$ due to Blondin et al.