Map-reduce process algebra: a formalism to describe directed acyclic graph task-based jobs in parallel environments

Cloud Computing has made possible flexible resources provisioning from an almost unlimited pool. This has created the opportunity to broaden the horizon of data that can be analyzed, allowing to support the so called Big Data Analytics applications. New programming paradigms, such as NoSQL queries and Map-Reduce applications, have emerged within frameworks such as Microsoft Azure, Hadoop and Apache Spark. In many cases, applications execute jobs that are split into stages, each one composed of tasks that can be run in parallel on many computational nodes. Directed acyclic graphs describe the precedence between stages, defining the execution rules and controlling the degree of parallelism. This work presents a Process Algebra dialect aimed at describing both jobs and execution environments. The proposed framework is then used to model and study standard parallel programming benchmarks, to demonstrate its applicability.