Reconfigurable distributed storage for dynamic networks

Gregory Chockler, Seth Gilbert, Vincent Gramoli, Peter M. Musial, Alex A. Shvartsman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


This paper presents a new algorithm, RDS (Reconfigurable Distributed Storage), for implementing a reconfigurable distributed shared memory in an asynchronous dynamic network. The algorithm guarantees atomic consistency (linearizability) in all executions in the presence of arbitrary crash failures of processors and message loss and delays. The algorithm incorporates a quorum-based read/write algorithm and an optimized consensus protocol, based on Paxos. RDS achieves the design goals of: (i) allowing read and write operations to complete rapidly, and (ii) providing long-term fault tolerance through reconfiguration, a process that evolves the quorum configurations used by the read and write operations. The new algorithm improves on previously developed alternatives by using a more efficient reconfiguration protocol, thus guaranteeing better fault tolerance and faster recovery from network instability. This paper presents RDS, a formal proof of correctness, conditional performance analysis, and experimental results.

Original languageEnglish (US)
Title of host publicationPrinciples of Distributed Systems - 9th International Conference, OPODIS 2005, Revised Selected Papers
Number of pages15
StatePublished - 2006
Externally publishedYes
Event9th International Conference on Principles of Distributed Systems, OPODIS 2005 - Pisa, Italy
Duration: Dec 12 2005Dec 14 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3974 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference9th International Conference on Principles of Distributed Systems, OPODIS 2005


  • Atomic objects
  • Distributed algorithms
  • Performance
  • Reconfiguration

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Reconfigurable distributed storage for dynamic networks'. Together they form a unique fingerprint.

Cite this