  We analyze the problem of discovering dependencies from distributed big data.
Existing (non-distributed) algorithms focus on minimizing computation by
pruning the search space of possible dependencies. However, distributed
algorithms must also optimize communication costs, especially in shared-nothing
settings, leading to a more complex optimization space. To understand this
space, we introduce six primitives shared by existing dependency discovery
algorithms, corresponding to data processing steps separated by communication
barriers. Through case studies, we show how the primitives allow us to analyze
the design space and develop communication-optimized implementations. Finally,
we support our analysis with an experimental evaluation on real datasets.
