# Tulip Overlay

This is the approved revision of this page, as well as being the most recent.

Tulip is a distributed, decentralized, P2P network intended for routing, searching and publish-lookup information sharing. It is a structured P2P network very much like Chord, Pastry, Tapestry and CAN.

## Overview

In Tulip protocol, a network with $n$ nodes uses $O(\sqrt{n}log n)$ space per node. Tulip guarantees a 2-hop optimal routing with a stretch of 2 over optimal routing, based on the assumption of the triangle inequality.

### Tulip Construction

Tulip defines the vicinity of each node as the set of $\sqrt{n}log n$ nodes that are closest to the current node in terms of physical proximity. Tulip's construction partitions the nodes into $\sqrt{n}$ color-sets such that:

1. Every color-set has at most $2\sqrt{n}$ nodes.
2. Every node has in its vicinity at least one node from every other color-set.

Colors are assigned to Nodes based on the hash value of the node's id. Hash functions such as SHA-1 are used to ensure that the size of each group is about $\sqrt{n}$ and is under $\sqrt{n}log n$ with high probability.

Each node $u$ in the network maintains data in the form of two lists to capture routing information:

1. Vicinity List: It is the list of information about all $log n$ closest neighbors of $u$ from each color.
2. Color List: It is the list of information about all nodes belonging to the same color group as node $u$.

In other words, node $u$ knows all the nodes in its color group as well $log n$ additional nodes for every other color.

### Key Lookup and Object Lookup

Key lookup in Tulip has a guaranteed stretch of 2 over optimal lookup with up to 2 lookup hops. If a source node $s$ wants to access an object at another node $t$ then, if both belong to the same color group node $s$ directly communicates with node $t$ in one hop or else if the nodes $s$ and $t$ are in different color groups, then, node $s$ communicates with its closest neighbor $w$ which is in the same color group as $t$ and reaches $t$ in 2-hops via the node $w$.

Objects are also given a color based on the hash value of their id. There is no correlation between the color of a node and the color of the objects it stores. Moreover, a single object may also be stored in multiple nodes. Hence, in order to enable object lookup, i.e. to find the nearest node having a copy of the object, all the nodes in Tulip maintain object pointers. If a node $x$ stores an object $o$, then a pointer indicating the same is stored by all nodes having the node $x$ in their vicinity list. Also, all the nodes in the same color group as an object $o$ will store a pointer to the closest node having the object $o$.

Consider a node $s$ which is searching for the nearest node storing an object $o$. If both $s$ and $o$ belong to the same color group then node $s$ has a pointer to the closest node storing $o$. Otherwise, it communicates with another node $w$ which has the same color as $o$ and finds a node $t$ nearest to $w$ storing $o$. The triangular inequality ensures a stretch of up to 4 over optimal object lookup.

Tulip provides separate protocols to maintain locality under churn. This includes protocols for node joining, node deletion, refresh mechanisms and multi-hop query routing. Tulip has been implemented in C++ and has already been deployed over the nodes in PlanetLab. Tulip has been shown to provide locality awareness and fault tolerance.

## Developers

Ittai Abraham, Ankur Badola, Danny Bickson, Dahlia Malkhi, Sharad Maloo, Saar Ron