算法与理论计算机2016arxiv.org
一种无等待（Wait-Free）栈
A Wait-Free Stack
进阶 · 约 45 分钟读完前置知识：并发编程基础、无锁数据结构、原子操作与内存模型
导读
论文讨论并发栈的 wait-free 实现，目标是在异步共享内存环境下让每个操作都能在有限步内完成。评论指出它虽然名为“栈”、提供后进先出（LIFO）语义，但 push/pop 并非常数时间，最坏情况复杂度需要看论文附录 A。
HN 关注点：wait-free 并发数据结构的实际可行性、性能代价与新颖性，尤其是它是否只是提供 LIFO 语义而非常数时间操作。
HN 评论精选
这几条评论里：质疑 1 补充 1 亲历 1
亲历亲历实现 wait-free 栈，强调它比 lock-free 栈困难得多。
我已经写过一个 wait-free 栈（gist 链接），它比 lock-free 栈难得多。后来还出版成书（日文，抱歉）。
kumagi查看英文原文
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
补充提醒读者该栈的 push/pop 最坏情况并非常数时间，只是提供 LIFO 语义。
一定要看论文末尾的附录 A（渐近最坏情况时间复杂度），如果你以为“栈”这个名字意味着 push/pop 是常数时间的话。这个数据结构只是在提供后进先出访问的意义上叫“栈”。
bnjmn查看英文原文
Make sure you check out Appendix A at the end of the paper (Asymptotic Worst-Case Time Complexity), in case you imagined the name "stack" implies constant-time push/pop performance. This data structure is only a "stack" in the sense that it provides last-in-first-out access.
质疑质疑其新颖性和 wait-free 性质，认为仍有竞争且类似 Kafka 的指针加清理设计。
我不太确定新颖在哪里——也许只是“wait-free”的措辞问题；但如果他们原子更新栈顶指针和链表，写操作会有锁竞争，标记元素被弹出时读操作也类似。我猜竞争受读者或写者数量限制，但我不会认为那是 wait-free（也可能只是措辞问题）。更关键的是，这只是 Kafka 工作方式的小变体（栈 vs 日志/队列，但同样有指针保存位置和清理操作），我不觉得特别新颖……也许我漏了什么？
zilchers查看英文原文
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 wait free (again, that could just be a verbiage thing). But, more to the point, this is just a slight twist on how Kafka works (stack vs log / queue, but same with the pointer holding place and a cleanup operation), I don't really see it as particularly novel...perhaps I'm missing something?
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2016Hacker News 讨论帖281 分 · 63 评
同领域还值得读
哲学家为何应关注计算复杂性
Why Philosophers Should Care About Computational Complexity (2011)
Scott Aaronson 的这篇长文论证计算复杂性理论（如 P vs NP、停机问题的复杂度视角）对哲学问题（如知识的本质、中文房间、水槽论证等）具有实质意义，而不仅是技术细…
算法与理论计算机2015 · 552 分 · 120 评进阶 · 约 90 分钟编辑精选通信的数学理论
A Mathematical Theory of Communication
是香农1948年的《通信的数学理论》，为通信建立数学框架：把信息量定义为不确定性或自由度（信息熵），并讨论信源编码、信道容量与可靠传输。
算法与理论计算机2020 · 495 分 · 91 评进阶 · 约 120 分钟编辑精选物理、拓扑、逻辑与计算：罗塞塔石碑
Physics, Topology, Logic and Computation: A Rosetta Stone (2009)
用范畴论充当“罗塞塔石碑”，试图在量子物理、拓扑、逻辑与计算四个领域之间建立统一的结构性类比：物理中的量子过程、拓扑中的配边、逻辑中的证明和计算中的程序，都可被视为某类范畴中的态…
算法与理论计算机2009 · 390 分 · 55 评 · 引用 13专业 · 约 180 分钟编辑精选一种快速、极小内存的一致性哈希算法
A Fast, Minimal Memory, Consistent Hash Algorithm
论文给出一种快速、省内存的一致哈希方案，目标是在桶数量变化时保持较小的键迁移成本，同时降低计算和内存开销。
算法与理论计算机2014 · 327 分 · 57 评 · 引用 4进阶 · 约 25 分钟编辑精选第五个 Busy Beaver 值的确定
Determination of the fifth Busy Beaver value
宣布确定了第五个 Busy Beaver 值 BB(5)：即 5 状态图灵机中停机前运行步数最多的机器（Champion）在 47,176,870 步后停机。
算法与理论计算机2025 · 288 分 · 116 评 · 引用 1专业 · 约 75 分钟编辑精选