Abstract / Description of output
A mutual exclusion algorithm is called speed independent if its correctness does not depend on the relative speed of the components. Famous mutual exclusion protocols such as Dekker's, Peterson's and Lamport's bakery are meant to be speed independent.
In this talk I argue that speed-independent mutual exclusion may not be implementable on standard hardware, depending on how we believe reading and writing to a memory location is really carried out. It can be implemented on electrical circuits, however.
This builds on previous work showing that mutual exclusion cannot be accurately modelled in standard process algebras.
In this talk I argue that speed-independent mutual exclusion may not be implementable on standard hardware, depending on how we believe reading and writing to a memory location is really carried out. It can be implemented on electrical circuits, however.
This builds on previous work showing that mutual exclusion cannot be accurately modelled in standard process algebras.
Original language | English |
---|---|
Title of host publication | 29th International Conference on Concurrency Theory (CONCUR 2018) |
Editors | Sven Schewe, Lijun Zhang |
Place of Publication | Dagstuhl, Germany |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany |
Number of pages | 1 |
Volume | 118 |
ISBN (Electronic) | 978-3-95977-087-3 |
DOIs | |
Publication status | Published - 31 Aug 2018 |
Publication series
Name | Leibniz International Proceedings in Informatics (LIPIcs) |
---|---|
Publisher | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik |
Volume | 118 |
ISSN (Electronic) | 1868-8969 |
Keywords / Materials (for Non-textual outputs)
- Mutual exclusion
- speed independence
- concurrent reading and writing
- liveness
- justness