Design a Lock-Free Concurrent Skip List for a Time-Series Database
Overview
What this challenge is about.
Implement Fraser's lock-free skip list in Rust with marked pointers for logical deletion. Validate under loom for all interleavings up to 4 threads (or use shuttle if loom can't terminate in your scenarios). Stress-test under 16 concurrent writers + 16 concurrent readers on the team's benchmark harness (provided). Benchmark insert, lookup, delete throughput at 1, 4, 8, 16, 32 threads vs the existing mutex-based implementation. Deliver source, loom test suite, benchmark plots, and a 5-page design document covering the ABA-problem mitigation and where the lock-free version is slower than the mutex one (typically: single-threaded).
The Brief
What you'll do, and what you'll demonstrate.
Replace a mutex-protected skip list with a lock-free CAS-based implementation validated under model checking and benchmarked against the baseline.
Earning criteria — what you'll demonstrate
- Implement Fraser-style lock-free data structures with marked pointers
- Validate concurrent correctness with loom model checking
- Benchmark concurrent data structures across realistic thread counts
- Document the cases where lock-free is slower than locking
Program Fit
Where this fits in your program.
Sharpens the same skills your degree expects you to demonstrate.
Skills
Skills you'll demonstrate.
Each one shows up on your verified credential.
Careers
Roles this prepares you for.
Real titles. Real skill bridges. Pick the one closest to your trajectory.
Career mappings coming soon.