Parallelism in Dynamic Graph Algorithms
19Guy Blelloch (Carnegie Mellon University)
https://simons.berkeley.edu/talks/guy-blelloch-carnegie-mellon-university-2023-09-18
Dynamic Graphs and Algorithm Design
At some level, dynamic data structures are inherently sequential since they involve sequences of queries and updates. Although there is some opportunity for parallelism within each operation, it is often too small to worry about, especially if the operations only require polylogarithmic time sequentially. This talk will present two lines of work that exposes significant parallelism in dynamic data structures. Firstly, I will talk about batch dynamic algorithms. In this setting updates and queries can be made in batches. Such batching permits more parallelism, and can also reduce the total work relative to applying the operations one at a time. Interestingly in some cases even batches with a sequence of mixed updates and queries can be implemented efficiently. Secondly, I will talk about graph streaming algorithms where we have a rapid stream of arbitrary queries and updates to a graph data structure. The goal is allow the operations to run in parallel while giving queries a consistent view of the graph, even while updates are happening concurrently. This setting mixes ideas from persistent and concurrent data structures. The persistence gives snapshots of the graph, and the concurrency handles the asynchronous setting in which the operations need to be processed.