"Indestructible Networks and Storage" Today's data networks are an engineering triumph, optimized over decades to give efficient, reliable delivery of data in normal times. The net has been given the capacity to handle surges and the robustness to deal with occasional failures. But in more hostile environments, where links, network nodes, and endpoints may be crashing more frequently, we must adopt new ideas that spend some of the spare capacity to provide greater resiliency and rapidly respond to changing conditions. One key idea is to add an element of randomness to routing, so that in addition to sending packets along the current best path to their destination, the network sends scout packets along alternate paths, capturing information that allows a rapid response if the main path is lost. Scout packets do not have global knowledge of the network topology. Rather they follow round-trip-time (RTT) trails left by previous scout packets, if any, and leave a trail of updated RTT information. Simulations indicate that this reduces packet drops by a factor of up to 38 in congested networks relative to OSPF. This is quite distinct from the overlay network approaches others have considered for robustness, and improves the underlying network directly. Our technique does require extra state in the routers beyond the current routing tables, but adds only a modest computational burden. Once network connectivity is assured, we have to consider preserving the information stored in the network. The normal approach is to replicate data in a small number of fixed locations. This is adequate in the face of mistakes and accidents. However, in the face of wide catastrophes or targeted attacks this approach is much more fragile. Instead we propose a system that is capable of withstanding heavy damage without losing data. We add an element of randomness to the storage locations. Think of computer viruses as involutary sharing. They diffuse through computer networks, carrying copies of themselves, and sometimes other files, through the network. They essentially define their own networks, moving from computer to computer via email, web server bugs, etc. We propose a voluntary virus, one that a user must subscribe to. A user devotes some portion of his memory to the collaborative storage facility. At a random interval, the user's machine will send either a randomly chosen file from his piece of the common storage or a file he needs replicated to one or more other participating machines. Each message will also carry the addresses of some participating machines. Thus files will diffuse through the network in a cloud radiating from the source. Searches radiate out in a similar manner though at a faster pace. The percentage a system gets of the common storage depends on what we choose for distribution rates, the percentage of local files vs public files transmitted, and the number of systems broadcast to. We provide rough guarantees of replication, limits for search times, and policing of users to avoid any one overrunning the system by means such as asking for occasional proof of holding data by computing a hash of a challenge and the data, setting entrance requirements like the ones that led to the growth of BITNET, and caching "breadcrumbs" to assist locating files. Without flooding the network, it is almost impossible to destroy a file, and flooding is detectable in enough time to take countermeasures. participants list so far: Anindya Basu Eran Gabber Eric Grosse Nick Maxemchuk Dave Presotto Mark Smith