between two processes. For example, a conflict arises if one process is trying to insert a new node, but at the same time another process is about to delete the predecessor of that node. There is a risk that the new node is added to the skip list, yet it is not longer reachable. (See image) K-element operations In this setting, operations on a priority queue is generalized to a batch of elements. For instance, k_extract-min deletes the smallest elements of the priority queue and returns those. In a shared-memory setting, the parallel priority queue can be easily implemented using parallel binary search trees and join-based tree algorithms. In particular, k_extract-min corresponds to a split on the binary search tree that has cost and yields a tree that contains the smallest elements. k_insert can be applied by a union of the original priority queue and the batch of insertions. If the batch is already sorted by the key, k_insert has cost. Otherwise, we need to first sort the batch, so the cost will be . Other operations for priority queue can be applied similarly. For instance, k_decrease-key can be done by first applying difference and then union, which first deletes the elements and then inserts them back with the updated keys. All these operations are highly parallel, and the theoretical and practical efficiency can be found in related research papers. The rest of this section discusses a queue-based algorithm on distributed memory. We assume each processor has its own local memory and a local (sequential) priority queue. The elements of the global (parallel) priority queue are distributed across all processors. A k_insert operation assigns the elements uniformly random to the processors which insert the elements into their local queues. Note that single elements can still be inserted into the queue. Using this strategy the global smallest elements are in the union of the local smallest elements of every processor with high probability. Thus each processor holds a representative part of the global priority queue. This property is used when k_extract-min is executed, as the smallest elements of each local queue are removed and collected in a result set. The elements in the result set are still associated with their original processor. The number of elements that is removed from each local queue depends on and the number of processors . By parallel selection the smallest elements of the result set