Abstract
We suggest a file storage system for a dynamic environment where servers may join and leave the system. Our construction has a \(O(\sqrt{n})\) write complexity, \(O(\sqrt{n}\log{n})\) read complexity and a constant data blowup-ratio, where n represents the number of processors in the network. Our construction is fault-tolerant against an adversary that can crash θ(n) processors of her choice while having slightly less adaptive queries than the reader.
When both the reader and the adversary are nonadaptive we derive lower bounds on the read complexity, write complexity and data blowup ratio. We show these bounds are tight using a simple storage system construction, based on an ε-intersecting quorum system.
Research supported by a grant from the Israel Science Foundation
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abraham, I., Malkhi, D.: Probabilistic quorums for dynamic systems. In: Fich, F.E. (ed.) DISC 2003. LNCS, vol. 2848, pp. 60–74. Springer, Heidelberg (2003)
Alvisi, L., Malkhi, D., Pierce, E., Reiter, M., Wright, R.: Dynamic Byzantine Quorum Systems. Dependable Systems and Networks(DSN) (2000)
Fiat, A., Saia, J.: Censorship resistant peer-to-peer content addressable networks. In: SODA 2002 (2002)
Kaashoek, F., Karger, D.R.: Koorde, a simple degree optimal hash table. In: Kaashoek, M.F., Stoica, I. (eds.) IPTPS 2003. LNCS, vol. 2735, Springer, Heidelberg (2003)
Katz, J., Trevisan, L.: On the efficiency of local decoding procedures for errorcorrecting codes. In: Proc. STOC 2000 (2000)
Malkhi, D., Naor, M., Ratajczak, D.: Viceroy, a Scalable and dynamic emulation of the buterfly. In: Proc. PODC 2002 (2002)
Malkhi, D., Reiter, M.: Byzantine Quorum Systems. The Journal of Distributed Computing 11(4) (1998)
Malkhi, D., Reiter, M., Wright, R.: Probabilistic quorum systems. In: PODC 1997 (1997)
Malkhi, D., Reiter, M., Wool, A., Wright, R.: Probabilistic Byzantine Quorum Systems. In: Proc. PODC 1998 (1998)
Naor, M., Roth, R.: Optimal File Sharing in Distributed Networks. SIAM J. Comput. (1995)
Naor, M., Wieder, U.: Novel architectures for p2p applications: the continuousdiscrete approach. In: Proc. SPAA 2003 (2003)
Naor, M., Wieder, U.: A Simple fault-tolerant Distributed Hash Table. In: Kaashoek, M.F., Stoica, I. (eds.) IPTPS 2003. LNCS, vol. 2735, Springer, Heidelberg (2003)
Naor, M., Wieder, U.: Scalable and dynamic quorum systems. In: Proc. PODC 2003 (2003)
Naor, M., Wool, A.: The load capacity and availability of quorum systems. SIAM J. on Computing (April 1998)
Ratnasamy, S., Francis, P., Handley, M., Karp, R., Shenker, S.: A scalable content addressable network. In: Proc ACM SIGCOMM 2001 (2001)
Rabin, M.O.: Efficient dispersal of information for security, load balancing, and fault tolerance. J. ACM 36 (1989)
Stoica, R., Morris, D., Karger, M.F., Kaashoek, H.: Balakrishnan, Chord: a scalable peer-to-peer lookup service for internet applications. In: ACM SIGCOMM 2001 (2001)
Zhao, B.Y., Kubiatowicz, Z.: Tapestry: An infrastructure for fault-tolerant widearea location and routing. Technical Report UCB CSD 01-1141 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nadav, U., Naor, M. (2004). Fault-Tolerant Storage in a Dynamic Environment. In: Guerraoui, R. (eds) Distributed Computing. DISC 2004. Lecture Notes in Computer Science, vol 3274. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30186-8_28
Download citation
DOI: https://doi.org/10.1007/978-3-540-30186-8_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23306-0
Online ISBN: 978-3-540-30186-8
eBook Packages: Springer Book Archive