2021/10/24 by Kozachinskiy, Alexander
#Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.2110.12452
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≥ 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 log2 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). This improves upon an upper bound 4log2 d + O(1) due to Blondin et al. We also show that any 1-aware protocol for our problem must have at least log2(d) states. This improves upon a lower bound log3 d due to Blondin et al.