Fast Averaging, and Applications to MapReduce and Consensus on Graphs

We look at the problem of computing the average (arithmetic mean) of a long vector of n numbers. Mathematically, this problem is simple; requires n – 1 additions and 1 division. However, some saving in the number of computations is possible if the vector exhibits certain regularity. In the extreme case, if all the numbers in the vector are equal to 5 (say), then we can get the exact answer with O(1) computations.

This simple problem of finding the arithmetic mean is interesting in many applications, one of them being MapReduce-type computations. MapReduce is an architecture patented by Google, and is de facto standard for large-scale computations in today’s data centers. In this talk, we present a mathematical abstraction of MapReduce, and investigate it from the following points of view:

1. Can we use a randomized algorithm to provide probabilistic performance guarantees, while speeding-up the overall completion time of a query?
2. What is the effect of “regularity” of the underlying vector on the query completion times?

This idea of approximate mean computation – that is, gaining speed-up while settling for probabilistic performance guarantees – finds applications in a number of other fields including control, robotics, estimation, and so on. We will discuss its applications to consensus on graphs.

Joint work with Devavrat Shah.