Queue based mutual exclusion with linearly bounded overtaking

Hesselink, W. H. & Aravind, A. A., 1-Jul-2011, In : Science of computer programming. 76, 7, p. 542-554 13 p.

Research output: Contribution to journalArticleAcademicpeer-review

Copy link to clipboard



The queue based mutual exclusion protocol establishes mutual exclusion for N > 1 threads by means of not necessarily atomic variables. In order to enter the critical section, a competing thread needs to traverse as many levels as there are currently competing threads. Competing threads can be overtaken by other competing threads. It is proved here, however, that every competing thread is overtaken less than N times, and that the overtaking threads were competing when the first one of them exits.
Original languageEnglish
Pages (from-to)542-554
Number of pages13
JournalScience of computer programming
Issue number7
Publication statusPublished - 1-Jul-2011


  • Mutual exclusion, Refinement, Shared memory, Bounded overtaking, Verification, ALGORITHM

Download statistics

No data available

ID: 2516294