
Research
Abstracts  2007 
Scalefree Routing SchemesFrans Kaashoek & Petar MaymounkovThe ProblemAfter almost a decade of research the P2P community has not yet achieved its primary goal of building a P2P system that implements a "useful" application (e.g. WWW) or data structure (e.g. hash table) and, at the same time, guarantees system and user "safety". Usefulness or safety are currently achievable in isolation, but not together. P2P systems are, by definition, largescale distributed systems comprised of mostlyindependent participants which are allowed to join or leave at will. This freedom of user behavior makes P2P systems very susceptible to impersonation attacks, known as Sybil Attacks. To resist impersonation attacks, a P2P system must abide by a simple rule: All communication in the system should occur only between pairs of nodes that are "friends" in the physical world. This rule imposes severe combinatorial constraints on distributed algorithms that can run on P2P systems while maintaining system "safety". We have established that a variety of useful data structures can be implemented on a P2P system, contingent on the existence of a "scalefree routing scheme". A routing scheme assigns a routing table and a label to each vertex of the network connetivity graph, such that local forwarding decisions can be made based on the current vertex's routing table and the destination vertex's label. A scalefree routing scheme additionally requires that:
Our reseach is concerned with the theoretical aspects (existence, lower bounds, and algorithms) of scalefree routing schemes, as well as the implementational aspects of the corresponding P2P systems. Research AgendaScalefree routing schemes are "harder" than classiscal ones since they have more stringent requirements. Existing lowerbound techniqes (like the ones of Thorup and Zwick "Approximate Distance Oracles" STOC'01) based on Erdös' girth conjecture of 1963 are not applicable. We are thus investigating new combinatorial methods for derving such bounds. The design of incremental algorithms also calls for techniques that deviate from the classical ones. Existing literature, e.g. Thorup and Zwick "Compact Routing Schemes" SPAA'01, uses heavilycombinatorial methods and data structures which do not seem amenable to incremental computation. To tackle this problem we have explored a few fruitful directions in the emerging field of Geometric Routing and Greedy Metric Embeddings. 

