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 |
|---|---|---|---|---|
| 947 | Parallelizing Sequential Graph Computations | 2017 | SIGMOD | 0.00012914714 |
| 2,851 | Incremental Graph Computations: Doable and Undoable | 2017 | SIGMOD | 7.9419904e-05 |
| 3,026 | Functional Dependencies for Graphs | 2016 | SIGMOD | 7.7387829e-05 |
| 4,858 | Association Rules with Graph Patterns | 2015 | VLDB | 6.3793644e-05 |
| 7,000 | RAGraph: A Region-Aware Framework for Geo-Distributed Graph Processing | 2024 | VLDB | 5.6251489e-05 |
| 7,015 | A Hierarchical Contraction Scheme for Querying Big Graphs | 2022 | SIGMOD | 5.6210836e-05 |
| 8,006 | Data-driven Visual Graph Query Interface Construction and Maintenance: Challenges and Opportunities | 2016 | VLDB | 5.4085844e-05 |
| 8,398 | Deducing Certain Fixes to Graphs | 2019 | VLDB | 5.3399392e-05 |
| 8,846 | Data Driven Approximation with Bounded Resources | 2017 | VLDB | 5.2649328e-05 |
| 9,073 | Machine Learning for Graph Data Management and Query Processing | 2025 | VLDB | 5.2283159e-05 |
| 11,563 | Extending Graph Rules with Oracles | 2024 | VLDB | 4.9793485e-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.0012092602 |
| 22 | Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud | 2012 | VLDB | 0.00055962491 |
| 1,148 | Graph Pattern Matching: From Intractable to Polynomial Time | 2010 | VLDB | 0.00011809728 |
| 1,317 | Incremental Graph Pattern Matching | 2011 | SIGMOD | 0.00011050011 |
| 1,410 | A Distributed Graph Engine for Web Scale RDF Data | 2013 | VLDB | 0.00010742208 |
| 2,573 | Minimal MapReduce Algorithms | 2013 | SIGMOD | 8.2821647e-05 |
| 3,179 | TAO: How Facebook Serves the Social Graph | 2012 | SIGMOD | 7.5654159e-05 |
| 5,152 | Performance Guarantees for Distributed Reachability Queries | 2012 | VLDB | 6.2525917e-05 |
| 5,462 | Distributed Query Evaluation with Performance Guarantees | 2007 | SIGMOD | 6.1221387e-05 |
| 5,605 | Capturing Topology in Graph Pattern Matching | 2012 | VLDB | 6.0695806e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 8,789 | Distributed Set Reachability | 2016 | SIGMOD |
| 2 | 2,101 | DUALSIM: Parallel Subgraph Enumeration in a Massive Graph on a Single Machine | 2016 | SIGMOD |
| 3 | 2,248 | Streaming Graph Partitioning: An Experimental Study | 2018 | VLDB |
| 4 | 10,740 | Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration | 2026 | VLDB |
| 5 | 3,154 | Managing Large Dynamic Graphs Efficiently | 2012 | SIGMOD |
| 6 | 3,830 | Distributed Edge Partitioning for Trillion-edge Graphs | 2019 | VLDB |
| 7 | 1,862 | Large-Scale Distributed Graph Computing Systems: An Experimental Evaluation | 2015 | VLDB |
| 8 | 1,249 | Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows | 2018 | VLDB |
| 9 | 12,192 | Dynamic Scaling for Parallel Graph Computations | 2019 | VLDB |
| 10 | 5,152 | Performance Guarantees for Distributed Reachability Queries | 2012 | VLDB |