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.

Published in:
Proceedings of the 25th ACM Symposium on Principles of Distributed Computing (PODC'06)
Presented at:
25th ACM Symposium on Principles of Distributed Computing (PODC'06), Denver, Colorado, USA, July 23-26, 2006
The full version of this paper is available as a EPFL/LPD technical report (LPD-REPORT-2006-008) with the same title.

Note: The status of this file is: Anyone

 Record created 2006-05-19, last modified 2020-10-25

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)