Coordination-freeness and parallel evaluation of conjunctive queries

Abstract

The interest in utilizing parallel and distributed systems to process large amounts of data has grown immensely over the past few years. However, this also brings along some interesting new challenges. In this thesis, we focus on coordination on the one hand, and efficient parallel evaluation of conjunctive queries on the other. We study the existing theoretical research regarding coordination-freeness and the CALM-conjecture and formalize some variations on the current model. Then we turn our attention to more practical evaluation strategies specifically for conjunctive queries. First, we look at optimal broadcasting strategies based on oblivious broadcasting functions. Next, we look at two algorithms in the MPC model: the single-round HyperCube algorithm which is optimal on skew-free input instances, and a multi-round algorithm based on HyperCube which is worst-case optimal even on skewed input instances. To conclude, we made an implementation of these last two algorithms and conducted several experiments to better understand their practical behaviour.