Lp Sampling in Distributed Data Streams with Applications to Adversarial Robustness

In the distributed monitoring model, a data stream over a universe of size $n$ is distributed over $k$ servers, who must continuously provide certain statistics of the overall dataset, while minimizing communication with a central coordinator. In such settings, the ability to efficiently collect a random sample from the global stream is a powerful primitive, enabling a wide array of downstream tasks such as estimating frequency moments, detecting heavy hitters, or performing sparse recovery. Of particular interest is the task of producing a perfect $L_p$ sample, which, given a frequency vector $f \in \mathbb{R}^n$, outputs an index $i$ with probability $\frac{f_i^p}{\|f\|_p^p} + \frac{1}{\mathrm{poly}(n)}$. In this paper, we resolve the problem of perfect $L_p$ sampling for all $p \ge 1$ in the distributed monitoring model. Specifically, our algorithm runs in $k^{p-1} \cdot \mathrm{polylog}(n)$ bits of communication, which is optimal up to polylogarithmic factors.