loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
International Conference on Dependable Systems and Networks (DSN'06)
Lucky Read/Write Access to Robust Atomic Storage
Philadelphia, Pennsylvania
June 25-June 28
ISBN: 0-7695-2607-1
Rachid Guerraoui, MIT, Cambridge, MA
Ron R. Levy, EPFL, CH-1015 Lausanne, Switzerland
Marko Vukolic, EPFL, CH-1015 Lausanne, Switzerland
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.
Citation:
Rachid Guerraoui, Ron R. Levy, Marko Vukolic, "Lucky Read/Write Access to Robust Atomic Storage," dsn, pp.125-136, International Conference on Dependable Systems and Networks (DSN'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.