In this report, we suggest that both P2P Content Sharing and Computing can benefit from a unified perspective via distributed data structures with suitably chosen abstract operations. We introduce the generic approach of augmenting distributed data structures. Our approach augments a DHT and builds a prefix trie on node IDs and adds augmenting information to nodes. The augmentation can use any aggregate operator on keys (Max, Min, Sum,etc.).We apply the augmentation approach to introduce a new distributed data structure called a Cone. Cones support a variety of queries to locate resources, such as locating a resource of maximum size or a resource of at least a given size. For a DHT with N nodes and IDs of m bits, queries and updates take an expected-case O(log N) and worst-case O(m) messages.

Pre-2018 CSE ID: CS2003-0755

Failure is inevitable: disks fail, hosts crash, networks partition, applications stop. Consequently, the principal challenge in designing highly-available systems is to tolerate each failure as it occurs and recover from its effects. For large systems, or systems with unreliable components, such failures can cease to be exceptional events, but instead may become the common case. Perhaps no design point is more challenging in this respect than that faced by heterogeneous peer-to-peer systems. Such systems are typically composed of very large numbers of hosts, of which only a minority may be available at any one time. In this environment, failure is not only common, but pervasive. This paper analyzes the challenges and limitations in building a highly-available storage system in such a peer-to-peer environment. In particular, we explore the design requirements on failure tolerance and failure recovery in environments with limited host availability. Our contributions are threefold: First, we provide an analytic model for reasoning about the efficiency of replication and erasure encoding as temporary storage redundancy mechanisms. Second, we extend this framework to model the availability of groups of files or file systems. Finally, we incorporate the costs of maintaining a given level of availability in the long term by recovering from persistent storage failures. We show that even in environments with pervasive failure it is possible to offer a storage service with a high degree of availability at a moderate cost in storage overhead.

Pre-2018 CSE ID: CS2002-0726

In this paper, we propose a new distributed heap-based data structure called Cone. Cone maintains an ordering of key values in a distributed fashion, and can support queries of the form, "Find x resources of size > S." Cone can be built on any routing substrate as long as the substrate supports longest prefix match-based lookups. We describe the Cone data structure, the operations it supports, and its load balancing properties. We have implemented and evaluated Cone on a 1000-node ModelNet emulation platform and a 50-node PlanetLab distributed testbed. We show that Cone has good load-balancing properties and that it is stable and reactive even when there is considerable amount of dynamism in the system.

Pre-2018 CSE ID: CS2004-0782

In this paper, we propose a new approach for designing distributed systems to survive Internet catastrophes called informed replication, and demonstrate this approach with the design and evaluation of a cooperative backup system called the Phoenix Recovery Service. Informed replication uses a model of correlated failures to exploit software diversity. The key observation that makes our approach both feasible and practical is that Internet catastrophes result from shared vulnerabilities. By replicating a system service on hosts that do not have the same vulnerabilities, an Internet pathogen that exploits a vulnerability is unlikely to cause all replicas to fail. To characterize software diversity in an Internet setting, we measure the software diversity of host operating systems and network services in a large organization. We then use insights from our measurement study to develop and evaluate heuristics for computing replica sets that have a number of attractive features. Our heuristics provide excellent reliability guarantees, result in low degree of replication, limit the storage burden on each host in the system, and lend themselves to a fully distributed implementation. We then present the design and prototype implementation of Phoenix, and evaluate it on the PlanetLab testbed.

Pre-2018 CSE ID: CS2005-0816

The effectiveness of a distributed system hinges on the manner in which tasks and data are assigned to the underlying system resources. Moreover, today's large-scale distributed systems must accommodate heterogeneity in both the offered load and in the makeup of the available storage and compute capacity. The ideal resource assignment must balance the utilization of the underlying system against the loss of locality incurred when individual tasks or data objects are fragmented among several servers. In this paper we describe this locality-maximizing placement problem and show that an optimal solution is NP-hard. We then describe a polynomial-time algorithm that generates a placement within an additive constant of two from optimal.

Pre-2018 CSE ID: CS2004-0777

The Internet today is highly vulnerable to \emph{Internet catastrophes}: events in which an exceptionally successful Internet pathogen, like a worm or email virus, causes data loss on a significant percentage of the computers connected to the Internet. In this paper, we explore the feasibility of using data redundancy, a model of dependent host vulnerabilities, and distributed storage to ensure data survives such events. In particular, we motivate the design of a cooperative, peer-to-peer remote backup system called the \Phoenix\ recovery system, and we argue that \Phoenix\ is a compelling architecture for providing a convenient and effective approach for tolerating Internet catastrophes. Our key observation that makes \Phoenix\ both feasible and practical is that an Internet catastrophe, like any large-scale Internet attack, exploits shared vulnerabilities. Hence, the replication mechanism should take the dependencies of host failures---in this case, host diversity---into account. Using a simulation model we show that, by doing informed placement of replicas, \Phoenix\ provide highly reliable and available cooperative backup and recovery with low overhead: with as few as 2 replicas, the system can backup and recover at least the equivalent of 20\% of storage contributed by each host in the system.

Pre-2018 CSE ID: CS2003-0732