MapReduce algorithm for finding st-connectivity

In recent years the MapReduce framework has become one of the most popular parallel computing platform for processing big data. It is frequently used by companies such as Facebook, IBM, and Google. Moreover, more and more universities adopt this approach for their academic purposes. Since the MapReduce computing framework is designed for distributed computing on massive data sets, with the help of new algorithms, it can be a suitable platform for processing graphs with billions of vertices and edges. The st-connectivity, that is, the existence of at least one path between any two vertices s and t, is a fundamental graph theory problem. This paper introduces a new algorithm, which is capable of finding st-connectivity in arbitrary graphs, designed for the MapReduce framework. The paper also defines the data structure, which might be suitable in case of other graph processing algorithms.