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.

研究了分布式跟踪模型，包括功能性监控、通信成本、适应性对手和鲁棒计数跟踪，提出了一种具有最佳通信的鲁棒算法，并通过引入 “部分差分隐私” 和证明一个新的推广定理来解决分布式问题的挑战。