Correctness and concurrent complexity of the black-white bakery algorithm

DOI10.1007/S00165-016-0364-4MaRDI QIDQ736464zbMATH OpenOpenAlexWikidataFDO

Authors W. H. Hesselink

Publication date 4 August 2016

Published in Formal Aspects of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00165-016-0364-4

zbMATH Keywords

mutual exclusionconcurrent complexityFCFSUNITY

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Recommendations

• The Black-White Bakery Algorithm and Related Bounded-Space, Adaptive, Local-Spinning and FIFO Algorithms
• scientific article; zbMATH DE number 868108
• scientific article; zbMATH DE number 2080925
• On the computational complexity of Bongartz's algorithm
• On the correctness of parallel algorithms
• The parallel complexity of two problems on concurrency
• Black-box correctness tests for basic parallel data structures
• Counterexamples to the long-standing conjecture on the complexity of BDD binary operations
• Complexity of checking bisimilarity between sequential and parallel processes

Cites work

• scientific article; zbMATH DE number 1639446 (Why is no real title available?)
• scientific article; zbMATH DE number 194539 (Why is no real title available?)
• A new solution of Dijkstra's concurrent programming problem
• An axiomatic proof technique for parallel programs
• Communicating state transition systems for fine-grained concurrent resources
• Long lived adaptive splitter and applications
• On interprocess communication. I: Basic formalism
• Progress under bounded fairness
• Simple, space-efficient, and fairness improved FCFS mutual exclusion algorithms
• The Black-White Bakery Algorithm and Related Bounded-Space, Adaptive, Local-Spinning and FIFO Algorithms
• The mutual exclusion problem
• Verification of sequential and concurrent programs
• Verifying a simplification of mutual exclusion by Lycklama-Hadzilacos

Cited in

(3)

• Towards an automatic proof of the bakery algorithm
• Tournaments for mutual exclusion: verification and concurrent complexity
• The Black-White Bakery Algorithm and Related Bounded-Space, Adaptive, Local-Spinning and FIFO Algorithms

Describes a project that uses

Uses Software

• PVS
• UNITY

This page was built for publication: Correctness and concurrent complexity of the black-white bakery algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q736464)