SkipNet: A Scalable Overlay Network with Practical Locality Properties

Scalable overlay networks such as Chord, Pastry, and Tapestry have
recently emerged as flexible infrastructure for building large
peer-to-peer systems. In practice, two disadvantages of such systems
are that it is difficult to control where data is stored and difficult
to guarantee that routing paths remain within an administrative
domain. SkipNet is a scalable overlay network that provides
controlled data placement and routing locality guarantees by
organizing data primarily by lexicographic key ordering. SkipNet also
allows for both fine-grained and coarse-grained control over data
placement, where content can be placed either on a pre-determined node
or distributed uniformly across the nodes of a hierarchical naming
subtree. An additional useful consequence of SkipNet's locality
properties is that partition failures, in which an entire organization
disconnects from the rest of the system, result in two disjoint, but
well-connected overlay networks.

Marvin Theimer received a PhD in Computer Science from Stanford
University in 1986. He then spent two years with the QuickSilver
distributed operating system project at IBM's Almaden Research Center.
Following that, he spent almost ten years at Xerox's Palo Alto Research
Center exploring the topics of ubiquitous computing and
weakly-consistent, replicated systems. He is currently a Senior
Researcher at Microsoft Research, exploring topics in Internet
infrastructure and peer-to-peer computing.