Transactional Data Structure Libraries

RiSE will host a talk by Idit Keidar on May 12, 2016

We introduce transactions into libraries of concurrent data structures; such transactions can be used to ensure atomicity of sequences of data structure operations. By focusing on transactional access to a well-defined set of data structure operations, we strike a balance between the ease-of programming of transactions and the efficiency of custom-tailored data structures. We exemplify this concept by designing and implementing a library supporting transactions on any number of maps, sets (implemented as skiplists), and queues. Our library offers efficient and scalable transactions, which are an order of magnitude faster than state-of-the-art transactional memory toolkits. Moreover, our approach treats stand-alone data structure operations (like put and enqueue) as first class citizens, and allows them to execute with virtually no overhead, at the speed of the original data structure
library.

Joint work with Alexander Spiegelman and Guy Golan-Gueta, to appear in PLDI 2016.

Speaker bio:

Idit Keidar is a Professor and the Associate Dean for Graduate Studies at the Viterbi Department of Electrical Engineering at the Technion. She also heads the Networked Software Systems Laboratory (NSSL). She received her BSc (summa cum laude), MSc (summa cum laude) and PhD from the Hebrew University of Jerusalem in 1992, 1994, and 1998 resp. Prof. Keidar is an expert in distributed computing and concurrency, having developed numerous distributed and networked systems, including for storage, multicast, group communication, group membership, distributed transactions and atomic commit, cloud services, trusted access to data in cloud storage, and concurrent programming. Her awards include the Henry Taub Prize for Academic Excellence, the Yanai Award for Excellence in Academic Education, the Muriel and David Jackow Award for Excellence in Teaching, the David Dudi Ben-Aharon Research Award, the Allon Fellowship, the Rothschild Yad-Hanadiv fellowship for postdoctoral studies, and a Wolf Foundation Prize for Ph.D. students.