Correctness and concurrent complexity of the black-white bakery algorithm

DOI10.1007/S00165-016-0364-4zbMATH Open1342.68348OpenAlexW2322615457WikidataQ59436837 ScholiaQ59436837MaRDI QIDQ736464FDOQ736464

Authors: W. H. Hesselink 

Publication date: 4 August 2016

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

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

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

zbMATH Keywords

mutual exclusionconcurrent complexityFCFSUNITY

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• On interprocess communication. I: Basic formalism
• An axiomatic proof technique for parallel programs
• A new solution of Dijkstra's concurrent programming problem
• Title not available (Why is that?)
• Long lived adaptive splitter and applications
• The Black-White Bakery Algorithm and Related Bounded-Space, Adaptive, Local-Spinning and FIFO Algorithms
• Verification of sequential and concurrent programs
• The mutual exclusion problem
• Verifying a simplification of mutual exclusion by Lycklama-Hadzilacos
• Title not available (Why is that?)
• Communicating State Transition Systems for Fine-Grained Concurrent Resources
• Simple, space-efficient, and fairness improved FCFS mutual exclusion algorithms

Cited In (2)

• The Black-White Bakery Algorithm and Related Bounded-Space, Adaptive, Local-Spinning and FIFO Algorithms
• Tournaments for mutual exclusion: verification and concurrent complexity

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)