Algorithms for managing data in distributed systems

This dissertation describes provably good algorithms for two fundamental problems in the area of data management far distributed systems: attack-resistance and data migration.; The first major problem addressed is that of attack-resistance. We describe the first fully distributed, scalable, attack-resistant peer-to-peer network. The network is attack-resistant in the sense that even when a constant fraction of the nodes in the network are deleted or controlled by an adversary, an arbitrarily large fraction of the remaining nodes can access an arbitrarily large fraction of the data items. Furthermore, the network is scalable in the sense that time and space resource bounds grow poly-logarithmically with the number of nodes in the network. We also describe a scalable peer-to-peer network that is attack-resistant in a highly dynamic environment: the network remains robust even after all of the original nodes in the network have been deleted by the adversary, provided that a larger number of new nodes have joined the network.; The second major problem addressed in this dissertation is that of data migration. The data migration problem is the problem of computing an efficient plan for moving data stored on devices in a network from one configuration to another. We first consider the case where the network topology is complete and all devices have the same transfer speeds. For this case, we describe polynomial time algorithms for finding a near-optimal migration plan when a certain number of additional nodes is available as temporary storage. We also describe a 3/2-approximation algorithm for the case where such nodes are not available. We empirically evaluate our algorithms for this problem and find they perform much better in practice than the theoretical bounds suggest. Finally, we describe several provably good algorithms for the more difficult case where the network topology is not complete and where device speeds are variable.