2018 Mirza Ahad Baig’s internship

In 2000 Jayanti et al. proved a linear lower bound on the worst-case step complexity of fault-tolerant implementations, from read and write operations,  of a large class of concurrent objects. This class includes widely-used objects like counters and  snapshots. Since then several papers have tried to circumvent the lower bound, either by restricting the use of the objects (e.g. bounding the number of times the counter can be incremented), by weakening their semantics or by using stronger synchronization primitives/ randomization.

Previous work left open the question of finding deterministic counter and snapshot implementations with sub-linear amortized step complexity. This question was partially answered during this internship. In particular, we got the first wait-free counter, implemented using only read and write operations, whose amortized operation step complexity is poly-logarithmic in all executions. This is the first non-blocking read/write counter algorithms that provides poly-logarithmic step complexity in executions of arbitrary length. Non-blocking algorithms ensure some progress of the computation even in presence of processes failures. In particular, our algorithm ensures that every process that does not fail completes its operations on the counter in a finite number of its steps. We also prove a logarithmic lower bound on the amortized step complexity of obstruction-free counter implementations of arbitrary length, thus showing that our upper bound is not far from being optimal.