A space- and time-efficient local-spin spin lock.
type: Item
instance of: scholarly article
title: A space- and time-efficient local-spin spin lock.
zbMATH Open document ID: 1042.68121
DOI: 10.1016/S0020-0190(02)00224-7
author: Yong-Jik Kim
author: James H. Anderson
published in: Information Processing Letters
publication date: 2003-01-21T00:00:00Z
review text: A simple code transformation is presented that reduces the space complexity of Yang and Anderson's local-spin mutual exclusion algorithm. In both the original and the transformed algorithm, only atomic read and write instructions are used; each process generates \(\Theta(\log N)\) remote memory references per lock request, where \(N\) is the number of processes. The transformed algorithm uses \(\Theta(N)\) distinct variables, which is clearly optimal.
Mathematics Subject Classification ID: 68W05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1856442
zbMATH Keywords: Mutual exclusion
zbMATH Keywords: Local spinning
zbMATH Keywords: Read/write atomicity
zbMATH Keywords: Shared-memory systems
zbMATH Keywords: Space complexity
zbMATH Keywords: Algorithms
MaRDI profile type: Publication
cites work: Q2766859
cites work: An improved lower bound for the time complexity of mutual exclusion
cites work: Adaptive and efficient mutual exclusion (extended abstract)
cites work: A fast, scalable mutual exclusion algorithm
full work available at URL: s0020-0190(02)00224-7
OpenAlex ID: W1965859223
description: scientific article; zbMATH DE number 1856442