Joint meeting with Theory Lunch (2)

  • Speaker: Erez Petrank (Technion)
  • Date: November 5, 2013 (Tuesday)
  • Room: TBA
  • Title:Wait-freedom made practical
  • Abstract:

With the proliferation of multicore systems, the design of concurrent algorithms and concurrent data structures to support them has becomes critical. Wait-free data structures provide a very basic and natural progress guarantee, assuring that each thread always makes progress when given enough CPU cycles. However, wait-free algorithms were considered difficult to design and too costly to be used in practice. Only the weaker lock-free guarantee, which allows almost all threads to starve, was achievable in practice. In this project, we provide efficient wait-free algorithms for various concurrent data structures and show that wait-freedom is achievable efficiently in practice.

Erez Petrank is an associate professor of Computer Science at the Technion. Petrank’s current research theme involves the design of practical data structures for modern multicore platforms. Previously, he was engaged with memory management for parallel architectures. His designs were incorporated into commercial runtime systems by IBM, Microsoft, and more, and his algorithms stand at the heart of modern versions for various classical memory management algorithms such as reference-counting, compaction, and real-time garbage collection. Petrank has received various awards including the IBM Research Division Award (twice), the Yanai Award for excellence in teaching, and the Rothschild Research fellowship, Petrank holds 10 patents, one of which was listed among the 10% most profitable IBM patents for 2002. His research has been funded by Intel, Microsoft, IBM, the Israel Science Foundation, and the United States – Israel Binational Science Foundation.