What is it about?
This paper examines the issue of register overflow in real-world implementations of the Bakery algorithm. The authors present a novel variant algorithm named Bakery++ that prevents overflows from ever happening by using simple conditional statements.
Featured Image
Photo by Андрей Сизов on Unsplash
Why is it important?
Bakery++ is a new mutual exclusion algorithm that is guaranteed never to allow an overflow. It is simple, correct, and easy to implement. Bakery++ has the same temporal and spatial complexities as the original Bakery.
Perspectives
Mutual Exclusion (ME) is a fundamental problem in concurrent computing. The Bakery algorithm was the first genuine solution to ME because it did not rely on any lower-lever mutual exclusion. The process of designing the the new algorithm as an overflow-free solution and verifying its correctness was an instructive task!
Amirhosein Sayyadabdi
University of Isfahan
Read the Original
This page is a summary of: Avoiding Register Overflow in the Bakery Algorithm, August 2020, ACM (Association for Computing Machinery),
DOI: 10.1145/3409390.3409411.
You can read the full text:
Contributors
The following have contributed to this page
