This left me wondering if there might be a deterministic parallel algorithm for union find :) I did find this arxiv paper from April which claims to have one:

This left me wondering if there might be a deterministic parallel algorithm for union find :) I did find this arxiv paper from April which claims to have one: https://arxiv.org/abs/2304.09331 https://arxiv.org/abs/2304.09331 My understanding is that they process batches of edges at a time. If they "conflict" (meaning they want to do different things to the data structure) then they're processed in serial, otherwise all edges in the batch are handled sequentially. They provide a bound on how often edges should conflict, and use that to show the complexity.