Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks

Details Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks

2011-08-17

arxiv.org/abs/1108.3413v2

Computer Science

Data Structures and Algorithms

19 pages, 1 figure

Scientific paper

We show that randomization can lead to significant improvements for a few fundamental problems in distributed tracking. Our basis is the {\em count-tracking} problem, where there are $k$ players, each holding a counter $n_i$ that gets incremented over time, and the goal is to track an $\eps$-approximation of their sum $n=\sum_i n_i$ continuously at all times, using minimum communication. While the deterministic communication complexity of the problem is $\Theta(k/\eps \cdot \log N)$, where $N$ is the final value of $n$ when the tracking finishes, we show that with randomization, the communication cost can be reduced to $\Theta(\sqrt{k}/\eps \cdot \log N)$. Our algorithm is simple and uses only O(1) space at each player, while the lower bound holds even assuming each player has infinite computing power. Then, we extend our techniques to two related distributed tracking problems: {\em frequency-tracking} and {\em rank-tracking}, and obtain similar improvements over previous deterministic algorithms. Both problems are of central importance in large data monitoring and analysis, and have been extensively studied in the literature.

Affiliated with

Also associated with

No associations

Rating

Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-540053