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. Amnesic Distributed Storage
 
conference paper

Amnesic Distributed Storage

Chockler, Gregory
•
Guerraoui, Rachid  
•
Keidar, Idit
2007
Proceedings of the 21st International Symposium on Distributed Computing (DISC'07)

Distributed storage algorithms implement the abstraction of a shared register over distributed base objects. We study a specific class of storage algorithms, which we call amnesic: these have the pragmatic property that old values written in the implemented register might be eventually forgotten, i.e., they are not permanently kept in the storage and might be overwritten in the base objects by more recent values. This paper precisely captures this property and argues that most storage algorithms are amnesic. We establish a fundamental impossibility of an amnesic storage algorithm to implement a robust register abstraction over a set of base objects of which at least one can fail arbitrarily, even if only in a responsive manner, unless readers are allowed to write to the base objects. Our impossibility helps justify the assumptions made by practical robust storage algorithms. We also derive from this impossibility the first sharp distinction between safe and regular registers. Namely, we show that, if readers do not write, then no amnesic algorithm can implement a regular register using safe registers.

  • Files
  • Details
  • Metrics
Type
conference paper
Author(s)
Chockler, Gregory
Guerraoui, Rachid  
Keidar, Idit
Date Issued

2007

Published in
Proceedings of the 21st International Symposium on Distributed Computing (DISC'07)
Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCL  
Available on Infoscience
July 24, 2007
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/9829
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