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$.

Published in:
IEEE International Conference on Dependable Systems and Networks (DSN '06)
Presented at:
IEEE International Conference on Dependable Systems and Networks (DSN '06), Philadelphia, PA, USA, June 25-28, 2006.
Year:
2006
Keywords:
Laboratories:

Note: The status of this file is: Anyone