Distributed Graph Simulation: Impossibility and Possibility
Summary: Proves that distributed graph simulation cannot be parallel-scalable in response time or data shipment independent of graph size. Establishes partition-bounded guarantees based on largest fragment and cross-fragment nodes/edges, with matching algorithms and special scalable cases. (summarized by gpt-5.6-luna on Jul 24 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Wenfei Fan (Beihang University; University of Edinburgh)
- 2. Xin Wang (Southwest Jiaotong University)
- 3. Yinghui Wu (University of Edinburgh; Washington State University)
- 4. Dong Deng (Tsinghua University)
BibTeX Citation
@article{fan_vldb14,
title = {{Distributed Graph Simulation: Impossibility and Possibility}},
author = {Fan, Wenfei and Wang, Xin and Wu, Yinghui and Deng, Dong},
journal = {PVLDB},
series = {{VLDB} '14},
volume = {7},
number = {12},
pages = {1083--1094},
doi = {10.14778/2732977.2732979},
url = {https://doi.org/10.14778/2732977.2732979},
year = {2014}
}Incoming Citations (Sorted by Pagerank)
Showing 11 of 11 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 956 | Parallelizing Sequential Graph Computations | 2017 | SIGMOD | 0.0001297452 |
| 2,798 | Incremental Graph Computations: Doable and Undoable | 2017 | SIGMOD | 8.1129891e-05 |
| 2,973 | Functional Dependencies for Graphs | 2016 | SIGMOD | 7.9083516e-05 |
| 4,832 | Association Rules with Graph Patterns | 2015 | VLDB | 6.4877e-05 |
| 6,857 | RAGraph: A Region-Aware Framework for Geo-Distributed Graph Processing | 2024 | VLDB | 5.7525746e-05 |
| 6,876 | A Hierarchical Contraction Scheme for Querying Big Graphs | 2022 | SIGMOD | 5.7483615e-05 |
| 7,848 | Data-driven Visual Graph Query Interface Construction and Maintenance: Challenges and Opportunities | 2016 | VLDB | 5.5327238e-05 |
| 8,225 | Deducing Certain Fixes to Graphs | 2019 | VLDB | 5.4624971e-05 |
| 8,701 | Data Driven Approximation with Bounded Resources | 2017 | VLDB | 5.3828806e-05 |
| 11,067 | Machine Learning for Graph Data Management and Query Processing | 2025 | VLDB | 5.093636e-05 |
| 11,227 | Extending Graph Rules with Oracles | 2024 | VLDB | 5.093636e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 10 of 10 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 3 | Pregel: A System for Large-Scale Graph Processing | 2010 | SIGMOD | 0.0012250108 |
| 20 | Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud | 2012 | VLDB | 0.00056944564 |
| 1,128 | Graph Pattern Matching: From Intractable to Polynomial Time | 2010 | VLDB | 0.0001206219 |
| 1,296 | Incremental Graph Pattern Matching | 2011 | SIGMOD | 0.00011269684 |
| 1,387 | A Distributed Graph Engine for Web Scale RDF Data | 2013 | VLDB | 0.00010949523 |
| 2,539 | Minimal MapReduce Algorithms | 2013 | SIGMOD | 8.4526595e-05 |
| 3,140 | TAO: How Facebook Serves the Social Graph | 2012 | SIGMOD | 7.7176906e-05 |
| 5,029 | Performance Guarantees for Distributed Reachability Queries | 2012 | VLDB | 6.3960846e-05 |
| 5,336 | Distributed Query Evaluation with Performance Guarantees | 2007 | SIGMOD | 6.2612462e-05 |
| 5,484 | Capturing Topology in Graph Pattern Matching | 2012 | VLDB | 6.2018052e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 8,651 | Distributed Set Reachability | 2016 | SIGMOD |
| 2 | 2,119 | DUALSIM: Parallel Subgraph Enumeration in a Massive Graph on a Single Machine | 2016 | SIGMOD |
| 3 | 2,221 | Streaming Graph Partitioning: An Experimental Study | 2018 | VLDB |
| 4 | 10,558 | Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration | 2026 | VLDB |
| 5 | 3,109 | Managing Large Dynamic Graphs Efficiently | 2012 | SIGMOD |
| 6 | 3,752 | Distributed Edge Partitioning for Trillion-edge Graphs | 2019 | VLDB |
| 7 | 1,875 | Large-Scale Distributed Graph Computing Systems: An Experimental Evaluation | 2015 | VLDB |
| 8 | 1,246 | Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows | 2018 | VLDB |
| 9 | 11,892 | Dynamic Scaling for Parallel Graph Computations | 2019 | VLDB |
| 10 | 5,029 | Performance Guarantees for Distributed Reachability Queries | 2012 | VLDB |