We present a PRAM implementation of a parallel dictionary with skip lists. More precisely, we give algorithms to search, insert and delete k ordered elements in a skip list of n elements in parallel. The algorithms are clear and easy to explain and implement. All of them are iterative. They can be implemented in the EREW PRAM model using O(k) processors in expected time O(log n + log k).
Gabarro, J., Martinez, C., Messeguer, X. "Parallel update and search in skip lists". 1993.