Treaps can handle parallel set operations very efficiently:

https://www.cs.cmu.edu/~scandal/papers/treaps-spaa98.pdf

Maestro Tarjan tells us skiplists and treaps are very nearly the same thing: https://arxiv.org/abs/1806.06726. I don’t see how to transpose TFA’s extension of the former to the latter, though.