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. Conferences, Workshops, Symposiums, and Seminars
  4. Lucky Read/Write Access to Robust Atomic Storage
 
conference paper

Lucky Read/Write Access to Robust Atomic Storage

Guerraoui, Rachid  
•
Levy, Ron R.
•
Vukolic, Marko
2006
IEEE International Conference on Dependable Systems and Networks (DSN '06)
IEEE International Conference on Dependable Systems and Networks (DSN '06)

This paper establishes tight bounds on the \emph{best-case} time-complexity of distributed atomic read/write storage implementations that tolerate \emph{worst-case} conditions. We study asynchronous robust implementations where a writer and a set of reader processes (clients) access an atomic storage implemented over a set of $2t+b+1$ server processes of which $t$ can fail: $b$ of these can be malicious and the rest can crash. We define a lucky operation (read or write) as one that runs synchronously and without contention. It is often argued in practice that lucky operations are the most frequent. We determine the exact conditions under which a {\em lucky} operation can be {\em fast}, namely expedited in one-communication round-trip with no data authentication. We show that every \emph{lucky} write (resp., read) can be \emph{fast} despite $f_w$ (resp., $f_r$) actual failures, if and only if $f_w + f_r \leq t - b$.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

lucky-dsn06.pdf

Access type

openaccess

Size

209.68 KB

Format

Adobe PDF

Checksum (MD5)

75b8f01d7c3ab44f66e55300351d9055

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