Time Complexity analysis for Map-Reduce model I am trying to redesign my algorithm to run on Hadoop/MapReduce paradigm. I was wondering if there is any holistic approach for measuring time complexity for algorithms on Big Data platforms. 

As a simple example, taking average of n (= 1 billion) numbers can be done on O(n) + C (assuming division to be constant time operation). If i break this massively parallelizable algorithm for Map Reduce, by dividing data over k nodes, my time complexity would simply become O(n/k) + C + C'. Here, C' can be assumed as the startup job planning time overhead. Note that there was no shuffling involved, and reducer's job was nearly trivial. 

I am interested in a more complete analysis of algorithm with iterative loops over data and involve heavy shuffling and reducer operations. I want to incorporate, if possible, the I/O operations and network transfers of data.
S. Arora, B. Barak, Computational Complexity Modern Approach, Chapter 13 is a good introductory resource to this topic: 


  Communication complexity concerns the following scenario. There are two players with unlimited computational power, each of whom holds an $n$ bit input, say $x$ and $y$. Neither knows the other’s input, and they wish to collaboratively compute $f(x, y)$ where the function $f : \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}$ is known to both. Furthermore, they had foreseen this situation (e.g., one of the parties could be a spacecraft and the other could be the base station on earth), so they had already — before they knew their inputs $x, y$ — agreed upon a protocol for communication. The cost of this protocol is the number of bits communicated by the players for the worst-case choice of inputs $x, y$.