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. Journal articles
  4. The Collective Memory of Amnesic Processes
 
research article

The Collective Memory of Amnesic Processes

Guerraoui, Rachid  
•
Levy, Ron R.
•
Pochon, Bastian
Show more
2008
ACM Transactions on Algorithms (TALG)

This paper considers the problem of robustly emulating a shared atomic memory over a distributed message passing system where processes can fail by crashing and possibly recover. We revisit the notion of atomicity in the crash-recovery context and introduce a generic algorithm that emulates an atomic memory. The algorithm is instantiated for various settings according to whether processes have access to local stable storage, and whether, in every execution of the algorithm, a sufficient number of processes are assumed not to crash. We establish the optimality of specific instances of our algorithm in terms of resilience, log-complexity (number of stable storage accesses needed in every read or write operation), as well as time-complexity (number of communication steps needed in every read or write operation). The paper also discusses the impact of considering a multi-writer versus a single-writer memory, as well as the impact of weakening the consistency of the memory, by providing safe or regular semantics instead of atomicity.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

crash_recovery.pdf

Access type

openaccess

Size

309.4 KB

Format

Adobe PDF

Checksum (MD5)

7a3ecaab885714d0d7378caa1a2811ee

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