ylkingsbury@watdragon.waterloo.edu (Yvonne Kingsbury) (11/18/89)
The University of Waterloo
200 University Avenue
Waterloo, Ontario
The Institute of Computer Research (ICR)
Presents a Colloquium on
Concurrent Skip Lists and Other Variations
by Dr. William Pugh
of Dept. of Computer Science, University of Maryland, College Park
DATE: November 21, 1989
TIME: 11:30 a.m. (Revision: Time Changed from 3:30 to 11:30)
LOCATION: Davis Centre, Room 1304
ABSTRACT
Skip lists are a probabilistic list-based data structure
that seem likely to supplant balanced trees as the
implementation method of choice for many applications. Skip
lists algorithms have the same asymptotic expected time
bounds as balanced trees and are simpler, faster and use
less space. I will briefly review skip list algorithms and
techniques used in their analysis.
I will also describe a simple and elegant method for
concurrent maintenance of sorted linked lists that can
easily be formally proven correct. I will also show how
this idea can be extended to skip lists, yielding simple and
efficient concurrent skip list algorithms. The algorithms
use no read locks and thus allow an unlimited number of
readers. In a test in which 1000 processes were trying to
insert and delete elements in a data structure containing
only 1000 elements, only a 15% overhead for lock contention
was incurred.
If time and interest permits, I will also discuss variations
on skip lists, such as the effects of not enforcing
restrictions on the maximum level of a list and using
different probability distributions for generating random
levels.
Everyone welcome.