Distributed Graph Simulation: Impossibility and Possibility

This paper studies fundamental problems for distributed graph simulation. Given a pattern query Q and a graph G that is fragmented and distributed, a graph simulation algorithm A is to compute the matches Q(G) of Q in G. We say that A is parallel scalable in (a) response time if its paral-lel computational cost is determined by the largest fragment Fm of G and the size |Q | of query Q, and (b) data shipment if its total amount of data shipped is determined by |Q| and the number of fragments of G, independent of the size of graph G. (1) We prove an impossibility theorem: there exists no distributed graph simulation algorithm that is par-allel scalable in either response time or data shipment. (2) However, we show that distributed graph simulation is par-tition bounded, i.e., its response time depends only on |Q|, |Fm | and the number |Vf | of nodes in G with edges across different fragments; and its data shipment depends on |Q| and the number |Ef | of crossing edges only. We provide the first algorithms with these performance guarantees. (3) We also identify special cases of patterns and graphs when par-allel scalability is possible. (4) We experimentally verify the scalability and efficiency of our algorithms. 1