Paper Info
Title
Lucky Read/Write Access to Robust Atomic Storage
Abstract
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 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 lucky operation can be fast, namely expedited in onecommunication round-trip with no data authentication. We show that every lucky write (resp., read) can be fast despite fw(resp., fr) actual failures, if and only if fw + fr \lt t-b.
Year
DOI
Venue
2006
10.1109/DSN.2006.50
DSN
Keywords
Field
DocType
data authentication,write access,lucky operation,lt t-b,actual failure,atomic read,storage implementation,asynchronous robust implementation,optimal resilience,atomic storage,time-complexity.,best-case time-complexity,lucky read,shared-memory emulations,robust atomic storage,arbitrary failures,exact condition,artificial intelligence,distributed algorithms,communication channels,distributed computing,authentication,computational complexity,time measurement,shared memory,time complexity,resilience,robustness
Authentication,Computer science,Computer network,Real-time computing,Robustness (computer science),If and only if,Time complexity,Distributed computing,Asynchronous communication,Communication channel,Distributed algorithm,Operating system,Computational complexity theory
Conference
ISSN
ISBN
Citations 
1530-0889
0-7695-2607-1
11
PageRank 
References 
Authors
0.56
18
3
Name
Order
Citations
PageRank
Rachid Guerraoui16364430.90
Ron R. Levy21307.03
Marko Vukolić350432.42