Date Added: Jun 2013
The authors consider the problem of computing a relational query q on a large input database of size n, using a large number p of servers. They establish both lower and upper bounds, in two settings. For a single round of communication, they give lower bounds in the strongest possible model, where arbitrary bits may be exchanged; they also give an algorithm that matches the lower bound for a specific class of databases. For multiple rounds of communication, they present lower bounds in a model where routing decisions for a tuple are tuple-based. They show that for the class of tree-like queries there exists a tradeoff between the number of rounds and the space exponent #.