Fault-Tolerant Storage in a Dynamic Environment



This paper considers distributed storage systems in faulty environments where servers join and leave the system dynamically. The fault model examined is adversarial, where faults may be malicious. First, we derive lower bounds on the read complexity, write complexity and storage blowup ratio in fault-tolerant systems with nonadaptive retrieval. Next, we consider a model in which the retrieval algorithm is slightly more powerful than the adversary in the adaptive nature of the queries. We come up with a system which tolerates a number of adversarial faults linear in the size of the network, while keeping a constant storage blowup ratio. We show a storage system where the retrieval complexity is dynamically adjusted to the number of faults so that it does not exceed $\sqrt{t}$, where $t$ is the number of actual faults. Last we propose an adaptation to a dynamic environment, yielding also an optimal dynamic quorum system.