A Simple and Robust Protocol for Distributed Counting
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918136837570560 |
|---|---|
| author | Cohen, Edith Shechner, Moshe Stemmer, Uri |
| author_facet | Cohen, Edith Shechner, Moshe Stemmer, Uri |
| contents | We revisit the distributed counting problem, where a server must continuously approximate the total number of events occurring across $k$ sites while minimizing communication. The communication complexity of this problem is known to be $Θ(\frac{k}ε\log N)$ for deterministic protocols. Huang, Yi, and Zhang (2012) showed that randomization can reduce this to $Θ(\frac{\sqrt{k}}ε\log N)$, but their analysis is restricted to the {\em oblivious setting}, where the stream of events is independent of the protocol's outputs.
Xiong, Zhu, and Huang (2023) presented a robust protocol for distributed counting that removes the oblivious assumption. However, their communication complexity is suboptimal by a $polylog(k)$ factor and their protocol is substantially more complex than the oblivious protocol of Huang et al. (2012). This left open a natural question: could it be that the simple protocol of Huang et al. (2012) is already robust?
We resolve this question with two main contributions. First, we show that the protocol of Huang et al. (2012) is itself not robust by constructing an explicit adaptive attack that forces it to lose its accuracy. Second, we present a new, surprisingly simple, robust protocol for distributed counting that achieves the optimal communication complexity of $O(\frac{\sqrt{k}}ε \log N)$. Our protocol is simpler than that of Xiong et al. (2023), perhaps even simpler than that of Huang et al. (2012), and is the first to match the optimal oblivious complexity in the adaptive setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_05870 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Simple and Robust Protocol for Distributed Counting Cohen, Edith Shechner, Moshe Stemmer, Uri Distributed, Parallel, and Cluster Computing Data Structures and Algorithms We revisit the distributed counting problem, where a server must continuously approximate the total number of events occurring across $k$ sites while minimizing communication. The communication complexity of this problem is known to be $Θ(\frac{k}ε\log N)$ for deterministic protocols. Huang, Yi, and Zhang (2012) showed that randomization can reduce this to $Θ(\frac{\sqrt{k}}ε\log N)$, but their analysis is restricted to the {\em oblivious setting}, where the stream of events is independent of the protocol's outputs. Xiong, Zhu, and Huang (2023) presented a robust protocol for distributed counting that removes the oblivious assumption. However, their communication complexity is suboptimal by a $polylog(k)$ factor and their protocol is substantially more complex than the oblivious protocol of Huang et al. (2012). This left open a natural question: could it be that the simple protocol of Huang et al. (2012) is already robust? We resolve this question with two main contributions. First, we show that the protocol of Huang et al. (2012) is itself not robust by constructing an explicit adaptive attack that forces it to lose its accuracy. Second, we present a new, surprisingly simple, robust protocol for distributed counting that achieves the optimal communication complexity of $O(\frac{\sqrt{k}}ε \log N)$. Our protocol is simpler than that of Xiong et al. (2023), perhaps even simpler than that of Huang et al. (2012), and is the first to match the optimal oblivious complexity in the adaptive setting. |
| title | A Simple and Robust Protocol for Distributed Counting |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms |
| url | https://arxiv.org/abs/2509.05870 |