Graduate Mentor's supervisor: Prof. Trevor Brown
Sets are among the most fundamental data structures in modern data-intensive applications. They support operations for creating, updating, clearing, and querying associations between keys and values. A set (or map) is called ordered if it provides a successor operation that returns the first key (or key-value pair) greater than a given key. Many applications need to maintain large amounts of ordered data.
For example, social media platforms maintain trending topics ordered by various engagement metrics as millions of users make posts and interact concurrently; financial trading systems maintain millions of orders by price and submission time to model market dynamics; and massive multiplayer online games maintain leaderboards of millions of players as they score points.
To process large volumes of operations, these applications employ many parallel threads of computation and therefore require ordered sets that scale, i.e., improve in performance as the number of available threads in the system increases.
Professor T. Brown and collaborators recently designed a concurrent version of the van Emde Boas tree that incorporates a number of novel space optimizations and can outperform other state-of-the-art concurrent ordered sets by a large margin. However, this data structure relies on hardware transactional memory (HTM) for synchronization. The goal of this project is to extend this work to universally available synchronization mechanisms for systems without HTM support, with optimistic concurrency control (OCC) being one natural direction.
The student will work on extending the existing concurrent tree to support synchronization via optimistic concurrency control (OCC). This will involve the design and implementation of new synchronization mechanisms, a new correctness argument, an experimental evaluation of performance and scalability, and a comparison against other state-of-the-art concurrent sets. Strong results may lead to the preparation of a research paper for publication.
This project is best suited for students who are comfortable programming in C++ and have completed CS 240/CS 240E (or have equivalent knowledge). Prior experience with multithreaded programming (specifically with HTM or OCC), concurrent data structures, or algorithms is helpful but not required. Students should be willing to learn new concepts independently, ask questions when needed, and engage with research papers and technical documentation.