Optimal Gossip-Based Aggregate Computation

Details Optimal Gossip-Based Aggregate Computation Optimal Gossip-Based Aggregate Computation

2010-01-19

arxiv.org/abs/1001.3242v1

Computer Science

Data Structures and Algorithms

Scientific paper

We present the first provably almost-optimal gossip-based algorithms for aggregate computation that are both time optimal and message-optimal. Given a $n$-node network, our algorithms guarantee that all the nodes can compute the common aggregates (such as Min, Max, Count, Sum, Average, Rank etc.) of their values in optimal $O(\log n)$ time and using $O(n \log \log n)$ messages. Our result improves on the algorithm of Kempe et al. \cite{kempe} that is time-optimal, but uses $O(n \log n)$ messages as well as on the algorithm of Kashyap et al. \cite{efficient-gossip} that uses $O(n \log \log n)$ messages, but is not time-optimal (takes $O(\log n \log \log n)$ time). Furthermore, we show that our algorithms can be used to improve gossip-based aggregate computation in sparse communication networks, such as in peer-to-peer networks. The main technical ingredient of our algorithm is a technique called {\em distributed random ranking (DRR)} that can be useful in other applications as well. DRR gives an efficient distributed procedure to partition the network into a forest of (disjoint) trees of small size. Our algorithms are non-address oblivious. In contrast, we show a lower bound of $\Omega(n\log n)$ on the message complexity of any address-oblivious algorithm for computing aggregates. This shows that non-address oblivious algorithms are needed to obtain significantly better message complexity. Our lower bound holds regardless of the number of rounds taken or the size of the messages used. Our lower bound is the first non-trivial lower bound for gossip-based aggregate computation and also gives the first formal proof that computing aggregates is strictly harder than rumor spreading in the address-oblivious model.

Affiliated with

Also associated with

No associations

Rating

Optimal Gossip-Based Aggregate Computation 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 Optimal Gossip-Based Aggregate Computation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Gossip-Based Aggregate Computation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-635890