Distributed Graph Simulation: Impossibility and Possibility

Wenfei Fan, Xin Wang, Yinghui Wu, Dong Deng

Research output: Contribution to journalArticlepeer-review

Abstract

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 parallel 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 parallel scalable in either response time or data shipment. (2)
However, we show that distributed graph simulation is partition 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 parallel scalability is possible. (4) We experimentally verify the scalability and efficiency of our algorithms.
Original languageEnglish
Pages (from-to)1083-1094
Number of pages12
JournalProceedings of the VLDB Endowment (PVLDB)
Volume7
Issue number12
Publication statusPublished - 2014

Fingerprint Dive into the research topics of 'Distributed Graph Simulation: Impossibility and Possibility'. Together they form a unique fingerprint.

Cite this