Reconfigurable Distributed Storage for Dynamic Networks

Gregory Chockler, Seth Gilbert, Vincent Gramoli, Peter Musial, Alex Shvartsman

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


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
Title of host publicationProceedings of the 9th International Conference on Principles of Distributed Systems (OPODIS '05)
Number of pages15
ISBN (Electronic)978-3-540-36322-4
ISBN (Print)978-3-540-36321-7
Publication statusPublished - 2005
Event 9th International Conference on Principles of Distributed Systmes (OPODIS '05) - Pisa, Italy
Duration: 11 Dec 200513 Dec 2005

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
ISSN (Print)0302-9743


Conference 9th International Conference on Principles of Distributed Systmes (OPODIS '05)


  • Distributed algorithms
  • reconfiguration
  • atomic objects
  • performance

Cite this