LOCK-FREE LINKED LISTS AND SKIP LISTS MIKHAIL FOMITCHEV
Bibliographic record
Abstract
Lock-free shared data structures implement distributed objects without the use of mutual exclusions, thus providing robustness and reliability. We present new implementations of lock-free linked list and lock-free skip list dictionary data structures for shared-memory systems. We give a detailed proof of correctness for both of them and present an amortized performance analysis for our linked lists. To the best of our knowledge, our implementation of the lock-free skip lists is the first that does not use the universal constructions. We also show that our linked lists implementation has a better amortized performance than prior lock-free implementations of this data structure. Our algorithms use the single word C&S synchronization primitive. ii Acknowledgements First, I want to thank my supervisor Eric Ruppert. Without his guidance and support, this thesis probably would not have been completed, or at the very least, it would be in a much poorer shape. I am very grateful for his vast contributions to this thesis and for the many things that I have learnt from him during my M. Sc. studies. I would also like to thank the professors I have been taking courses with during my graduate studies in York University. Particularly, I would like to thank Patrick Dymond, my co-supervisor. The insight into the amortized analysis techniques that I have obtained from him was critical to the success of this work. I am grateful to all members of my examining committee for their time and for their helpful comments on my thesis. I would like to express my gratitude to the Ontario Graduate Scholarship program for the scholarship I was awarded in 2002-2003 academic year.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame machine prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. The Gemma side is a direct model label for every work in the frame, read from the title-only record. The Codex side is a classifier learned from the 10,348 direct Codex labels and calibrated to design-weighted sample rates; fields without enough sample support carry no Codex call. Candidate is the union of the two sides; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels.
Distilled classifier scores by category (both heads)
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.001 | 0.007 |
| Meta-epidemiology (narrow) | 0.001 | 0.001 |
| Meta-epidemiology (broad) | 0.001 | 0.000 |
| Bibliometrics | 0.001 | 0.002 |
| Science and technology studies | 0.001 | 0.002 |
| Scholarly communication | 0.003 | 0.007 |
| Open science | 0.001 | 0.003 |
| Research integrity | 0.001 | 0.002 |
| Insufficient payload (model declined to judge) | 0.008 | 0.005 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one source (direct Gemma or distilled Codex), not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".