Home > Research > Publications & Outputs > On the time-complexity of robust and amnesic st...

Links

Text available via DOI:

View graph of relations

On the time-complexity of robust and amnesic storage

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSNChapter

Published
Close
Publication date2008
Host publicationPrinciples of Distributed Systems: 12th International Conference, OPODIS 2008, Luxor, Egypt, December 15-18, 2008. Proceedings
PublisherSpringer
Pages197-216
Number of pages20
Volume5401 LNCS
ISBN (electronic)9783540922216
ISBN (print) 9783540922209
<mark>Original language</mark>English

Abstract

We 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. We 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, we show for the first time that amnesic algorithms can also meet these lower bounds. We do this by giving two amnesic constructions: for k∈=∈1, we show that the lower bound of two communication rounds is also sufficient for every read operation to complete and for k∈=∈t∈+∈1 we show that the lower bound of one round is also sufficient for every operation to complete. © 2008 Springer Berlin Heidelberg.