Edinburgh Research Explorer

Distributed Graph Simulation: Impossibility and Possibility

Research output: Contribution to journalArticle

Related Edinburgh Organisations

Open Access permissions

Open

Documents

http://www.vldb.org/pvldb/vol7/p1083-fan.pdf
Original languageEnglish
Pages (from-to)1083-1094
Number of pages12
JournalProceedings of the VLDB Endowment (PVLDB)
Volume7
Issue number12
Publication statusPublished - 2014

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.

Download statistics

No data available

ID: 17598373