4 papers
Conflict-Freedom as a Progress Condition
Petr Kuznetsov, Pierre Sutra, Guillermo Toyos-Marfurt
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…
Pending Conflicts Make Progress Impossible
Petr Kuznetsov, Pierre Sutra, Guillermo Toyos-Marfurt
In this work, we study progress conditions for commutativity-aware, linearizable implementations of shared objects. Motivated by the observation that commuting operations can be ex…
Space-Time Trade-off in Bounded Iterated Memory
Guillermo Toyos-Marfurt, Petr Kuznetsov
The celebrated asynchronous computability theorem (ACT) characterizes tasks solvable in the read-write shared-memory model using the unbounded full-information protocol, where in e…
On the Bit Complexity of Iterated Memory
Guillermo Toyos-Marfurt, Petr Kuznetsov
Computability, in the presence of asynchrony and failures, is one of the central questions in distributed computing. The celebrated asynchronous computability theorem (ACT) charact…