Is Speed-Independent Mutual Exclusion Implementablel (Invited Talk)

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.
Original languageEnglish
Title of host publication29th International Conference on Concurrency Theory (CONCUR 2018)
EditorsSven Schewe, Lijun Zhang
Place of PublicationDagstuhl, Germany
PublisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany
Number of pages1
Volume118
ISBN (Electronic)978-3-95977-087-3
DOIs
Publication statusPublished - 31 Aug 2018

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Volume118
ISSN (Electronic)1868-8969

Keywords / Materials (for Non-textual outputs)

  • Mutual exclusion
  • speed independence
  • concurrent reading and writing
  • liveness
  • justness

Fingerprint

Dive into the research topics of 'Is Speed-Independent Mutual Exclusion Implementablel (Invited Talk)'. Together they form a unique fingerprint.

Cite this