Stanford InfoLab Publication Server

Butterflies and Peer-to-Peer Networks

Datar, Mayur (2002) Butterflies and Peer-to-Peer Networks. Technical Report. Stanford.

WarningThere is a more recent version of this item available.



The popularity of systems like Napster, Gnutella etc. have spurred recent interest in Peer-to-peer systems. A central problem in all these systems is efficient location of resources based on their keys. A network that supports such queries is referred to as Content Addressable Network (CAN). Many solutions have been proposed to building CANs. However most of these solutions do not focus on adversarial faults, which might be critical to building a censorship resistant peer-to-peer system. In a recent paper Fiat and Saia have proposed a solution to building such a system. We propose a new solution based on multi-butterflies that improves upon the previous solution by Fiat and Saia. Our new network, {\bf multi-hypercube}, is a fault tolerant version of hypercube. We also demonstrate how this network can be maintained dynamically. This addresses the first open problem in the paper by Fiat and Saia.

Item Type:Techreport (Technical Report)
Uncontrolled Keywords:Multi-butterflies, P2P Networks, Fault Tolerance.
Subjects:Computer Science > Distributed Systems
Related URLs:Project Homepage
ID Code:566
Deposited By:Import Account
Deposited On:27 Jan 2002 16:00
Last Modified:25 Dec 2008 08:59

Available Versions of this Item

Download statistics

Repository Staff Only: item control page