Fast Averaging, and Applications to MapReduce and Consensus on Graphs

Опубликовано 17 августа 2016, 1:59

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.