Randomized algorithms for tracking distributed count, frequencies, and ranks
Randomized algorithms for tracking distributed count, frequencies, and ranks
We show that randomization can lead to significant improvements for a few fundamental problems in distributed tracking. Our basis is the count-tracking problem, where there are k players, each holding a counter ni that gets incremented over time, and the goal is to track an ∑-approximation of their sum n=∑ini …