Tight Bounds for Critical Sections in Processor Consistent Platforms
Why this work is in the frame
A frame that forgets how it found something cannot be audited. These are the routes that admitted this work.
Bibliographic record
Abstract
Most weak memory consistency models are incapable of supporting a solution to mutual exclusion using only read and write operations to shared variables. Processor consistency-Goodman's version (PC-G) is an exception. Ahamad et al. showed that Peterson's mutual exclusion algorithm is correct for PC-G, but Lamport's bakery algorithm is not. This paper derives a lower bound on the number of and type of (single or multiwriter) variables that a mutual exclusion algorithm must use in order to be correct for PC-G. Specifically, any such solution for n processes must use at least one multiwriter variable and n single-writer variables. Peterson's algorithm for two processes uses one multiwriter and two single-writer variables, and therefore establishes that this bound is tight for two processes. This paper presents a new n-process algorithm for mutual exclusion that is correct for PC-G and achieves the bound for any n. While Peterson's algorithm is fair, this extension to arbitrary n is not fair. Six known algorithms that use the same number and type of variables are shown to fail to guarantee mutual exclusion when the memory consistency model is only PC-G, as opposed to the sequential consistency model for which they were designed. A corollary of our investigation is that, in contrast to sequential consistency, multiwriter variables cannot be implemented from single-writer variables in a PC-G system
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.
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.000 | 0.000 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.000 | 0.000 |
| Bibliometrics | 0.000 | 0.001 |
| Science and technology studies | 0.000 | 0.000 |
| Scholarly communication | 0.000 | 0.000 |
| Open science | 0.000 | 0.000 |
| Research integrity | 0.000 | 0.000 |
| Insufficient payload (model declined to judge) | 0.000 | 0.000 |
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 it