A DESIGN OF A PARALLEL DICTIONARY USING SKIP LISTS

We present a top-down design of a parallel PRAM dictionary using skip lists. More precisely, we give detailed algorithms to search for, inse rt or delete k elements in a skip list of n elements in parallel. The algorithms are iterative and easy to implement on real machines. We di scuss some implementation issues and give concrete examples in C. The algorithms run on an EREW PRAM in expected time O(log n + log k) usin g k processors. We also show an explicit protocol to avoid read confli cts thus obtaining an efficient EREW version of our algorithms. Althou gh the asymptotic performance of the parallel skip list algorithms is not better compared to that of other parallel dictionaries, they are a practical alternative. Skip list algorithms are very simple and there is a small probability of large deviations from their expected perfor mance.