Tapestry Algorithm for a P2P Network

Group Member Names -

Nihal Mishra

Abhishek Jaimini

Steps to run code on Windows 10

Run with Escript (Recommended)

1. Open Terminal
2. cd p2p-Tapestry
3. Generate executable with mix escript.build
4. Run with escript ./tapestry numNodes numRequests
5. For Bonus part, run with escript ./tapestry numNodes numRequests failure-percentage

Run with Mix

mix run project3.exs numNodes numRequests

Bonus - mix run project3.exs numNodes numRequests failure-percentage

Tapestry Algorithm

Tapestry is a peer-to-peer overlay network which provides a distributed hash table, routing, and multicasting infrastructure for distributed applications. The Tapestry peer-to-peer system offers efficient, scalable, self-repairing, location-aware routing to nearby resources.

Peer-to-Peer overlay networks can be used to provide many useful services. The goal of this project is to implement in Elixir using the actor model the Tapestry Algorithm and a simple object access service to prove its usefulness. The specification of the Tapestry protocol can be found in the paper -

Tapestry: A Resilient Global-Scale Overlay for Service Deployment by Ben Y. Zhao, Ling Huang, Jeremy Stribling, Sean C. Rhea, Anthony D. Joseph and John D. Kubiatowicz.

Link to the paper: https://pdos.csail.mit.edu/~strib/docs/tapestry/tapestry_jsac03.pdf

Wikipedia page: https://en.wikipedia.org/wiki/Tapestry_(DHT)

What is working

Tapestry algorithm has been implemented over a network of nodes generated by using the Elixir Actor Model, where every actor (GenServer) acts a node in the system. We iteratively add nodes to the system, generate a hexadecimal hash for it and populate its routing table.

Then the routing is done by choosing each node as source and randomly selecting another node as destination. We use the lookup table to find the intermediate node for the hop by computing its closest reachable node to the destination node. The route terminates when the destination node is reached and it stores the number of hops that the route took to reach the destination node, in a global datastore. This process repeats for every node numRequests number of times. Finally we print the maximum number of hops among all requests for all routes.

Largest network handled

Largest network size that we could handle was of 9999 nodes and 10 requests.