[论文] 未决冲突使进展变得不可能

Source: arXiv - 2602.04013v1

请提供您希望翻译的具体文本内容（例如摘要、引言或其他章节），我将按照要求将其译成简体中文并保留原始的格式和链接。谢谢！

概述

本文研究了可交换性——即某些操作可以重新排序而不影响最终状态——如何影响线性化共享对象的进度保证。作者提出了一种新的进度条件，冲突阻塞自由 (COF)，它保证只要一个操作仅与可交换操作产生步骤竞争，它就能完成。随后，作者证明，尽管该概念直观上很有吸引力，但在经典的异步读写共享内存模型中，COF 无法用于通用构造。

关键贡献

• 引入冲突‑阻塞‑自由 (COF)：一种进度条件，通过允许与可交换操作的竞争来放宽阻塞自由，同时在仅存在冲突（不可交换）操作时仍保证完成。
• 形式化“冲突感知”进度：在可线性化对象的上下文中提供冲突与可交换操作的精确定义。
• 不可能性证明：表明任何满足 COF 的通用构造都不能仅使用异步读写寄存器实现。
• 理论洞见：展示仅仅调用冲突操作就会产生不可避免的同步开销，即使该操作实际上从未执行。

方法论

1. 模型与定义

• 作者们工作在标准的 异步共享内存模型 中，进程通过 原子读/写寄存器 进行通信。
• 可交换（Commuting）操作被定义为其效果可以互换而不改变抽象状态的操作；冲突（conflicting）操作则相反。
• COF 正式定义如下：如果进程 p 的操作在 没有任何冲突操作的步骤争用（来自可交换操作的步骤争用被忽略）的情况下运行足够长的时间，则该操作完成。

2. 通用构造框架

• 他们考虑一种通用的 “通用构造”，该构造可以使用共享内存基元实现任意 线性化对象。
• 该构造被假设为 冲突感知（conflict‑aware）：它能够检测并发操作是否与当前操作冲突。

3. 不可能性论证

• 通过归约到经典的 共识（consensus）不可能性，他们构造了一个执行，其中两个进程调用冲突操作，这些操作实际上从未在对象上 执行 任何步骤，但在 COF 下仍然相互阻塞。
• 通过精心交错读写操作，他们展示了任何符合 COF 的通用构造都将在 无等待（wait‑free）方式下解决共识，这与已知的读/写内存的不可实现性结果相矛盾。

结果与发现

• COF is strictly stronger than obstruction‑freedom（它允许更高的并行度），但 strictly weaker than wait‑freedom（它仍然容忍一定的争用）。
• Universal constructions cannot satisfy COF 在纯读/写模型中；任何尝试实现它的做法都会隐式提供一个 wait‑free 共识解，这在理论上是不可能的。
• Pending conflicts are costly：即使冲突操作仅处于 pending（即已被调用但尚未执行任何步骤）状态，它也可能在 COF 下阻塞其他操作的进展。

Practical Implications

• 并发库的设计: 开发者不能依赖 COF 来保证仅基于读/写寄存器构建的通用无锁数据结构的前进性。需要额外的同步原语（例如 compare‑and‑swap、fetch‑and‑add）来绕过此不可能性。
• 优化可交换工作负载: 虽然 COF 本身在全局上不可实现，但 可交换 操作不必相互阻塞的洞见可以指导专用数据结构（例如 CRDT、并发计数器）的设计，这类结构明确将可交换路径与冲突路径分离。
• 调试与性能调优: 理解仅仅 调用 冲突操作就会引入隐藏的同步开销，可帮助工程师在高争用系统中发现意外的停顿。
• 语言/运行时支持: 该结果表明，旨在实现“冲突感知”前进性的运行时系统应暴露低层原语（如 LL/SC）或提供超出普通读/写的内建冲突检测机制。

限制与未来工作

• 模型限制：该不可能性仅适用于异步读/写内存模型。它并未排除使用更强原语（例如，原子 RMW、事务性内存）的 COF 实现。
• 对通用构造的范围：证明针对通用构造；操作集合受限的专用对象仍可能实现 COF。
• 未来方向：
  • 探索在更丰富的基对象（例如 fetch‑and‑add、compare‑and‑swap）下的 COF 可行性。
  • 确定具体的对象族（例如可交换计数器、集合），在这些对象上可以高效实现 COF。
  • 开发实用的冲突检测 API，让开发者显式区分可交换路径和冲突路径，从而减轻潜在冲突的隐藏成本。

作者

• Petr Kuznetsov
• Pierre Sutra
• Guillermo Toyos-Marfurt

论文信息

• arXiv ID: 2602.04013v1
• 分类: cs.DC
• 出版日期: 2026年2月3日
• PDF: 下载 PDF