Conflict-Freedom as a Progress Condition
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918511306080256 |
|---|---|
| author | Kuznetsov, Petr Sutra, Pierre Toyos-Marfurt, Guillermo |
| author_facet | Kuznetsov, Petr Sutra, Pierre Toyos-Marfurt, Guillermo |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_19531 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Conflict-Freedom as a Progress Condition Kuznetsov, Petr Sutra, Pierre Toyos-Marfurt, Guillermo Distributed, Parallel, and Cluster Computing F.1.2 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. |
| title | Conflict-Freedom as a Progress Condition |
| topic | Distributed, Parallel, and Cluster Computing F.1.2 |
| url | https://arxiv.org/abs/2605.19531 |