Make a Graph Algorithm Thread-Safe

Problem Given an existing single-threaded implementation of a graph algorithm, explain how to make it safe for concurrent execution across multiple threads, and write pseudocode reflecting the design.

Requirements

• Identify every piece of shared mutable state the algorithm touches
• Guarantee correctness: no node processed twice, no node missed, no torn reads of shared structures
• Preserve the algorithm's result — a parallel run must produce an answer consistent with a sequential one
• Pseudocode showing the synchronization points and the work-distribution scheme

Core design

• Start by classifying state, because the synchronization falls out of the classification:
  • Read-only after construction (the adjacency structure, if never mutated) — needs no locking at all, only safe publication before the threads start.
  • Shared mutable — the visited set, frontier/work queue, and any result accumulator. These are the contention points.
  • Thread-local — per-thread scratch buffers and partial results, which need no synchronization.
• Visited-marking is the critical section that matters most: a contains followed by an add is a race, and two threads will both expand the same node. The fix is a single atomic operation — an atomic compare-and-swap on a per-node flag, or a concurrent set's putIfAbsent, where exactly one thread observes the transition and claims the node.
• Frontier as a concurrent work queue with threads pulling nodes and pushing discovered neighbours. Termination is non-obvious: an empty queue does not mean done, because a thread may still be expanding a node that will push more work. Track active workers alongside queue emptiness, or use a phaser/barrier per BFS level.
• Result accumulators should be per-thread and merged at the end rather than locked on every update — the merge is O(threads), the contention is O(edges).
• Partition first, lock second: if the graph decomposes into disjoint subgraphs (or can be partitioned by node ID), each thread owns a region and synchronization is needed only at boundary edges. Eliminating shared state beats synchronizing it.

Discussion points

• Level-synchronous BFS parallelizes cleanly (barrier between levels, no ordering issues within a level); DFS does not — its correctness depends on visitation order, so a parallel DFS explores a different tree and is only valid if the algorithm doesn't rely on DFS ordering.
• Trade-off: a single lock around the visited set is trivially correct and destroys scaling; atomic per-node flags scale but need the CAS-claim discipline; lock striping sits between.
• False sharing: per-node flags packed into one cache line make adjacent atomics contend even with no logical conflict — pad or use a bitset with word-level CAS.
• Load imbalance on skewed graphs: high-degree hub nodes give one thread disproportionate work. Discuss work-stealing over static partitioning.
• Determinism: results may be correct but non-reproducible (traversal order varies run to run), which matters if downstream code or tests assume a fixed order.
• Amdahl's law reality check: if the algorithm is memory-bound on random adjacency access, threads contend on memory bandwidth and parallel speedup stalls well before core count.