School of Computer Science Colloquium Announcement of Dr. Trevor Brown:"Fast and simple concurrent data structures using PathCAS "

Friday, December 2, 2022 - 11:00 to 12:00


The School of Computer Science at the University of Windsor is pleased to present…  

Colloquium Presentation by Dr. Trevor Brown 

Picture of Dr. Trevor Brown, SCS colloquium presenter on Dec. 2, 2022
Date: Friday December 2, 2022 
Time: 11:00am – 12:00pm  
Location: Erie Hall, Room 3123 
Reminders: Two-part attendance mandatory, arrive 5-10 minutes prior to event starting - LATECOMERS WILL NOT BE ADMITTED once the door has been closed and the presentation has begun. Please be respectful of the presenter by NOT knocking on the door for admittance. 


Concurrent data structures are important building blocks for modern software, as they can be accessed by multiple threads of execution at the same time. To maximize the performance of concurrent data structures, researchers have often turned to highly complex fine-grained synchronization techniques. The resulting algorithms are fast, but very difficult to reason about. On the other hand, simple synchronization techniques, such as hand over hand locking, or transactional memory, are easy to understand, but can have limited performance or portability compared to handcrafted algorithms. 
Techniques at both ends of this complexity-performance spectrum have been extensively explored, but less is known about the middle ground: techniques that are willing to sacrifice some performance for simplicity, while remaining competitive with state-of-the-art handcrafted designs. In this talk, I first will survey simple techniques for designing concurrent data structures, and illustrate when they perform well, or poorly, compared to state of the art handcrafted data structures. I will then present PathCAS, a novel synchronization technique that carefully combines existing ideas with new insights, while avoiding common overheads. PathCAS can be used to implement efficient search data structures relatively simply, and the resulting implementations can be competitive with highly tuned, handcrafted algorithms. 
Keywords: Concurrency, data structures, synchronization, locks, lock-free 


Dr. Trevor Brown is an assistant professor in the Cheriton School of Computer Science at the University of Waterloo. He did his PhD at the University of Toronto under Faith Ellen, and did postdocs at the Technion under Hagit Attiya, and at IST Austria under Dan Alistarh. His research interests lie at the intersection between theory and practice, and are focused around concurrent data structures, memory management, and the exploration of modern hardware features such as transactional memory, and non-volatile RAM. 




5113 Lambton Tower 401 Sunset Ave. Windsor ON, N9B 3P4 (519) 253-3000 Ext. 3716