On the Time-Complexity of Robust and Amnesic Storage

The authors consider wait-free implementations of a regular read/write register for unauthenticated data using a collection of 3t + k base objects, t of which can be subject to Byzantine failures. They focus on amnesic algorithms that store only a limited number of values in the base objects. In contrast, non-amnesic algorithms store an unbounded number of values, which can eventually lead to problems of space exhaustion. Lower bounds on the time-complexity of read and write operations are currently met only by non-amnesic algorithms. In this paper, they show for the first time that amnesic algorithms can also meet these lower bounds.