arXiv:2605.19531 · v2
Conflict-Freedom as a Progress Condition
摘要
An obstruction-free implementation guarantees progress to every operation that is given enough time to take steps in isolation. But, as we show in this paper, the mere presence of concurrent operations alone does not have to prevent progress; only incomplete conflicting (non-commuting) operations may do so. This progress condition, that we call conflict-freedom, is a natural generalization of obstruction-freedom that promises efficient implementations for objects exhibiting semantic commutativity. We show that, as with obstruction-freedom, every sequential object has a read-write conflict-free linearizable implementation. Our conflict-free universal construction is based on a novel generalization of the instrumental commit-adopt object, interesting in its own right.
作者备注：24 pages, 2 figures. This is an extended version of a conference article. The conference version of this article appears in the proceedings of the 2026 ACM Symposium on Principles of Distributed Computing (PODC'26)