There are several approaches to parallel search and maintenance of dictionaries, including priority queues, 2-3 trees, and B-trees. The authors discuss skip lists as an efficient alternative. This long paper is basically a meticulous description, in text and pseudocode, of three algorithms, namely search, insertion, and deletion. A detailed discussion of the efficiency of these algorithms is given.

The parallel search algorithm uses an ordered array of k keys to be searched for and a set of packets with these keys; the packets are sent across the list until they stop in appropriate positions. The expected performance of the algorithm is O ( log n + log k ), where n is the number of nodes on the skip list. The same performance is obtained for the insertion and deletion of algorithms. This efficiency is comparable to that of other parallel dictionary algorithms.

Search and insertion have already been implemented in the data parallel language C* and run on the CM-2. The authors discuss some implementation issues.