Skip lists (Pugh, 1990) provide sorted dictionaries with logarithmic-time operations like search trees but skip lists are much more amenable to concurrent updates.
Is it possible to create an efficient purely functional concurrent skip list? If not, is it possible to create any kind of efficient purely functional concurrent sorted dictionary?