  In this paper, we study the communication complexity for the problem of
computing a conjunctive query on a large database in a parallel setting with
$p$ servers. In contrast to previous work, where upper and lower bounds on the
communication were specified for particular structures of data (either data
without skew, or data with specific types of skew), in this work we focus on
worst-case analysis of the communication cost. The goal is to find worst-case
optimal parallel algorithms, similar to the work of [18] for sequential
algorithms.
  We first show that for a single round we can obtain an optimal worst-case
algorithm. The optimal load for a conjunctive query $q$ when all relations have
size equal to $M$ is $O(M/p^{1/\psi^*})$, where $\psi^*$ is a new query-related
quantity called the edge quasi-packing number, which is different from both the
edge packing number and edge cover number of the query hypergraph. For multiple
rounds, we present algorithms that are optimal for several classes of queries.
Finally, we show a surprising connection to the external memory model, which
allows us to translate parallel algorithms to external memory algorithms. This
technique allows us to recover (within a polylogarithmic factor) several recent
results on the I/O complexity for computing join queries, and also obtain
optimal algorithms for other classes of queries.
