Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Reports, Documentation, and Standards
  4. How Fast Can a Very Robust Read Be?
 
report

How Fast Can a Very Robust Read Be?

Guerraoui, Rachid  
•
Vukolic, Marko
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.

  • Files
  • Details
  • Metrics
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés