A Concurrent Crash-Resilient Graph Data Structure for Non-Volatile Memory

Abstract

Parallel graph analysis frameworks such as the Parallel Boost Graph Library, Galois, or Ligra either do not support analyses on dynamically changing graphs, or do so inefficiently. Current practice is to prepare read-only snapshots for analysis. Taking snapshots can take considerable time for large graphs, and the use of global locks for snapshots conflicts with updates. Further, recording and replaying large input streams is not feasible, and there is no support for crash-resilience. In this poster, we describe ongoing work on a novel concurrent graph data structure that takes advantage of the Atlas programming model for persistent memory. This work supports efficient dynamic updates, non-blocking snapshots, and crash-resilience.

Publication
North East Database Day, 2017: Poster