File:Lock-Free to Wait-Free Simulation in Rust.webm
Summary
| Description |
English: In this stream, we start 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. The first half or so of the stream is us going through what problem the paper is solving, and the proposed algorithm, and the second half is us working towards encoding it in Rust. We didn't get all the way there in this video, so there are more videos to come!
0:00:00 Introduction 0:04:44 Questions about what we'll cover 0:09:04 Lock-based concurrency 0:14:50 Non-blocking concurrency 0:17:30 Wait-freedom 0:19:10 Q&A on concurrency guarantees 0:26:51 What does simulation mean? 0:30:04 What does practical mean? 0:40:19 The fast-path-slow-path method 0:46:02 Going from lock-free to wait-free 0:51:28 Cat time 0:52:09 Q&A on going wait-free 0:54:23 The basic algorithm 1:00:40 Cat time 1:01:29 Q&A on algorithm 1:05:42 The basic algorithm cont'd 1:10:12 Visualizing linked list helping 1:26:15 Challenges 1:32:52 System assumptions 1:34:52 Wait-free algorithm examples 1:37:41 Q&A on algorithm 1:42:00 Intermission 1:44:10 Resuming 1:45:20 Blindly writing the normalized representation 2:28:55 Comparing against the paper 2:59:57 The ABA problem 3:09:23 Q&A on code and ABA 3:17:20 Understanding the normalized representation 3:21:06 Intermission 3:22:40 Fat points for ABA? 3:24:50 Implementing the simulator 3:39:10 Operation records and the help queue 4:07:14 The help state machine: preCAS 4:22:10 The help state machine: executeCAS 4:24:12 The help state machine: postCAS 4:26:23 The help state machine: retrying 4:30:40 Returning the operation output 4:31:12 Tidying up warnings 4:33:15 Monitoring pre/post runs 4:43:30 What's missing in execute? 4:44:49 Q&A for today Live version with chat: https://www.youtube.com/watch?v=Hzm_OZ44qOA. |
| Date | |
| Source | YouTube: Lock-Free to Wait-Free Simulation in Rust – View/save archived versions on archive.org and archive.todayCategory:Media from YouTube |
| Author | Jon Gjengset |
Licensing
.svg){kind=icon}
- You are free:
- to share – to copy, distribute and transmit the work
- to remix – to adapt the work
- Under the following conditions:
- attribution – You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
 |
This file, which was originally posted to an external website, has not yet been reviewed by an administrator or reviewer to confirm that the above license is valid. See Category:License review needed for further instructions. |