Sign in to confirm you’re not a bot
This helps protect our community. Learn more

Introduction

0:00

Questions about what we'll cover

4:44

Lock-based concurrency

9:04

Non-blocking concurrency

14:50

Wait-freedom

17:30

Q&A on concurrency guarantees

19:10

What does simulation mean?

26:51

What does practical mean?

30:04

The fast-path-slow-path method

40:19

Going from lock-free to wait-free

46:02

Cat time

51:28

Q&A on going wait-free

52:09

The basic algorithm

54:23

Cat time

1:00:40

Q&A on algorithm

1:01:29

The basic algorithm cont'd

1:05:42

Visualizing linked list helping

1:10:12

Challenges

1:26:15

System assumptions

1:32:52

Wait-free algorithm examples

1:34:52

Q&A on algorithm

1:37:41

Intermission

1:42:00

Resuming

1:44:10

Blindly writing the normalized representation

1:45:20

Comparing against the paper

2:28:55

The ABA problem

2:59:57

Q&A on code and ABA

3:09:23

Understanding the normalized representation

3:17:20

Intermission

3:21:06

Fat points for ABA?

3:22:40

Implementing the simulator

3:24:50

Operation records and the help queue

3:39:10

The help state machine: preCAS

4:07:14

The help state machine: executeCAS

4:22:10

The help state machine: postCAS

4:24:12

The help state machine: retrying

4:26:23

Returning the operation output

4:30:40

Tidying up warnings

4:31:12

Monitoring pre/post runs

4:33:15

What's missing in execute?

4:43:30

Q&A for today

4:44:49
Lock-Free to Wait-Free Simulation in Rust
1KLikes
48,259Views
2021May 22
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.... 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:    • Lock-Free to Wait-Free Simulation in Rust ...  .

Follow along using the transcript.

Jon Gjengset

96K subscribers

Practical Wait-Free Simulation

Lock-Free to Wait-Free Simulation in Rust

Jon Gjengset
2

Lock-Free to Wait-Free Simulation in Rust (part 2)

Jon Gjengset