Skip to main content

A First-Come-First-Served Mutual-Exclusion Algorithm with Small Communication Variables

Edward A. Lycklama, Vassos Hadzilacos

PDF DOI 10.1145/115372.115370 dblp BibTeX

Abstract

We present an algorithm for the mutual-exclusion problem that satisfies the "first-come-firstserved" property and requires only five shared bits per participant.The algorithm works in a model of concurrency that does not assume atomic operations.

Related papers

What It Means for a Concurrent Program to Satisfy a Specification: Why No One Has Specified Priority POPL 1985
A New Solution to Lamport's Concurrent Programming Problem Using Small Shared Variables TOPLAS 1983
Tidex: a mutual exclusion lock PPoPP 2016
The Concurrency Workbench: A Semantics-Based Tool for the Verification of Concurrent Systems TOPLAS 1993
A Proof of Burns N-Process Mutual Exclusion Algorithm Using Abstraction TACAS 1998
A Bounded First-In, First-Enabled Solution to the l-Exclusion Problem TOPLAS 1994
On group mutual exclusion for dynamic systems PPoPP 2021
MPI+Threads: runtime contention and remedies PPoPP 2015