Mutual exclusion by four shared bits with not more than quadratic complexity

Hesselink, W. H., 1-May-2015, In : Science of computer programming. 102, p. 57-75 19 p.

Research output: Contribution to journalArticleAcademicpeer-review

For years, the mutual exclusion algorithm of Lycklama and Hadzilacos (1991) [21] was the optimal mutual exclusion algorithm with the first-come-first-served property, with a minimal number of (non-atomic) communication variables (5 bits per thread). Recently, Aravind published an improvement of it, which uses 4 bits per thread and has simplified waiting conditions. This algorithm is extended here with fault tolerance, and it is verified by assertional methods, using the proof assistant PVS. Progress is proved by means of UNITY logic. The paper proposes a new measure of concurrent time complexity, and proves that the concurrent complexity for throughput of the present algorithm is not more than quadratic in the number of threads.
Original languageEnglish
Pages (from-to)57-75
Number of pages19
JournalScience of computer programming
Publication statusPublished - 1-May-2015

View graph of relations

Download statistics

No data available

ID: 29167710