How Fast Can a Very Robust Read Be?

This paper studies the time complexity of reading unauthenticated data from a distributed storage made of a set of failure-prone base objects. More specifically, we consider the abstraction of a robust read/write storage that provides wait-free access to unauthenticated data over a set of base storage objects with $t$ possible failures, out of which at most $b$ are arbitrary and the rest are simple crash failures. We prove a $2$ communication round-trip lower bound for reading from a {\em safe} storage that uses at most $2t+2b$ base objects, independently of the number or round-trips needed by the writer. We then prove the lower bound tight by exhibiting a {\em regular} storage that uses $2t+b+1$ base objects (optimal resilience) and features $2$ communication round-trips for both read and write operations.

Elements of this paper appear in a paper with the same title in the Proceedings of the 25th ACM Symposium on Principles of Distributed Computing (PODC'06), 2006.

 Record created 2006-05-08, last modified 2018-01-27

External link:
Download fulltext
Rate this document:

Rate this document:
(Not yet reviewed)