Lock-Free to Wait-Free Simulation in Rust (part 2)
Channel: Jon Gjengset
Date: 2021-06-13

In this stream, we continue implementing the concurrency algorithm from the academic paper "A Practical Wait-Free Simulation for Lock-Free Data Structures" by Erez Petrank and and Shahar Timnat in Rust. The paper details a general way to turn lock-free concurrent data-structures into wait-free ones (we also talk about what that means), and you can find it at http://cs.technion.ac.il/~erez/Papers/wf-simulation-full.pdf.

0:00:00 Introduction
0:01:18 Rust for Rustaceans
0:02:54 Code Recap
0:12:03 Naming the CAS list type
0:33:05 Versioned CASes
2:05:38 ExecuteCASes
2:09:46 Cat interlude
2:10:52 Paper vs. Code
2:20:03 Contention detection
2:36:22 It compiles!
2:36:40 PostCASes
2:50:45 Intermission
2:53:11 Paper vs. Code
2:56:06 Tidying Up Nested Result
2:59:46 The Wait-Free Queue
3:04:35 Per-Thread Handles
3:35:45 Porting the Queue
3:54:40 Weird Head Semantics
4:16:56 Pop and Push
4:32:40 Implementing Helping
5:15:37 State of Affairs and Next Steps

You can find the current code at https://github.com/jonhoo/bystander.

Live version with chat: https://www.youtube.com/watch?v=OqnZpVufTtg.