算法与理论计算机2020arxiv.org
Chronofold：一种面向版本化文本的数据结构 (2020)
Chronofold: A data structure for versioned text (2020)
进阶 · 约 90 分钟读完前置知识：分布式系统基础、CRDT 概念、因果序
导读
Chronofold 是一种用于版本化文本的数据结构，旨在支持对文本的并发编辑与历史版本管理，处理分布式编辑中的因果顺序问题。论文提出可在不再需要细粒度变更时折叠结构以节省空间。
HN 关注点：是因为它把缓存失效与因果一致性这两个分布式系统的难题结合到一个数据结构中，与 CRDT 等协同编辑方案相关。
HN 评论精选
这几条评论里：支持 1 补充 3
补充提供了多个现成实现和学习资源
这是 2020 年 4 月的论文。现在已有几个实现可以上手玩：一个 Rust 实现 [1]、一个 PureScript/JS 实现 [2]。后者作者的视频系列 [3] 对理解它特别有帮助，如果你愿意花几个小时看直播的话。
wokwokwok查看英文原文
This is from April 2020. You can find a few implementations (1, 2) to play with now if you’re interested… I found the video series [3] in the latter particularly interesting in trying to understand it, if you’re game to sit through a few hours of live stream. [1] - (rust) https://github.com/dkellner/chronofold [2] - (js) https://github.com/jmatsushita/purescript-chronofold [3] - https://m.youtube.com/watch?v=gg5q_V7tBjE&pp=sAQA
支持认为它融合了缓存失效与因果性两大难题，赞赏其空间折叠设计
这本质上是缓存失效问题，混合了相对论/因果性——把两个领域最难的部分揉进一个数据结构/算法里。我觉得很有意思，需要多读几遍才能理解所有细节。当单个变更不再需要时折叠结构的想法在节省空间方面很有吸引力，期待看到它的实现。
mikewarot查看英文原文
So, this is essentially cache invalidation, mixed with relativity/causality... the hardest aspects of two different fields, all rolled into one data structure/algorithm. I found it interesting, and something I will have to read a few more times before all the details make sense. The idea of collapsing the structure when individual changes are no longer needed is appealing in terms of space saving. I look forward to seeing this implemented.
补充指出这是近期另一篇相关讨论的后续
我猜这是最近这篇文章的后续：https://news.ycombinator.com/item?id=28017204
josh11b查看英文原文
I suspect this is a follow-up to this recent article: https://news.ycombinator.com/item?id=28017204
补充补充了作者的演讲视频资料
这是 Grischenko 关于 Chronofold 的一个演讲：https://m.youtube.com/watch?v=dKzMZsg5EVA
jitl查看英文原文
Here’s a presentation by Grischenko on Chronofold https://m.youtube.com/watch?v=dKzMZsg5EVA
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2020Hacker News 讨论帖16 分 · 0 评
- 2021Hacker News 讨论帖207 分 · 23 评
同领域还值得读
哲学家为何应关注计算复杂性
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 分钟编辑精选