On liveness of dynamic storage

DOI10.1007/978-3-319-72050-0_21MaRDI QIDQ1742792zbMATH OpenOpenAlexFDO

Authors Alexander Spiegelman, Idit Keidar

Publication date 12 April 2018

Full work available at URL https://arxiv.org/abs/1507.07086

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Abstract: Dynamic distributed storage algorithms such as DynaStore, Reconfigurable Paxos, RAMBO, and RDS, do not ensure liveness (wait-freedom) in asynchronous runs with infinitely many reconfigurations. We prove that this is inherent for asynchronous dynamic storage algorithms, including ones that use $Omega$ or $diamondS$ oracles. Our result holds even if only one process may fail, provided that machines that were successfully removed from the system's configuration may be switched off by an administrator. Intuitively, the impossibility relies on the fact that a correct process can be suspected to have failed at any time, i.e., its failure is indistinguishable to other processes from slow delivery of its messages, and so the system should be able to reconfigure without waiting for this process to complete its pending operations. To circumvent this result, we define a dynamic eventually perfect failure detector, and present an algorithm that uses it to emulate wait-free dynamic atomic storage (with no restrictions on reconfiguration rate). Together, our results thus draw a sharp line between oracles like $Omega$ and $diamondS$, which allow some correct process to continue to be suspected forever, and a dynamic eventually perfect one, which does not.

Recommendations

• Reconfigurable distributed storage for dynamic networks
• Dynamic atomic storage without consensus
• Dynamic atomic storage without consensus
• Dynamic reconfiguration: a tutorial
• Dynamic reconfiguration: abstraction and optimal asynchronous solution

Cited in

(6)

• Asynchronous reconfiguration with Byzantine failures
• Dynamic atomic storage without consensus
• Dynamic reconfiguration: a tutorial
• Asynchronous reconfiguration with Byzantine failures
• Dynamic Byzantine reliable broadcast
• Reconfigurable distributed storage for dynamic networks

This page was built for publication: On liveness of dynamic storage

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1742792)