  Most of the prior work in massively parallel data processing assumes
homogeneity, i.e., every computing unit has the same computational capability,
and can communicate with every other unit with the same latency and bandwidth.
However, this strong assumption of a uniform topology rarely holds in practical
settings, where computing units are connected through complex networks. To
address this issue, Blanas et al. recently proposed a topology-aware massively
parallel computation model that integrates the network structure and
heterogeneity in the modeling cost. The network is modeled as a directed graph,
where each edge is associated with a cost function that depends on the data
transferred between the two endpoints. The computation proceeds in synchronous
rounds, and the cost of each round is measured as the maximum cost over all the
edges in the network.
  In this work, we take the first step into investigating three fundamental
data processing tasks in this topology-aware parallel model: set intersection,
cartesian product, and sorting. We focus on network topologies that are tree
topologies, and present both lower bounds, as well as (asymptotically) matching
upper bounds. The optimality of our algorithms is with respect to the initial
data distribution among the network nodes, instead of assuming worst-case
distribution as in previous results. Apart from the theoretical optimality of
our results, our protocols are simple, use a constant number of rounds, and we
believe can be implemented in practical settings as well.
