Using locks to control access to shared data structures limits concurrency. We consider shared-memory implementations of two fundamental data structures, queues and stacks, that avoid the use of locks. All previous lock-free implementations of these data structures require Omega(p) steps per operation, on average, in a system of p processes. This talk will describe implementations that achieve polylogarithmic step complexity per operation while also providing a stronger progress property: every operation completes within a bounded number of steps. This is joint work with Hossein Naderibeni and Shalom Asbell.
Eric Ruppert is a faculty member at York University in Toronto, Canada. He does research on the theory of computation by multiple processes, with a focus on shared-memory systems. He completed his PhD at the University of Toronto, and has spent time as a researcher at Brown University, EPFL and Université Paris Cité. He is currently visiting FORTH for two months.
