Admin: Created page with "'''Tulip''' is a distributed, decentralized, P2P network intended for routing, searching and publish-lookup information sharing. It is a structured P2P networ..."

2019-07-30T13:46:38Z

Created page with "'''Tulip''' is a distributed, decentralized, P2P network intended for routing, searching and publish-lookup information sharing. It is a structured P2P networ..."

New page

'''Tulip''' is a distributed, decentralized, [[Peer-to-peer|P2P]] network intended for routing, searching and publish-lookup information sharing. It is a structured P2P network very much like [[Chord project|Chord]], [[Pastry (DHT)|Pastry]], [[Tapestry (DHT)|Tapestry]] and [[Content Addressable Network|CAN]].

==Overview==

In Tulip protocol, a network with <math>n</math> nodes uses <math>O(\sqrt{n}log n)</math> 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 <math>\sqrt{n}log n</math> nodes that are closest to the current node in terms of physical proximity. Tulip's construction partitions the nodes into <math>\sqrt{n}</math> color-sets such that:
# Every color-set has at most <math>2\sqrt{n}</math> nodes.
# 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 <math>\sqrt{n}</math> and is under <math>\sqrt{n}log n</math> with high probability.

Each node <math>u</math> in the network maintains data in the form of two lists to capture routing information:
# Vicinity List: It is the list of information about all <math>log n</math> closest neighbors of <math>u</math> from each color.
# Color List: It is the list of information about all nodes belonging to the same color group as node <math>u</math>.
In other words, node <math>u</math> knows all the nodes in its color group as well <math>log n</math> 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 <math>s</math> wants to access an object at another node <math>t</math> then, if both belong to the same color group node <math>s</math> directly communicates with node <math>t</math> in one hop or else if the nodes <math>s</math> and <math>t</math> are in different color groups, then, node <math>s</math> communicates with its closest neighbor <math>w</math> which is in the same color group as <math>t</math> and reaches <math>t</math> in 2-hops via the node <math>w</math>.

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 <math>x</math> stores an object <math>o</math>, then a pointer indicating the same is stored by all nodes having the node <math>x</math> in their vicinity list. Also, all the nodes in the same color group as an object <math>o</math> will store a pointer to the closest node having the object <math>o</math>.

Consider a node <math>s</math> which is searching for the nearest node storing an object <math>o</math>. If both <math>s</math> and <math>o</math> belong to the same color group then node <math>s</math> has a pointer to the closest node storing <math>o</math>. Otherwise, it communicates with another node <math>w</math> which has the same color as <math>o</math> and finds a node <math>t</math> nearest to <math>w</math> storing <math>o</math>. 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

==External links==
*[http://iptps05.cs.cornell.edu/PDFs/CameraReady_230.pdf Paper proposing Tulip: "Practical Locality-Awareness for Large Scale Information Sharing]

==Source==

[http://wikipedia.org/ http://wikipedia.org/]
[[Category:Decentralized network]]
[[Category:Cryptographic algorithms]]
[[Category:People of the industry]]
==See Also on BitcoinWiki==
* [[Biometric voter registration]]

Tulip Overlay - Revision history

Admin: Created page with "'''Tulip''' is a distributed, decentralized, P2P network intended for routing, searching and publish-lookup information sharing. It is a structured P2P networ..."