Wednesday, 7.12.2011, 11:30
Lock-freedom is a progress guarantee that ensures overall program progress. Wait-freedom is a stronger progress guarantee that ensures the progress of each thread in the program. The latter property is valuable for systems that need to be responsive, such as real-time systems, operating systems, etc. While many practical lock-free algorithms are known in the literature, constructing wait-free algorithms is considered a complicated task that results in inefficient implementations. In this talk, we present first construction of a wait-free queue and a methodology called fast-path-slow-path, which allows the wait-free algorithms (and our queue in particular) to practically match the performance of the lock-free ones. Subsequent work has used this methodology to create other efficient wait-free algorithms.
bio: Alex Kogan is a Ph.D. student in the Department of Computer Science at the Technion. He holds M.Sc. (2008) and B.A (Summa Cum Laude, 2002) degrees from the same department. His research interests lie at the intersection of distributed and mobile computing, and in parallel computing. Specifically, he is interested in constructing efficient and reliable distributed algorithms for mobile networks, utilizing emergent technologies for wireless communication and the availability of cloud services. Recently, he became interested in exploring and boosting the performance of modern multi-core systems by devising efficient concurrent algorithms.