A Simple and Practical Concurrent Non-blocking Unbounded Graph with Reachability Queries

Bapi Chatterjee, Sathya Peri, Muktikanta Sa, Nandini Singhal

Abstract

Graph algorithms applied in many applications, including social networks, communication networks, VLSI design, graphics, and several others, require dynamic modifications—addition and removal of vertices and/or edges—in the graph. This paper presents a novel concurrent non-blocking algorithm to implement a dynamic unbounded directed graph in a shared-memory machine. The addition and removal operations of vertices and edges are lock-free. For a finite sized graph, the lookup operations are wait-free. Most significant component of the presented algorithm is the reachability query in a concurrent graph. The reachability queries in our algorithm are obstruction-free and thus impose minimal additional synchronization cost over other operations. We prove that each of the data structure operations are linearizable. We extensively evaluate a sample C/C++ implementation of the algorithm through a number of micro-benchmarks. The experimental results show that the proposed algorithm scales well with the number of threads and on an average provides 5 to 7x performance improvement over a concurrent graph implementation using coarse-grained locking.

Introduction

Graphs are fundamental to modern computing, powering everything from social network analysis to circuit design. In high-performance multi-core systems, these graphs must be "concurrent," allowing multiple threads to read and write simultaneously. Traditional concurrency control relies on locks, which often create bottlenecks. For example, a thread performing a complex reachability query (like a Breadth-First Search) might lock the entire graph, forcing all update threads to wait. This leads to issues such as deadlocks, priority inversion, and poor scalability.

Non-blocking data structures avoid these pitfalls by ensuring that threads can make progress without waiting for locks. However, building a non-blocking, unbounded graph that supports complex queries while maintaining linearizability—the guarantee that every operation appears to take effect instantaneously—is a significant technical challenge.

Design and Implementation

The proposed algorithm represents the graph using a composite adjacency list. This structure consists of a sorted linked list of "vertex-nodes" (VNodes), where each VNode points to its own sorted linked list of "edge-nodes" (ENodes).

The graph representation using a composite adjacency list of VNodes and ENodes.

Lock-Free Modifications

Structural changes, such as adding or removing vertices and edges, are handled using atomic Compare-And-Swap (CAS) operations. To remove a node, the algorithm first "logically" marks it as deleted before "physically" unlinking it. This two-step process ensures that concurrent threads do not lose their place in the list during a traversal.

Reachability and Linearizability

The core innovation of this work is the linearizable reachability query (GetPath). To ensure correctness without global locks, the authors use a "Double Collect" strategy. Each VNode includes an atomic edge counter (ecnt) that increments whenever its adjacency list is modified. During a search, the algorithm records these counters; if they remain unchanged after the search, the result is validated as consistent.

Timeline illustrating concurrent operations and the challenges of maintaining linearizability across multiple threads.

The reachability query is designed to be obstruction-free. While weaker than lock-freedom, obstruction-freedom is simpler to implement and performs exceptionally well in practice because total thread interference is relatively rare in typical workloads.

Experimental Evaluation

The algorithm was evaluated using C/C++ micro-benchmarks on a system with 56 physical cores. The researchers tested various scenarios, from lookup-intensive (90% lookups) to update-intensive (90% updates) workloads.

Key findings include:

  • Significant Speedup: The non-blocking algorithm provided a 5x to 7x performance improvement over coarse-grained locking.
  • Linear Scalability: While the lock-based version's performance decreased as more threads were added due to contention, the non-blocking version scaled linearly until hardware saturation.
  • Efficient Queries: The obstruction-free reachability queries introduced minimal overhead, proving that the ecnt-based validation is highly efficient.

Conclusion

This paper presents a practical, non-blocking directed graph that achieves high performance and scalability. By combining lock-free list management with a clever atomic counter for query validation, the algorithm provides a robust solution for concurrent graph processing. While the current work focuses on reachability, these techniques could be extended to other complex graph algorithms, such as finding strongly connected components or calculating shortest paths, in future research.

Summary updated

Abstract

Graph algorithms applied in many applications, including social networks, communication networks, VLSI design, graphics, and several others, require dynamic modifications -- addition and removal of vertices and/or edges -- in the graph. This paper presents a novel concurrent non-blocking algorithm to implement a dynamic unbounded directed graph in a shared-memory machine. The addition and removal operations of vertices and edges are lock-free. For a finite sized graph, the lookup operations are wait-free. Most significant component of the presented algorithm is the reachability query in a concurrent graph. The reachability queries in our algorithm are obstruction-free and thus impose minimal additional synchronization cost over other operations. We prove that each of the data structure operations are linearizable. We extensively evaluate a sample C/C++ implementation of the algorithm through a number of micro-benchmarks. The experimental results show that the proposed algorithm scales well with the number of threads and on an average provides 5 to 7x performance improvement over a concurrent graph implementation using coarse-grained locking.
BibTeX
@inproceedings{chatterjee2019simple,
  author = {Bapi Chatterjee and Sathya Peri and Muktikanta Sa and Nandini Singhal},
  title = {{A Simple and Practical Concurrent Non-blocking Unbounded Graph with Reachability Queries}},
  booktitle = {ICDCN},
  year = {2019},
  url = {https://openreview.net/forum?id=e56LCROw5b},
}
Figure