Lucky Read/Write Access to Robust Atomic Storage

This paper establishes tight bounds on the best-case time-complexity of distributed atomic read/write storage implementations that tolerate 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 fail by crashing. We define a {\em lucky} operation (read or write) as one that runs synchronously and without contention. 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$.