Back to Search
Start Over
Tight Bounds for Critical Sections in Processor Consistent Platforms.
- Source :
- IEEE Transactions on Parallel & Distributed Systems; Oct2006, Vol. 17 Issue 10, p1072-1083, 12p, 2 Black and White Photographs, 4 Diagrams
- Publication Year :
- 2006
-
Abstract
- Most weak memory consistency models are incapable of supporting a solution to mutual exclusion using only read and write operations to shared variables. Processor Consistency-Goodman's version (PC-G) is an exception. Ahamad et al. showed that Peterson's mutual exclusion algorithm is correct for PC-G, but Lamport's bakery algorithm is not. This paper derives a lower bound on the number of and type of (single or multiwriter) variables that a mutual exclusion algorithm must use in order to be correct for PC-G. Specifically, any such solution for n processes must use at least one multiwriter variable and n single-writer variables. Peterson's algorithm for two processes uses one multiwriter and two single-writer variables, and therefore establishes that this bound is tight for two processes. This paper presents a new n-process algorithm for mutual exclusion that is correct for PC-G and achieves the bound for any n. While Peterson's algorithm is fair, this extension to arbitrary n is not fair. Six known algorithms that use the same number and type of variables are shown to fail to guarantee mutual exclusion when the memory consistency model is only PC-G, as opposed to the Sequential Consistency model for which they were designed. A corollary of our investigation is that, in contrast to Sequential Consistency, multiwriter variables cannot be implemented from single-writer variables in a PC-G system. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 10459219
- Volume :
- 17
- Issue :
- 10
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Parallel & Distributed Systems
- Publication Type :
- Academic Journal
- Accession number :
- 22531582
- Full Text :
- https://doi.org/10.1109/TPDS.2006.146