Please note: This master’s thesis presentation will be given online.
Anubhav
Srivastava,
Master’s
candidate
David
R.
Cheriton
School
of
Computer
Science
Supervisor: Professor Trevor Brown
The ordered dictionary is one of the most fundamental abstract data types. It stores a set of key-value pairs, and supports operations to insert, remove and retrieve key-value pairs. It can also support range query operations.
In this thesis presentation, I will describe how (a,b)-trees (a generalization of B-trees) with simple optimistic locking can yield concurrent dictionaries that outperform state-of-the-art implementations. The trees perform particularly well under update-heavy workloads (in some cases outperforming all leading trees by a factor of 2). I also describe how elimination, a well-known idea in concurrent stacks, can be applied to further accelerate performance in skewed access distributions (in which some keys are accessed/updated more often than others).
To join this master’s thesis presentation on MS Teams, please go to https://teams.microsoft.com/l/meetup-join/19%3ameeting_NWQ1OTFiOTctYTllMS00MTE5LTk2Y2UtMWRiNDZhMTc4NmM5%40thread.v2/0?context=%7b%22Tid%22%3a%22723a5a87-f39a-4a22-9247-3fc240c01396%22%2c%22Oid%22%3a%221083eef2-81b4-42c4-a900-c879b9204119%22%7d.