Conflict-Freedom as a Progress Condition
For distributed systems designers, this provides a new progress condition that leverages commutativity for more efficient concurrent object implementations.
The paper introduces conflict-freedom, a progress condition generalizing obstruction-freedom, which guarantees progress unless operations conflict. It proves that every sequential object has a read-write conflict-free linearizable implementation via a novel commit-adopt object.
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.