  MapReduce (and its open source implementation Hadoop) has become the de facto
platform for processing large data sets. MapReduce offers a streamlined
computational framework by interleaving sequential and parallel computation
while hiding underlying system issues from the programmer. Due to the
popularity of MapReduce, there have been attempts in the theoretical computer
science community to understand the power and limitations of the MapReduce
framework. In the most widely studied MapReduce models each machine has memory
sub-linear in the input size to the problem, hence cannot see the entire input.
This restriction places many limitations on algorithms that can be developed
for the model; however, the current understanding of these restrictions is
still limited.
  In this paper, our goal is to work towards understanding problems which do
not admit efficient algorithms in the MapReduce model. We study the basic
question of determining if a graph is connected or not. We concentrate on
instances of this problem where an algorithm is to determine if a graph
consists of a single cycle or two disconnected cycles. In this problem, locally
every part of the graph is similar and the goal is to determine the global
structure of the graph. We consider a natural class of algorithms that can
store/process/transfer the information only in the form of paths and show that
no randomized algorithm cannot answer the decision question in a
sub-logarithmic number of rounds. Currently, there are no absolute super
constant lower bounds on the number of rounds known for any problem in
MapReduce. We introduce some of the first lower bounds for a natural graph
problem, albeit for a restricted class of algorithms. We believe our result
makes progress towards understanding the limitations of MapReduce.
