2 Pastry and the P2P Applications based on It

What is Pastry?

A structured P2P network that supports object location and routing.

What is the routing efficiency of Pastry?

O(log N) routing hops.

What is the size of Pastry's routing table?

O(log N).

What is the purpose of Pastry's leaf set?

To store the |L| closest peers in ID space.

What is the purpose of Pastry's neighborhood set?

To store the |M| closest nodes in IP space.

How does Pastry's locality awareness work?

It maintains a neighborhood set of the closest nodes by proximity measure.

How is locality maintained in Pastry's routing table?

Entries are chosen to be as close as possible in IP space while still satisfying shared prefix requirements.

How does Pastry handle node arrival?

Routes a join message to the node with the closest ID.

What happens when a node joins Pastry?

All nodes on the route return their state to the joining node.

How does Pastry handle node failure?

It repairs the leaf set by contacting the live node with the largest index on the side of the failed node.

How does Pastry repair the routing table after node failure?

Contacts other nodes on the same row or the next row to find a replacement node.

How does Pastry repair the neighborhood set after node failure?

Checks with live neighbors for other close nodes.

How does Pastry handle fault tolerance and malicious peers?

Randomly chooses between nodes satisfying routing protocol criteria to avoid bad nodes.

What is the expected routing performance of Pastry?

O(log N).

What is PAST?

A P2P archival storage utility built on Pastry.

What is the purpose of PAST?

To exploit the multitude of Internet nodes to achieve strong persistence and high availability for global storage.

What are the key characteristics of PAST?

Large-scale

What is SCRIBE?

A P2P multicast system built on Pastry.

What is the purpose of SCRIBE?

To enable efficient many-to-many communication in P2P networks.

What is SplitStream?

A P2P live streaming system built on Pastry and SCRIBE.

How does SplitStream improve on single tree multicast?

It divides the stream into stripes

What is the benefit of SplitStream's approach?

All nodes contribute

What is the worst-case routing performance of Pastry?

Linear to N.

How does Pastry ensure data availability?

It replicates data across multiple nodes.