按年被提到
20152016 · 1 次2026
算法与数据结构›经典算法与数据结构·arXiv:1510.00116 · cs.DC

A Wait-Free Stack

Seep Goel, Pooja Aggarwal, Smruti R. Sarangi · 2015
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2016-07-17 · 最近 2022-11-13
2不同的人
2活跃月份
2讨论串
0被引(OpenAlex)
arXiv 摘要(候选层不写导读)

In this paper, we describe a novel algorithm to create a con- current wait-free stack. To the best of our knowledge, this is the first wait-free algorithm for a general purpose stack. In the past, researchers have proposed restricted wait-free implementations of stacks, lock-free implementations, and efficient universal constructions that can support wait-free stacks. The crux of our wait-free implementation is a fast pop operation that does not modify the stack top; instead, it walks down the stack till it finds a node that is unmarked. It marks it but does not delete it. Subsequently, it is lazily deleted by a cleanup operation. This operation keeps the size of the stack in check by not allowing the size of the stack to increase beyond a factor of W as compared to the actual size. All our operations are wait-free and linearizable.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

没有评论直接链到它;下面是它被提交的讨论串里回复最多的评论(不计入统计)
讨论串评论duiker101 · 2016-07

“So uhm the top 2 link of HN in the last 5 hours have been about this and while they are highly voted there is very little discussion going. Can someone give some context as to why this is attracting so much (surely deserved) attention? How will this affect us? Is it likely to have a deep effect on general computing performances? In what ways will this be …”

A Wait-Free Stack原评论 ↗
讨论串评论kumagi · 2016-07

“I already wrote wait-free stack https://gist.github.com/kumagi/d259274270fdc1385f81 It is much difficult than lock-free stack. https://gist.github.com/kumagi/b9a4715b1ce0dd511922 And published as book(in Japanese sorry) http://longgate.co.jp/books/grimoire-vol3.html”

A Wait-Free Stack原评论 ↗
讨论串评论zilchers · 2016-07

“I'm not sure I see what's novel about this - maybe it's a verbiage thing around "wait free," but if they're atomically updating the top pointer and linked list, there will be lock contention on writes, and similarly when marking an item popped, on reads. I suppose the contention is bounded by the number of readers or writers, but I wouldn't consider that …”

A Wait-Free Stack原评论 ↗
被提交为 story · 2 次