Distributed Thresholded Counting with Limited Interaction

Problems in the area of distributed computing have been extensively studied. In this paper, we focus on the Distributed Thresholded Counting problem in the coordinator model. In this problem, we have k sites holding their input and communicating with a central coordinator. The coordinator's task is to determine whether the sum of inputs is larger than a threshold. While the communication complexity of this basic problem has been studied for decades, it is still not well understood. Our work considers the worst-case communication cost for an algorithm that uses limited interaction - i.e. a bounded number of rounds of communication. Algorithms in previous research usually need O(łogłog N) or O(k) rounds. In comparison, in the deterministic case, our algorithm achieves optimal communication complexity in only α(k) rounds, where α(k) denotes the inverse Ackermann function and is nearly constant. We also give a randomized algorithm that balances communication, rounds, and error probability.