How Fast Can a Very Robust Read Be?

• Presented at: 25th ACM Symposium on Principles of Distributed Computing (PODC'06), Denver, Colorado, USA, July 23-26, 2006
• Published in: Proceedings of the 25th ACM Symposium on Principles of Distributed Computing (PODC'06)
• Publication date: 2006

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.

Note: The full version of this paper is available as a EPFL/LPD technical report (LPD-REPORT-2006-008) with the same title.

Keywords: Storage emulations ; Arbitrary failures ; Optimal resilience ; Time-complexity

Reference

• LPD-CONF-2006-033

Record created on 2006-05-19, modified on 2012-03-20