Nonblocking Concurrent Data Structures

Friday, 14th March 2014, 3:30 pm (PDCC Meeting Room)
Speaker: Professor Faith Ellen (University of Toronto, Canada)
Title: Nonblocking Concurrent Data Structures

A library of concurrent data structures can make the task of developing concurrent software much easier. Although sequential data structures can be transformed into concurrent data structures in straightforward ways using locks or transactional memory, the results are generally inefficient.
We discuss some of the difficulties and techniques involved in constructing efficient concurrent data structures, including our recent work on balanced binary search trees.


Faith Ellen has been a Professor in the Department of Computer Science at the University of Toronto since 1986. She received her B.Math. in Pure Mathematics and Computer Science in 1977 and her M.Math in Computer Science in 1978 from the University of Waterloo. She received her Ph.D. in Computer Science from the University of California, Berkeley, in 1982. From 1983 to 1986, she was an Assistant Professor in the Department of Computer Science at the University of Washington. Faith Ellen was the vice-chair of SIGACT from 1997 to 2001 and was the chair of the steering committee for PODC from 2006 to 2009. Her main area of research is studying the complexity of problems in distributed computing, with the goal of understanding how parameters of various models affect their computational power.