Home > Research > Publications & Outputs > The complexity of robust atomic storage

Research

Associated organisational units

Links

Text available via DOI:

Keywords

View graph of relations

The complexity of robust atomic storage

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review

Published

Standard

The complexity of robust atomic storage. / Dobre, D.; Guerraoui, R.; Majuntke, M. et al.
PODC '11 Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing. ACM, 2011. p. 59-68.

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review

Harvard

Dobre, D, Guerraoui, R, Majuntke, M, Suri, N & Vukolić, M 2011, The complexity of robust atomic storage. in PODC '11 Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing. ACM, pp. 59-68. https://doi.org/10.1145/1993806.1993816

APA

Dobre, D., Guerraoui, R., Majuntke, M., Suri, N., & Vukolić, M. (2011). The complexity of robust atomic storage. In PODC '11 Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing (pp. 59-68). ACM. https://doi.org/10.1145/1993806.1993816

Vancouver

Dobre D, Guerraoui R, Majuntke M, Suri N, Vukolić M. The complexity of robust atomic storage. In PODC '11 Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing. ACM. 2011. p. 59-68 doi: 10.1145/1993806.1993816

Author

Dobre, D. ; Guerraoui, R. ; Majuntke, M. et al. / The complexity of robust atomic storage. PODC '11 Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing. ACM, 2011. pp. 59-68

Bibtex

@inproceedings{add3e29e114042bfb8de5e0a01673a0d,
title = "The complexity of robust atomic storage",
abstract = "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. {\textcopyright} 2011 ACM.",
keywords = "Arbitrary failures, Lower bounds, Optimal resilience, Storage emulations, Time-complexity, Data authentication, Fault-prone, Message passing systems, Read operation, Storage component, Time-optimal, Write operations, Message passing, Optimization, Atoms",
author = "D. Dobre and R. Guerraoui and M. Majuntke and Neeraj Suri and M. Vukoli{\'c}",
year = "2011",
month = jun,
day = "6",
doi = "10.1145/1993806.1993816",
language = "English",
isbn = "9781450307192",
pages = "59--68",
booktitle = "PODC '11 Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing",
publisher = "ACM",

}

RIS

TY - GEN

T1 - The complexity of robust atomic storage

AU - Dobre, D.

AU - Guerraoui, R.

AU - Majuntke, M.

AU - Suri, Neeraj

AU - Vukolić, M.

PY - 2011/6/6

Y1 - 2011/6/6

N2 - 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. © 2011 ACM.

AB - 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. © 2011 ACM.

KW - Arbitrary failures

KW - Lower bounds

KW - Optimal resilience

KW - Storage emulations

KW - Time-complexity

KW - Data authentication

KW - Fault-prone

KW - Message passing systems

KW - Read operation

KW - Storage component

KW - Time-optimal

KW - Write operations

KW - Message passing

KW - Optimization

KW - Atoms

U2 - 10.1145/1993806.1993816

DO - 10.1145/1993806.1993816

M3 - Conference contribution/Paper

SN - 9781450307192

SP - 59

EP - 68

BT - PODC '11 Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing

PB - ACM

ER -