Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. The complexity of robust atomic storage
 
conference paper

The complexity of robust atomic storage

Dobre, Dan
•
Guerraoui, Rachid  
•
Majuntke, Matthias
Show more
2011
Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing - PODC '11
the 30th annual ACM SIGACT-SIGOPS symposium

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.

  • Files
  • Details
  • Metrics
Type
conference paper
DOI
10.1145/1993806.1993816
Author(s)
Dobre, Dan
Guerraoui, Rachid  
Majuntke, Matthias
Suri, Neeraj
Vukolić, Marko
Date Issued

2011

Publisher

ACM Press

Publisher place

New York, New York, USA

Published in
Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing - PODC '11
Start page

59

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCL  
Event nameEvent placeEvent date
the 30th annual ACM SIGACT-SIGOPS symposium

San Jose, California, USA

06-08 06 2011

Available on Infoscience
June 12, 2015
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/115073
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés