The Taub Faculty of Computer Science Events and Talks

Today, most computing platforms are parallel, and the amount of parallelism available for the computation is ever increasing. This growing popularity of parallel platforms creates a need for efficient algorithms that utilize the growing degree of potential parallelism. This study presents specific algorithms as well as general techniques for creating fast practical data structures, focusing on data structures that provide a progress guarantee(e.g., wait-free data structures). Additionally, the theoretical foundations of concurrent data structures are explored and a lower bound for wait-free algorithms is provided. This talk will cover mainly two results. The first is a fast wait-free iterator for data structures that implement sets. The second is a general simulation technique that converts a lock-free data structure into a wait-free one, while preserving the efficiency of the original data structure.