Ecole d'ingénieur et centre de recherche en Sciences du numérique

The complexity of robust atomic storage

Dobre, Dan; Guerraoui, Rachid; Majuntke, Matthias; Suri, Neeraj; Vukolic, Marko

PODC 2011, 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, June 6-8, 2011, San Jose, CA, USA

We study the time-complexity of robust atomic read/write storage from fault-prone storage components in asynchronous message-passing systems. Robustness here means wait-free tolerating the largest possible number t of Byzantine storage component failures (optimal resilience) without relying on data authentication. We show that no single-writer multiple-reader (SWMR) robust atomic storage implementation exists if (a) read operations complete in less than four communication round-trips (rounds), and (b) the time-complexity of write operations is constant. More precisely, we present two lower bounds. The first is a read lower bound stating that three rounds of communication are necessary to read from a SWMR robust atomic storage. The second is a write lower bound, showing that (log(t)) write rounds are necessary to read in three rounds from such a storage. Applied to known results, our lower bounds close a fundamental gap: we show that time-optimal robust atomic storage can be obtained using well-known transformations from regular to atomic storage and existing time-optimal regular storage implementations.

Document Doi Bibtex

Titre:The complexity of robust atomic storage
Mots Clés:Lower bounds, Storage emulations, Arbitrary failures, Optimal resilience, Time-complexity
Type:Conférence
Langue:English
Ville:San Jose
Pays:ÉTATS-UNIS
Date:
Département:Sécurité numérique
Eurecom ref:3458
Copyright: © ACM, 2011. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in PODC 2011, 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, June 6-8, 2011, San Jose, CA, USA http://dx.doi.org/10.1145/1993806.1993816
Bibtex: @inproceedings{EURECOM+3458, doi = {http://dx.doi.org/10.1145/1993806.1993816 }, year = {2011}, title = {{T}he complexity of robust atomic storage}, author = {{D}obre, {D}an and {G}uerraoui, {R}achid and {M}ajuntke, {M}atthias and {S}uri, {N}eeraj and {V}ukolic, {M}arko}, booktitle = {{PODC} 2011, 30th {A}nnual {ACM} {SIGACT}-{SIGOPS} {S}ymposium on {P}rinciples of {D}istributed {C}omputing, {J}une 6-8, 2011, {S}an {J}ose, {CA}, {USA}}, address = {{S}an {J}ose, {\'{E}}{TATS}-{UNIS}}, month = {06}, url = {http://www.eurecom.fr/publication/3458} }
Voir aussi: