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. kVe say that A is parallel scalable in (a) response time if its parallel computational cost is determined by the largest fragment F-m of G and the size vertical bar Q vertical bar of query Q, and (b) data shipment if its total amount of data shipped is determined by vertical bar Q vertical bar and the number of fragments of C. independent of the size of graph G. (1) We prove an impossibility theorem: there exists no distributed graph simulation algorithm that is parallel scalable in either response time or data shipment. (2) However, we show that distributed graph simulation is par ion bounded, i.e., its response time depends only on vertical bar Q vertical bar, vertical bar F-m vertical bar and the number vertical bar V-f vertical bar of nodes in G with edges across different fragments; and its data shipment depends on vertical bar Q vertical bar and the number vertical bar E-f vertical bar of crossing edges only. We provide the first algorithms with these performance guarantees. (3) We also identify special cases of patterns and graphs when parallel scalability is possible. (4) We experimentally verify the scalability and efficiency of our algorithms.