Adversarially Robust Distributed Count Tracking via Partial Differential
  Privacy
Zhongzheng Xiong Xiaoyi Zhu Zengfeng Huang
We study the distributed tracking model, also known as distributed functional
monitoring. This model involves $k$ sites each receiving a stream of items and
communicating with the central server. The server's task is to track a function
of all items received thus far continuously, with minimum communication cost.
For count tracking, it is known that there is a $\sqrt{k}$ gap in communication
between deterministic and randomized algorithms. However, existing randomized
algorithms assume an "oblivious adversary" who constructs the entire input
streams before the algorithm starts. Here we consider adaptive adversaries who
can choose new items based on previous answers from the algorithm.
Deterministic algorithms are trivially robust to adaptive adversaries, while
randomized ones may not. Therefore, we investigate whether the $\sqrt{k}$
advantage of randomized algorithms is from randomness itself or the oblivious
adversary assumption. We provide an affirmative answer to this question by
giving a robust algorithm with optimal communication. Existing robustification
techniques do not yield optimal bounds due to the inherent challenges of the
distributed nature of the problem. To address this, we extend the differential
privacy framework by introducing "partial differential privacy" and proving a
new generalization theorem. This theorem may have broader applications beyond
robust count tracking, making it of independent interest.