From kash Mon Jan 30 17:57:34 2006 Return-Path: Received: from exchfe1.cs.cornell.edu (exchfenlb-1.cs.cornell.edu [128.84.97.33]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k0UMvX429162 for ; Mon, 30 Jan 2006 17:57:33 -0500 (EST) Received: from EXCHVS1.cs.cornell.edu ([128.84.97.23]) by exchfe1.cs.cornell.edu with Microsoft SMTPSVC(6.0.3790.1830); Mon, 30 Jan 2006 17:57:33 -0500 X-MimeOLE: Produced By Microsoft Exchange V6.5 Content-class: urn:content-classes:message MIME-Version: 1.0 X-Security: message sanitized on sundial.cs.cornell.edu See http://www.impsec.org/email-tools/sanitizer-intro.html for details. $Revision: 1.148 $Date: 2004-12-19 11:59:17-08 X-Security: The postmaster has not enabled quarantine of poisoned messages. Content-Type: multipart/alternative; boundary="----_=_NextPart_001_01C625F0.8D25A96F" Subject: Paper 2 Date: Mon, 30 Jan 2006 17:57:30 -0500 Message-ID: <2EE48095D8C21643B0B70EC95F9BFBAFFBBD5E@EXCHVS1.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: Paper 2 Thread-Index: AcYl8Iykvepr6i/pSVe8WK30r0zylA== From: "Ian Kash" To: X-OriginalArrivalTime: 30 Jan 2006 22:57:33.0241 (UTC) FILETIME=[8E0FB290:01C625F0] X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on sundial.cs.cornell.edu X-Spam-Status: No, score=-5.3 required=5.0 tests=ALL_TRUSTED,AWL,BAYES_00, HTML_MESSAGE,MIME_QP_LONG_LINE autolearn=ham version=3.0.2 X-Spam-Level: This is a multi-part message in MIME format. ------_=_NextPart_001_01C625F0.8D25A96F Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable Chord uses a ring structure like the Pastry ring and implements lookups on it in log n hops. Each node stores a set of pointers where the ith is to the first node at least 2^{i-1} around the ring. The target node can then be found in a logarithmic number of steps by following the "longest" finger less than the key. This is similar to Pastry with b=3D2 (i.e. travelling halfway around involves flipping the first bit in binary). Since the definition is more restrictive, it loses the ability of Pastry to choose any eligible node based on locality and to use other bases to reduce the number of hops. Since Chord always transfers messages forwards, it loses the ability of Pastry to overshoot which may lead to a shorter path. However, Chord gains in simplicity of the finger table. It is much simpler to maintain than the Pastry routing table and thus the resulting network degrades more gracefully in the face of churn. =20 The routing method for Tapestry is essentially the same as that of Pastry, however there are several important design differences for other portions of the system that result in improved robustness. Costly deletion operations are avoided by marking nodes invalid but not actually removing them for a period of time to give them a chance to recover. While Pastry stores all the copies of an object in a single neighborhood, Tapestry uses a salt to scatter them through the ring. This means that a problem in a single portion of the ring (whether due to local inconsistencies in routing information or malicious behavior) doesn't cause the object to become unreachable. The use of backpointers gives the flexibility to let those nodes pointing to a given node know to change their routing if the node is overloaded or wishes to leave the network gracefully (though at the cost of requiring additional state). They also can help identify inconsistent views of the ring which can be a problem for Pastry. ------_=_NextPart_001_01C625F0.8D25A96F Content-Type: text/html; charset="us-ascii" Content-Transfer-Encoding: quoted-printable -->

Chord uses a ring structure like the Pastry ring and implements

lookups on it in log n hops.  Each node stores a = set of pointers where

the ith is to the first node at least 2^{i-1} around = the ring.  The

target node can then be found in a logarithmic number = of steps by

following the "longest" finger less than = the key.  This is similar to

Pastry with b=3D2 (i.e. travelling halfway around = involves flipping the

first bit in binary).  Since the definition is = more restrictive, it

loses the ability of Pastry to choose any eligible = node based on

locality and to use other bases to reduce the number = of hops.  Since

Chord always transfers messages forwards, it loses = the ability of

Pastry to overshoot which may lead to a shorter = path.  However, Chord

gains in simplicity of the finger table.  It is = much simpler to

maintain than the Pastry routing table and thus the resulting network

degrades more gracefully in the face of = churn.

 

The routing method for Tapestry is essentially the = same as that of

Pastry, however there are several important design differences for

other portions of the system that result in improved robustness.

Costly deletion operations are avoided by marking = nodes invalid but

not actually removing them for a period of time to = give them a chance

to recover.  While Pastry stores all the copies = of an object in a

single neighborhood, Tapestry uses a salt to scatter = them through the

ring.  This means that a problem in a single = portion of the ring

(whether due to local inconsistencies in routing = information or

malicious behavior) doesn't cause the object to = become unreachable.

The use of backpointers gives the flexibility to let = those nodes

pointing to a given node know to change their routing = if the node is

overloaded or wishes to leave the network gracefully = (though at the

cost of requiring additional state).  They also = can help identify

inconsistent views of the ring which can be a problem = for Pastry.

------_=_NextPart_001_01C625F0.8D25A96F-- From asr32 Mon Jan 30 22:19:38 2006 Return-Path: Received: from authusersmtp.mail.cornell.edu (granite1.mail.cornell.edu [128.253.83.141]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k0V3Jc412287 for ; Mon, 30 Jan 2006 22:19:38 -0500 (EST) Received: from dreadnought.cornell.edu (r253240123.resnet.cornell.edu [128.253.240.123]) (authenticated bits=0) by authusersmtp.mail.cornell.edu (8.13.1/8.12.10) with ESMTP id k0V3Jb5e002618 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for ; Mon, 30 Jan 2006 22:19:38 -0500 (EST) Message-Id: <6.2.1.2.2.20060129102639.03120ae0@postoffice8.mail.cornell.edu> X-Mailer: QUALCOMM Windows Eudora Version 6.2.1.2 Date: Mon, 30 Jan 2006 22:17:36 -0500 To: egs+summary From: Ari Rabkin Subject: PAPER 2 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00 autolearn=ham version=3.0.2 X-Spam-Level: Chord and Tapestry: Like Pastry, Chord and Tapestry are ring-based structured peer-to-peer systems. Chord is the most primitive of the three. Unlike the other two, it makes no attempt to achieve network locality. Chord does not use pastry's prefix-based routing, and as a result, "finger pointers", and also a much smaller leaf set. Perhaps in consequence, Chord's joins and leaves take O(log^2 n), which is asymptotically worse than Pastry's O(log n) Like Pastry, Chord does not necessarily heal properly after a network partition. In contrast, Tapestry is not clearly an advance over Pastry. Keeping one primary, and two secondary "neighbor" pointers seems more vulnerable than the k neighbors that Pastry keeps. Spending a day trying to repair connections seems like a serious weakness if churn is high. Pastry replicates objects, Tapestry leaves pointers. Which approach is superior depends on the context. On the other hand, Tapestry seems to search more widely for 'neighbors' with low network latencies. Ari Rabkin asr32 Risley Hall 454 3-2842 The resources of civilization are not yet exhausted. --William Gladstone From ymir.vigfusson Tue Jan 31 00:40:36 2006 Return-Path: Received: from uproxy.gmail.com (uproxy.gmail.com [66.249.92.194] (may be forged)) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k0V5ea419337 for ; Tue, 31 Jan 2006 00:40:36 -0500 (EST) Received: by uproxy.gmail.com with SMTP id m2so113150ugc for ; Mon, 30 Jan 2006 21:40:35 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:to:subject:mime-version:content-type; b=bRAucrFBINuKwCH1E4BdFME/YXUw/CoLrK3dLypF1JXFXD72g8uS2HtcZHBssQ0+ZNFkpYGuvXGbo8ZYOcdjzT1I+dTJOR/upg3/MVp3mqO3lc/eFiqErjHL9yERsN+DTESpOd4Ph9/VZbw01bqNPK6NuHQgfOyELC3kx4tGzHk= Received: by 10.49.20.3 with SMTP id x3mr965197nfi; Mon, 30 Jan 2006 21:40:35 -0800 (PST) Received: by 10.49.43.1 with HTTP; Mon, 30 Jan 2006 21:40:35 -0800 (PST) Message-ID: <9302f1e20601302140h3bb8217dx160fba081f4ea150@mail.gmail.com> Date: Tue, 31 Jan 2006 00:40:35 -0500 From: Ymir Vigfusson To: egs+summary Subject: PAPER 2 MIME-Version: 1.0 X-Security: message sanitized on sundial.cs.cornell.edu See http://www.impsec.org/email-tools/sanitizer-intro.html for details. $Revision: 1.148 $Date: 2004-12-19 11:59:17-08 X-Security: The postmaster has not enabled quarantine of poisoned messages. Content-Type: multipart/alternative; boundary="----=_Part_11473_17681844.1138686035041" X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on sundial.cs.cornell.edu X-Spam-Status: No, score=-1.5 required=5.0 tests=BAYES_00,HTML_00_10, HTML_MESSAGE,RCVD_BY_IP autolearn=no version=3.0.2 X-Spam-Level: ------=_Part_11473_17681844.1138686035041 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Some differences between the three ring-based P2P protocols: Pastry, Chord and Tapestry (intentionally not using Pastry as a basis). Unlike both Pastry and Tapestry, the vanilla Chord does not take any networ= k topology (i.e. latencies and/or geographic distances) into account when creating its network. The authors mention some potential improvements in this respect in their Future Work section, mainly by taking network delay into account when picking nodes from the intervals in the ID ring. Pastry has a routing table that it tries to maintain as being "close" nodes as far as it can, while Chord depends on successors and fingers that may not b= e at all close (its routing scheme has only one dimension). Chord can also produce some weird network pathologies, such as disjoint rings (that cannot be stablized) or touching rings that share one node in common. When considering where things are put, both Pastry and Chord map things to random places so they may be scattered all over. Tapestry tries to exploit locality by optimize its neighbours, trying to maintain "close" nodes as neighbours = ( w.r.t. network latency) so that when you ask for an object, there should be a copy close by. Both Pastry and Tapestry try to replicate copies of objects, except that Pastry does this at random, while Tapestry does this by considering the network latencies (doing optimally if latency of the N^2 node pairs are known). Pastry has a lookup time of O(lg N) in both worst-case and average case and a routing table of size O(2^b * log_{2^b} N) (plus leafs). Chord has average lookup time of (lg N)/2, has a routing table with O(lg N) entries and with high probability uses O(lg^2 N) messages to join/part a node from its network. Tapestry tries to "keep things close" and maintains a neighbour map of size O(log N) neighbours, and message path length with O(log N) hops. In effect (since the base of the logarithm is irrelevant in the order), all three protocols keep track of O(log N) neighbours and can route through O(log N) hops. In terms of simplicity of the protocols: Chord and Pastry are rather minima= l and simple protocols with the only complex functions involving joins/parts and network rapir, Tapestry is a more complex beast with that requires a bunch of involved considerations (maintaining closeness, finding hotspots, caches etc.). That's all I can think of right now :) Hope to see more in class tomorrow. - Ymir ------=_Part_11473_17681844.1138686035041 Content-Type: text/html; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Some differences between the three ring-based P2P protocols: Pastry, Chord = and Tapestry (intentionally not using Pastry as a basis).

Unlike bot= h Pastry and Tapestry, the vanilla Chord does not take any network topology= ( i.e. latencies and/or geographic distances) into account
when creating i= ts network. The authors mention some potential improvements in this respect= in their Future Work section, mainly by taking network
delay into accou= nt when picking nodes from the intervals in the ID ring. Pastry has a routi= ng table that it tries to maintain as being "close" nodes as
far as it can, while Chord depends on successors and fingers that may n= ot be at all close (its routing scheme has only one dimension). Chord can a= lso
produce some weird network pathologies, such as disjoint rings (that= cannot be stablized) or touching rings that share one node in common.=20

When considering where things are put, both Pastry and Chord map th= ings to random places so they may be scattered all over. Tapestry tries to = exploit locality
by optimize its neighbours, trying to maintain "cl= ose" nodes as neighbours ( w.r.t. network latency) so that when you ask for an object, there should be= a copy
close by. Both Pastry and Tapestry try to replicate copies of ob= jects, except that Pastry does this at random, while Tapestry does this by = considering the network=20
latencies (doing optimally if latency of the N^2 node pairs are known).=

Pastry has a lookup time of O(lg N) in both worst-case and average = case and a routing table of size O(2^b * log_{2^b} N) (plus leafs).  =
Chord has average lookup time of (lg N)/2, has a routing table with O(lg N)= entries and with high probability uses O(lg^2 N) messages to join/part a n= ode from its network.
Tapestry tries to "keep things close" an= d maintains a neighbour map of size O(log N) neighbours, and message path l= ength with O(log N) hops.
In effect (since the base of the logarithm is irrelevant in the order),= all three protocols keep track of O(log N) neighbours and can route throug= h O(log N) hops.

In terms of simplicity of the protocols: Chord and = Pastry are rather minimal and simple protocols with the only complex functi= ons involving joins/parts and network rapir,=20
Tapestry is a more complex beast with that requires a bunch of involved= considerations (maintaining closeness, finding hotspots, caches etc.).
That's all I can think of right now :) Hope to see more in class tomor= row.

- Ymir

------=_Part_11473_17681844.1138686035041-- From pjk25 Tue Jan 31 00:48:48 2006 Return-Path: Received: from authusersmtp.mail.cornell.edu (granite1.mail.cornell.edu [128.253.83.141]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k0V5mm420911 for ; Tue, 31 Jan 2006 00:48:48 -0500 (EST) Received: from [192.168.0.103] (user-10mt73g.cable.mindspring.com [65.110.156.112]) (authenticated bits=0) by authusersmtp.mail.cornell.edu (8.13.1/8.12.10) with ESMTP id k0V5mlFQ019990 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=NOT) for ; Tue, 31 Jan 2006 00:48:47 -0500 (EST) Mime-Version: 1.0 (Apple Message framework v746.2) To: egs+summary Message-Id: <9346C694-1106-4FD6-B185-F1DD4D0A354B> Content-Type: multipart/signed; micalg=sha1; boundary=Apple-Mail-3--681797947; protocol="application/pkcs7-signature" From: Philip Kuryloski Subject: PAPER 2 Date: Tue, 31 Jan 2006 00:51:15 -0500 X-Mailer: Apple Mail (2.746.2) X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00 autolearn=ham version=3.0.2 X-Spam-Level: --Apple-Mail-3--681797947 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Pastry and Chord share similar functionality in that they provide object location and efficient routing for location queries. However, beyond this most basic similarity, their implementations quickly diverge. Pastry relies on random assignment of node IDs to ensure that localized failure in the underlying internet do not result in the failure of successive pastry nodes. Chord relies on a consistent hashing scheme designed to maintain an even distribution of keys across multiple nodes despite nodes entering and dropping out of the network. This gives chord a ring topology for the distribution of keys in the network. Despite this difference, both schemes result in a log N search time, as each search narrows its search space by a constant factor at each hop. Because Chord uses a consistent hashing scheme, it has provisions for the addition of multiple nodes nodes with similar keys. Due to the nature of Chord's routing tables, O(log N) updates are required to redistribute keys. However, this does necessitate the shuffling of keys from one node to another. Another shortcoming of Chord is that the consistent hashing scheme requires the use of virtual nodes within real nodes to ensure that each node does in fact receive keys when they are hashed. Also, Chord does not direct messages based on the latency of links in its underlying network. Tapestry uses random assignment of node ids in the same manner as Pastry. Tapestry also uses a digit based search to route messages toward a target, resulting in similarly structured routing tables as Pastry. Tapestry, unlike Pastry, uses random object keys which do not naturally associate with particular node ids. This requires that routes be built through the network that associate an object with a particular node. A unique feature of Tapestry is that it maintains routing table entries for failed nodes and merely marks them as invalid, allowing for minimal expenditure of resources reintegrating that node if it comes back online within a reasonable period of time. In terms of the integration of new nodes, Tapestry functions in a very similar way to Pastry, borrowing routing table information from neighboring nodes in the node id space. However, Tapestry also associates an epoch with node/object association messages, supporting the movement of objects from one node to another. A protocol for caching objects on additional nodes to reduce routing "hotspots" is also provided by tapestry. This, unlike Pastry, allows the placement of replicas along the path to the original rather than along side of it. Philip Kuryloski 444 Rhodes Hall Cornell University Ithaca, NY 14853-5112 607.255.4222 pjk25 --Apple-Mail-3--681797947 Content-Transfer-Encoding: base64 Content-Type: application/pkcs7-signature; name=smime.p7s Content-Disposition: attachment; filename=smime.p7s MIAGCSqGSIb3DQEHAqCAMIACAQExCzAJBgUrDgMCGgUAMIAGCSqGSIb3DQEHAQAAoIIGFjCCAs8w ggI4oAMCAQICAw+L7TANBgkqhkiG9w0BAQQFADBiMQswCQYDVQQGEwJaQTElMCMGA1UEChMcVGhh d3RlIENvbnN1bHRpbmcgKFB0eSkgTHRkLjEsMCoGA1UEAxMjVGhhd3RlIFBlcnNvbmFsIEZyZWVt YWlsIElzc3VpbmcgQ0EwHhcNMDUwOTI2MTc1NzM0WhcNMDYwOTI2MTc1NzM0WjBDMR8wHQYDVQQD ExZUaGF3dGUgRnJlZW1haWwgTWVtYmVyMSAwHgYJKoZIhvcNAQkBFhFwamsyNUBjb3JuZWxsLmVk dTCCASIwDQYJKoZIhvcNAQEBBQADggEPADCCAQoCggEBALFkgyhHSufUWaYxKh+wvUSDmrM8cViE JjeRS7Ssdd5tf0ckH2iwktNuSkxSsavsmAY+8zahwJjwk/JWTVyOGW/QsjgA5zoTJeAz4ah/QcKZ hou20lN6NvlFZWA43b4/jwtpVVa2RMS1fitkEs7YA9N16akGyXCpJR2i6EVTk7tx8/zf7i7bqg4t tmbJaySQyMQ4QV1O+F00m+zms0WZN5XRDqPwU2/WZfUE5BK/pGLkkFheBGSJJssuOsct8ctup0AI fJLlLZZhBCEdNeM2x9KfQEm+Tk3Ty0zl0pOewe7oW9vgwBJ2LwTVurzQ7qXeq1VhkDmkQJOwjcxM ssGAPXMCAwEAAaMuMCwwHAYDVR0RBBUwE4ERcGprMjVAY29ybmVsbC5lZHUwDAYDVR0TAQH/BAIw ADANBgkqhkiG9w0BAQQFAAOBgQBanW/NR5+pfeGOS7lM21kLObfzzGKtHvTFZ/RS0cSgWSKaCZfx aLLhqC9EFFFxh0b4wn0zCTv4CQWhrpaPZZC7oroP70kqWypQdjFbQ2rlLrVVS8pE4gtjZnRPFMr0 BEH+1K7kWB6kTHvg2eI1EotCI92yARGzlzKrXjPonHppijCCAz8wggKooAMCAQICAQ0wDQYJKoZI hvcNAQEFBQAwgdExCzAJBgNVBAYTAlpBMRUwEwYDVQQIEwxXZXN0ZXJuIENhcGUxEjAQBgNVBAcT CUNhcGUgVG93bjEaMBgGA1UEChMRVGhhd3RlIENvbnN1bHRpbmcxKDAmBgNVBAsTH0NlcnRpZmlj YXRpb24gU2VydmljZXMgRGl2aXNpb24xJDAiBgNVBAMTG1RoYXd0ZSBQZXJzb25hbCBGcmVlbWFp bCBDQTErMCkGCSqGSIb3DQEJARYccGVyc29uYWwtZnJlZW1haWxAdGhhd3RlLmNvbTAeFw0wMzA3 MTcwMDAwMDBaFw0xMzA3MTYyMzU5NTlaMGIxCzAJBgNVBAYTAlpBMSUwIwYDVQQKExxUaGF3dGUg Q29uc3VsdGluZyAoUHR5KSBMdGQuMSwwKgYDVQQDEyNUaGF3dGUgUGVyc29uYWwgRnJlZW1haWwg SXNzdWluZyBDQTCBnzANBgkqhkiG9w0BAQEFAAOBjQAwgYkCgYEAxKY8VXNV+065yplaHmjAdQRw nd/p/6Me7L3N9VvyGna9fww6YfK/Uc4B1OVQCjDXAmNaLIkVcI7dyfArhVqqP3FWy688Cwfn8R+R NiQqE88r1fOCdz0Dviv+uxg+B79AgAJk16emu59l0cUqVIUPSAR/p7bRPGEEQB5kGXJgt/sCAwEA AaOBlDCBkTASBgNVHRMBAf8ECDAGAQH/AgEAMEMGA1UdHwQ8MDowOKA2oDSGMmh0dHA6Ly9jcmwu dGhhd3RlLmNvbS9UaGF3dGVQZXJzb25hbEZyZWVtYWlsQ0EuY3JsMAsGA1UdDwQEAwIBBjApBgNV HREEIjAgpB4wHDEaMBgGA1UEAxMRUHJpdmF0ZUxhYmVsMi0xMzgwDQYJKoZIhvcNAQEFBQADgYEA SIzRUIPqCy7MDaNmrGcPf6+svsIXoUOWlJ1/TCG4+DYfqi2fNi/A9BxQIJNwPP2t4WFiw9k6GX6E sZkbAMUaC4J0niVQlGLH2ydxVyWN3amcOY6MIE9lX5Xa9/eH1sYITq726jTlEBpbNU1341YheILc IRk13iSx0x1G/11fZU8xggLnMIIC4wIBATBpMGIxCzAJBgNVBAYTAlpBMSUwIwYDVQQKExxUaGF3 dGUgQ29uc3VsdGluZyAoUHR5KSBMdGQuMSwwKgYDVQQDEyNUaGF3dGUgUGVyc29uYWwgRnJlZW1h aWwgSXNzdWluZyBDQQIDD4vtMAkGBSsOAwIaBQCgggFTMBgGCSqGSIb3DQEJAzELBgkqhkiG9w0B BwEwHAYJKoZIhvcNAQkFMQ8XDTA2MDEzMTA1NTExNlowIwYJKoZIhvcNAQkEMRYEFK6Wfs+R/AEY ViOnuxnQTVp+kMygMHgGCSsGAQQBgjcQBDFrMGkwYjELMAkGA1UEBhMCWkExJTAjBgNVBAoTHFRo YXd0ZSBDb25zdWx0aW5nIChQdHkpIEx0ZC4xLDAqBgNVBAMTI1RoYXd0ZSBQZXJzb25hbCBGcmVl bWFpbCBJc3N1aW5nIENBAgMPi+0wegYLKoZIhvcNAQkQAgsxa6BpMGIxCzAJBgNVBAYTAlpBMSUw IwYDVQQKExxUaGF3dGUgQ29uc3VsdGluZyAoUHR5KSBMdGQuMSwwKgYDVQQDEyNUaGF3dGUgUGVy c29uYWwgRnJlZW1haWwgSXNzdWluZyBDQQIDD4vtMA0GCSqGSIb3DQEBAQUABIIBAHmNls1JkX9T wppvZlJxU28vjVxrcM5boiPU8y+LmdSQBq7dwv+o1jdYEcbFzPRQ3PqJEscBIPkGjaEGWDxRS3Qw 5Hf1echMmCRAYZIzCEvVhSmJeur6vUy+CvG+/zDYkFmO34/l8Bh+WUybAxQCFauHVsJmpXGH0Rca sLH529xpqXyBPAW8CNMjqrsuRFQSCtlizjCRS2DmHYcDf8GywjqeFoIg8+HjSpyH2Z+xlCtyxIpv GzL60E4Vo8P99+UYa+TDdO6uwcdXpHxp9PjdeJVryJRpi53MaTeeC2+uCJDWabBdtx5mfoVesSbF m7jDZxK3k0L2dOeSkafCYFXEMiMAAAAAAAA= --Apple-Mail-3--681797947-- From niranjan.sivakumar Tue Jan 31 00:55:29 2006 Return-Path: Received: from xproxy.gmail.com (xproxy.gmail.com [66.249.82.205] (may be forged)) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k0V5tS422916 for ; Tue, 31 Jan 2006 00:55:29 -0500 (EST) Received: by xproxy.gmail.com with SMTP id h30so916782wxd for ; Mon, 30 Jan 2006 21:55:28 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:from:reply-to:to:subject:date:user-agent:mime-version:content-type:content-transfer-encoding:content-disposition:message-id; b=aijWXbdqKMeHBAPfImWHyG9krToe8gbSUSFRpr7ZtOFATKFPiOViMit68cebnRtJ/MkyeLrb5uqF7OyOieesNyI0Zw1dseJehV9Bd6J3Oe3U9q5eYbRIFPmmSA5R73qtSqLjzirEDGwDEQQi1T09LtJsMVF/pYr7g9Pu+ywSSPg= Received: by 10.70.74.19 with SMTP id w19mr8247431wxa; Mon, 30 Jan 2006 21:55:27 -0800 (PST) Received: from ?192.168.0.102? ( [69.207.63.116]) by mx.gmail.com with ESMTP id h35sm10020549wxd.2006.01.30.21.55.27; Mon, 30 Jan 2006 21:55:27 -0800 (PST) From: Niranjan Sivakumar Reply-To: niranjan.sivakumar To: egs+summary Subject: PAPER 2 Date: Tue, 31 Jan 2006 00:55:23 -0500 User-Agent: KMail/1.9 MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200601310055.24259.niranjan.sivakumar> X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.5 required=5.0 tests=BAYES_00,RCVD_BY_IP autolearn=ham version=3.0.2 X-Spam-Level: Niranjan Sivakumar Chord primarily differs from Pastry in how it implements its routing mechanism. Whereas Pastry's routing mechanism is based on matching prefixes of a key with those of entries in its routing data structure, Chord maintains comparatively less routing information consisting of information about successive nodes in the ring. Chord maintains a few successive nodes in its finger table in order to account for failures and changes to the network. Chord forwards queries to nodes in the ring, trying to find the closes ID that would most closely precede that key that is being searched for in order to find its successor. The finger pointers are spaced such that the distance to the target ID will be halved in successive iterations. The basic routing mechanism of the Plaxton system employed by Tapestry is very similar to Pastry and is based on matching suffixes (analogous to the prefixes of Pastry. There is, however, a location system of "root nodes" associated with objects that is unique to Tapestry. Messages destined for a particular object are routed towards the root, and can diverge to a server holding the object if such a mapping is encountered en route to the root. This allows for copies of objects to be on the network. The systems deals with root nodes being targets of failure with replication and caching. One of the weaknesses seen in both of these papers is similar to something that we noticed in the Pastry paper. There doesn't seem to be a robust method to search for content. The key based method does not seem to allow for things such as semantic searching or range searching very easily. Chord also does not seem to have an analogous mechanism to the Pastry neighborhood information to avoid routing queries in an inefficient manner due to the random nature of the nodes in the network. From victoria Tue Jan 31 02:36:06 2006 Return-Path: Received: from turing.cs.hmc.edu (turing.cs.hmc.edu [134.173.42.99]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k0V7a5423974 for ; Tue, 31 Jan 2006 02:36:05 -0500 (EST) Received: by turing.cs.hmc.edu (Postfix, from userid 34382) id 719AE53230; Mon, 30 Jan 2006 23:35:59 -0800 (PST) Date: Mon, 30 Jan 2006 23:35:59 -0800 From: Victoria Krafft To: egs+summary Subject: PAPER 2 Message-ID: <20060131073559.GA16513> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.4.2.1i X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00 autolearn=ham version=3.0.2 X-Spam-Level: Pastry, Chord, and Tapestry are all similar peer to peer networks, based on a Distributed Hash Table (DHT). Pastry and Chord have only a few differences. Chord does not attempt to take network locality into account, which means that messages will probably take a bit longer over a large network. Chord keeps a constant size routing table, with a lookup time of O(log N). Chord can also improve load balancing by creating virtual nodes in the network. Tapestry is slightly different. It's based on the Plaxon mesh data structure, which is essentially a DHT. Each node has a unique ID, and routing across the network is accomplished by forwarding a message to a node with an ID closer to the destination of the message. For each object in the network, there are several root nodes, which know the location of the object. Tapestry also features the idea of second chance recovery. If a node disappears from the network, it is marked as inactive, and not removed from the other nodes for some period of time (perhaps an hour or a day). If the node re-joins the network within that time frame, then it can simply pick up where it left off. While Tapestry's second chance recovery mechanism sounds promising when the network will not be experiencing high churn, it could become costly. To give an extreme example, if 3/4 of the network is offline at any given time, but comes back once a day to check and see if anything new has been added, then 3/4 of the routing table entries each node stores are currently invalid, and will just be sitting around taking up memory. -- Victoria Krafft From nsg7 Tue Jan 31 09:59:23 2006 Return-Path: Received: from postoffice10.mail.cornell.edu (postoffice10.mail.cornell.edu [132.236.56.14]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k0VExN410726 for ; Tue, 31 Jan 2006 09:59:23 -0500 (EST) Received: from webmail.cornell.edu (hermes21.mail.cornell.edu [132.236.56.20]) by postoffice10.mail.cornell.edu (8.12.10/8.12.6) with ESMTP id k0VExLvg019209 for ; Tue, 31 Jan 2006 09:59:21 -0500 (EST) Received: from 132.236.227.119 by webmail.cornell.edu with HTTP; Tue, 31 Jan 2006 09:59:22 -0500 (EST) Message-ID: <1673.132.236.227.119.1138719562.squirrel@webmail.cornell.edu> Date: Tue, 31 Jan 2006 09:59:22 -0500 (EST) Subject: PAPER 2 From: "Nicholas S Gerner" To: egs+summary User-Agent: SquirrelMail/1.4.5 MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Priority: 3 (Normal) Importance: Normal X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00 autolearn=ham version=3.0.2 X-Spam-Level: Chord and Tapestry both present distributed datastructures similar to Pastry. Both use a ring overlay to route messages with a key identifier to a node with the id nearest to the message's identifier (although Tapestry doesn't describe its overlay as a ring). However, both Chord and Tapestry use more proactive protocols to maintain network state information. While Pastry maintains a table of nodes in an exponentially expanding ring, Chord maintains information about one other node at exponentially expanding intervals (called the finger table). Specifically, node with id n stores the IP of the node responsible for key n+2^i for each i up to the length of the identifier. In Chord, destinations are located by moving exponentially closer to the destination, but recursively returning the destination IP, requring an explicit round-trip. Chord network state is maintained by a "stabilization" protocol which periodically contacts the successor (next pointer in the ring) asking for its predecessor (which should be the current node, or else that node should be the current node's successor). The finger table is similarly periodically updated. Node failures are handled by keeping a list of r possible successors and updating this list with the stabilization protocol. This is in contrast to Pastry which maintains network state reactively to detection of node failure or node joins. Tapestry maintains a route table similarly to Pastry. In Tapestry information about objects in the network are published to the node responsible for the object. Information is cached along the path from the originating node to the node responsible for that object. Node insertion is handled similarly to Pastry. Object caches at nodes are periodically updated or removed. Periodic heart-beats are sent between neighbors to verify connectivity. Failed nodes are not immediately removed from state and are kept for some period to speed up recovery of repaired nodes. The proactive protocols employed by both Chord and Tapestry incur an overhead for network state maintenance. Both systems still involve significant node arrival message exchanges (Chord involves log^2 message exchanges). The Tapestry paper admits that this cost of republishing object locations (updating caches along the way) can be too high, but modifies its approach by adding a node disconnect protocol. It seems that proactive schemes to network state maintenance don't handle arbitrary node failures and incur too high a cost for what all papers assume is the common case: nodes remain alive indefinately (which may be a faulty assumption). --Nick Gerner From ryanp Tue Jan 31 10:11:23 2006 Return-Path: Received: from exchfe2.cs.cornell.edu (exchfenlb-2.cs.cornell.edu [128.84.97.34]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k0VFBN417158 for ; Tue, 31 Jan 2006 10:11:23 -0500 (EST) Received: from exchfe2.cs.cornell.edu ([128.84.97.28]) by exchfe2.cs.cornell.edu with Microsoft SMTPSVC(6.0.3790.1830); Tue, 31 Jan 2006 10:11:23 -0500 Received: from [128.253.211.203] ([128.253.211.203]) by exchfe2.cs.cornell.edu over TLS secured channel with Microsoft SMTPSVC(6.0.3790.1830); Tue, 31 Jan 2006 10:11:23 -0500 Mime-Version: 1.0 (Apple Message framework v746.2) Content-Transfer-Encoding: 7bit Message-Id: <6D68D0E1-2D52-49E1-8E23-43E1DEBEBA31> Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed To: egs+summary From: "Ryan S. Peterson" Subject: PAPER 2 Date: Tue, 31 Jan 2006 10:11:20 -0500 X-Mailer: Apple Mail (2.746.2) X-OriginalArrivalTime: 31 Jan 2006 15:11:23.0032 (UTC) FILETIME=[98EE4180:01C62678] X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.6 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.0.2 X-Spam-Level: Chord and Tapestry both introduce peer-to-peer distributed hash tables, promoting efficiency and reliability. Chord structures its nodes in a ring by increasing key value, much like Pastry. However, unlike Pastry, Chord always hashes object keys to the key's "successor" node, defined as the closest node from the key in the clockwise direction around the ring. While Chord and Pastry both advertise O(log n) lookup time, their lookup algorithms and data structures are quite different. Each Chord node maintains a constant- sized list of "fingers," or pointers that point successively farther around the ring in the clockwise direction. Finger i of node with key n points to node the first node that succeeds key n + 2^(i-1) in the ring, once again in the clockwise direction. Thus, finger 1 always points to the next node, and the remaining fingers point increasingly farther and farther away. Therefore, like Pastry nodes, each Chord node knows more nodes in its local area than nodes on the other side of the ring. Lookup in Chord proceeds by starting at some arbitrary node and following the fingers around the ring, making smaller jumps as the routing nears the target node. While Chord proves several time guarantees, it has more opportunity to incur overhead than Pastry. Since Chord always moves in the clockwise direction, it will never find the shortest route to a target node just to the left (counterclockwise direction) of the start node. Furthermore, Chord nodes do not maintain leaf sets, so routing involves traversing the finger pointers until the exact node is reached, whereas in Pastry, routing requires only one more hop as soon as the routing has reached any "nearby" node. Lastly in terms of time, Chord does not use a proximity metric to take network conditions into account when determining fingers or routing paths, which could slow down the DHT dramatically if some of the nodes are far away or are responding slowly. Therefore, although Chord proves time guarantees, its O(log n) lookup time has a higher coefficient than Pastry's does. In terms of space, Chord's join algorithm implies that every node maintains a pointer for each digit of the key, requiring nodes in small networks to maintain duplicate fingers that point to the same nodes. However, this may be optimized away if space proved to be a problem. In terms of stability, Chord, unlike Pastry, does not provide any guarantees for preventing the ring from splitting. Since each Chord node only maintains its forward pointers (and one backward pointer for assisting in joins and failures), it is difficult to say how many failures would compromise the ring structure. As a final observation, Chord provides one primitive, lookup, which identifies the home node for a given key, whereas Pastry provides routing primitives. In other words, Chord provides the application with a pointer to the home node, which the application could use to send a file directly to it. This could improve performance if the object being transferred is large (since Pastry would route it from one node to another), but maybe slow insert time down since it requires two separate phases: lookup then insert. Tapestry presents a spanning-tree-like network structure that contrasts with the ring structure of Chord and Pastry. Each node is both a root of its "object" tree--the trees for which that node is the home node for the object in question--and a node in a multi-layer spanning tree that enables matching more digits in the suffix of the lookup key. Because of Tapestry's tree structure, object lookup has more similarities to overlay network routing than moving around a ring. The authors give examples of routing around crashed nodes, much as routing would occur in an Internet overlay in the presence of failure. Because of this more unstructured approach, Tapestry provides fewer guarantees, since a node failure affects the network differently depending on its location in the spanning trees. However, because Tapestry does traverse the spanning trees based on the postfix of the lookup key, it still does provide a O(log n) upper bound on lookups assuming the network is stable. Overall, Tapestry seems less principled, providing a structure that has many of the same vulnerabilities as the Internet. This might make lookups faster in some instances, but makes it more difficult to reason about performance since the structure is more loosely defined. Ryan From km266 Tue Jan 31 10:47:08 2006 Return-Path: Received: from authusersmtp.mail.cornell.edu (granite1.mail.cornell.edu [128.253.83.141]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k0VFl8428762 for ; Tue, 31 Jan 2006 10:47:08 -0500 (EST) Received: from KEVSTOY (cpe-69-207-37-68.twcny.res.rr.com [69.207.37.68]) (authenticated bits=0) by authusersmtp.mail.cornell.edu (8.13.1/8.12.10) with ESMTP id k0VFl7p0029079 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NOT) for ; Tue, 31 Jan 2006 10:47:07 -0500 (EST) Message-ID: <001d01c6267d$a08c6200$4425cf45@KEVSTOY> Reply-To: "Kevin" From: "Kevin" To: Subject: PAPER 2 Date: Tue, 31 Jan 2006 10:47:22 -0500 MIME-Version: 1.0 X-Security: message sanitized on sundial.cs.cornell.edu See http://www.impsec.org/email-tools/sanitizer-intro.html for details. $Revision: 1.148 $Date: 2004-12-19 11:59:17-08 X-Security: The postmaster has not enabled quarantine of poisoned messages. Content-Type: multipart/alternative; boundary="----=_NextPart_000_001A_01C62653.B7465A20" X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2900.2527 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2527 X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.4 required=5.0 tests=AWL,BAYES_00, FORGED_OUTLOOK_TAGS,HTML_10_20,HTML_MESSAGE autolearn=no version=3.0.2 X-Spam-Level: This is a multi-part message in MIME format. ------=_NextPart_000_001A_01C62653.B7465A20 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Chord is different from Pastry in several key ways. The first is the = way that it routes a key to a node. Chord tries to locate a node, n, = where n is the the first node greater than or equal to the key. Instead = of routing by constantly finding a node whose prefix matches that of the = keys by one more digit, it keeps bookmarks, or a finger table, of nodes = that are progressively farther away (by factors of 2). In this way it = is possible for n to find a node who has more information in its finger = table about the target. This also leads to an O(log n) lookup time. = Chord does not place a constraint on the structure of the keys it looks = up, giving the higher-level application more freedom. Like Pastry, = Chord keeps a leaf-set like structure of successor nodes (and one = predecessor node) in order to help maintain stability in case of = joins/leaves. Unlike Pastry, Chord offers no neighborhood-like set. = Locality is not taken into account in Chord and it is perfectly possible = for a packet to be routed around the world several times before it = reaches its proper destination. Chord does have a wide variety of problems. While not a technical = issue, one complaint I have with it is the word 'successor'. In most = uses I have seen, successor usually is strictly greater than, not equal = to or greater than in the way Chord uses it. If a node fails that was = holding specific data, that data is forever lost. This issue is = discussed without any great depth in part of the paper and says to just = duplicate data to k successors of n -- this ends up being quite a = nuisence since all of a sudden each node is responsible for k-times the = amount of data it was originally responsible for. Failures between = stabilizations kill the system. In their example, 3 failures out of a = 500 node system cause a failure rate of 3%. If a chunk of the physical = system got taken out and 25 nodes failed (5% of the whole system), 25% = of queries will fail! Luckily it seems this will only delay correct = transmission of the message, although in a really big system, = stabalizing every 30 seconds might not be realistic. My last complaint = and probably biggest complaint is, once again, security. A node could = join in with a fake ID and drop packets on the ground or throw other = nodes' finger tables off. Tapestry works on the principal of a Plaxton mesh. As far as I could = tell, the network topology is not circular. Messages get routed = similarly to Pastry with suffixes being matched one base at a time and = messages being routed closer to the target. The difference is the = target: the target is not where the object is stored, but rather a node = that knows where the object is stored. This improves security but takes = away from reliability. In order to eliminate a single point of failure, = multiple nodes have information on the node that stores the object. = Furthermore, nodes along the path aquire this information as it is = routed through them and they cache it. Tapestry also combines the idea = of a neighbor table with the routing table, trying to ensure that the = new table takes both into account: it knows where a message should be = routed along with the quickest (ping-wise, or otherwise) node to pass = the message on to. Tapestry has some problems, one of which seems to be its use of = resources. Throughout the paper it is stated that bandwidth, disk = space, and other resources will be plentiful. With many people = searching for and looking to download more files, it is arguable that = traffic and disk space are big issues. Tapestry also seems to 'trust' a = node more than it should. Tapestry gives a failed node a second chance = period while it tries to contact it once in a while to see if it is back = online. While this might be good in a reliable set of nodes or servers = you expect to constantly be up, it is fully possible for a node to join = and leave the network within a couple of minutes, or faster. If this = is done by multiple nodes with similar numbers then the alternative = nodes in the neighbor table might all be in their second chance period. = When the main node goes down, a search has to be initiated anyway, yet = interim network performance was not optimal. The last problem I would = like to mention with Tapestry is one that the paper points out itself. = A new node coming in changes the way an object might be routed. Before = the system is refreshed, there is a vulnerability here. ------=_NextPart_000_001A_01C62653.B7465A20 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable
 Chord is different from Pastry in = several key=20 ways.  The first is the way that it routes a key to a node.  = Chord=20 tries to locate a node, n, where n is the the first node greater than or = equal=20 to the key.  Instead of routing by constantly finding a node whose = prefix=20 matches that of the keys by one more digit, it keeps bookmarks, or a = finger=20 table, of nodes that are progressively farther away (by factors of = 2).  In=20 this way it is possible for n to find a node who has more information in = its=20 finger table about the target.  This also leads to an O(log n) = lookup=20 time.  Chord does not place a constraint on the structure of the = keys it=20 looks up, giving the higher-level application more freedom.  Like = Pastry,=20 Chord keeps a leaf-set like structure of successor nodes (and one = predecessor=20 node) in order to help maintain stability in case of joins/leaves.  = Unlike=20 Pastry, Chord offers no neighborhood-like set.  Locality is not = taken into=20 account in Chord and it is perfectly possible for a packet to be routed = around=20 the world several times before it reaches its proper = destination.
 Chord=20 does have a wide variety of problems.  While not a technical issue, = one=20 complaint I have with it is the word 'successor'.  In most uses I = have=20 seen, successor usually is strictly greater than, not equal to or = greater than=20 in the way Chord uses it.  If a node fails that was holding = specific data,=20 that data is forever lost.  This issue is discussed without any = great depth=20 in part of the paper and says to just duplicate data to k successors of = n --=20 this ends up being quite a nuisence since all of a sudden each node is=20 responsible for k-times the amount of data it was originally responsible = for.  Failures between stabilizations kill the system.  In = their=20 example, 3 failures out of a 500 node system cause a failure rate of = 3%. =20 If a chunk of the physical system got taken out and 25 nodes failed (5% = of the=20 whole system), 25% of queries will fail!  Luckily it seems this = will only=20 delay correct transmission of the message, although in a really big = system,=20 stabalizing every 30 seconds might not be realistic.  My last = complaint and=20 probably biggest complaint is, once again, security.  A node could = join in=20 with a fake ID and drop packets on the ground or throw other nodes' = finger=20 tables off.
 
 
 Tapestry works on the principal = of a Plaxton=20 mesh.  As far as I could tell, the network topology is not = circular. =20 Messages get routed similarly to Pastry with suffixes being matched one = base at=20 a time and messages being routed closer to the target.  The = difference is=20 the target: the target is not where the object is stored, but rather a = node that=20 knows where the object is stored.  This improves security but takes = away=20 from reliability.  In order to eliminate a single point of failure, = multiple nodes have information on the node that stores the = object. =20 Furthermore, nodes along the path aquire this information as it is = routed=20 through them and they cache it.  Tapestry also combines the idea of = a=20 neighbor table with the routing table, trying to ensure that the new = table takes=20 both into account: it knows where a message should be routed along with = the=20 quickest (ping-wise, or otherwise) node to pass the message on=20 to.
 Tapestry has some problems, one of which seems to be its = use of=20 resources.  Throughout the paper it is stated that bandwidth, disk = space,=20 and other resources will be plentiful.  With many people searching = for and=20 looking to download more files, it is arguable that traffic and disk = space are=20 big issues.  Tapestry also seems to 'trust' a node more than it=20 should.  Tapestry gives a failed node a second chance period while = it tries=20 to contact it once in a while to see if it is back online.  While = this=20 might be good in a reliable set of nodes or servers you expect to = constantly be=20 up, it is fully possible for a node to join and leave the network within = a=20 couple of minutes, or faster.   If this is done by multiple = nodes with=20 similar numbers then the alternative nodes in the neighbor table might = all be in=20 their second chance period.  When the main node goes down, a search = has to=20 be initiated anyway, yet interim network performance was not = optimal.  The=20 last problem I would like to mention with Tapestry is one that the paper = points=20 out itself.  A new node coming in changes the way an object might = be=20 routed.  Before the system is refreshed, there is a vulnerability=20 here.
------=_NextPart_000_001A_01C62653.B7465A20-- From gp72 Tue Jan 31 11:00:45 2006 Return-Path: Received: from postoffice10.mail.cornell.edu (postoffice10.mail.cornell.edu [132.236.56.14]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k0VG0j403252 for ; Tue, 31 Jan 2006 11:00:45 -0500 (EST) Received: from webmail.cornell.edu (hermes21.mail.cornell.edu [132.236.56.20]) by postoffice10.mail.cornell.edu (8.12.10/8.12.6) with ESMTP id k0VG0gvg001112; Tue, 31 Jan 2006 11:00:43 -0500 (EST) Received: from 128.253.122.16 by webmail.cornell.edu with HTTP; Tue, 31 Jan 2006 11:00:43 -0500 (EST) Message-ID: <1280.128.253.122.16.1138723243.squirrel@webmail.cornell.edu> In-Reply-To: <1256.128.253.122.16.1138722260.squirrel@webmail.cornell.edu> References: <1256.128.253.122.16.1138722260.squirrel@webmail.cornell.edu> Date: Tue, 31 Jan 2006 11:00:43 -0500 (EST) Subject: PAPER 2 From: "Gopal Parameswaran" To: egs+summary User-Agent: SquirrelMail/1.4.5 MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Priority: 3 (Normal) Importance: Normal X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00 autolearn=ham version=3.0.2 X-Spam-Level: All the three P2P systems discussed ie. Pastry, Chord and Tapestry are different forms of scalable de-centralized ring networks that allow for insertion and deletion of nodes from the network and support distributed hash table functionality. All the three systems are highly similar in their primary functionality but differ in their algorithms. Since they are all different forms of distributed hash tables they provide support getting and putting objects into the system based on keys and a lookup function that gives the address of the node that has the object. The leaf set in pastry and the finger set in Chord gives the proximity in logical space. Chord does not consider network proximity at all unlike Pastry where a neighborhood set is also maintained for routing to the nodes that are close by. Thus in the case of Chord the messages could travel longer distances to just go to a node in its neighborhood. Pastry unlike Chord has a bigger table with routing information and hence even though it provides benefit for local searches more work needs to be done when nodes join and drop out of the system since every time a change occurs the tables maintained by pastry needs to be updated. Chord however seems to have an apparent issue with of orphan nodes when some nodes drop out of the system. Since a node's information is kept in a successor node if the successor node drops out of the system or a series of successor nodes drops out then the node could be left as an orphan with no connections to the node. Chord unlike Pastry and Tapestry uses consistent hashing where each node has a certain fixed number of keys that it can allocate and if the need for the number of keys goes above than the node's capacity it can create virtual nodes. It provides an advantage when nodes are being added and dropped from the system since any remapping that needs to be done will be done locally leaving all other nodes unaffected. Pastry handles fault tolerant location by maintaining more than one node Id of the network belonging to one digit for routing in the routing table so that if any one one node in its list has dropped out then it can be routed via another node. Tapestry on the other hand handles the fault tolerant location finding by defining multiple paths to resources that are cached and that leads to different independent paths in the search for the resource. Also Pastry and Chord uses TCP timeout to detect if the nodes are down or dead. Tapestry on the other hand introduces a key concept of each node identifying itself as alive at periodic intervals to help ensure its neighboring nodes that contain a reference to it that it is alive by sending small packets. Also in Tapestry unlike the other two systems the concept of a second chance is introduced for nodes that has failed to respond or timed out. This means that if a node fails to respond then a second message is send to that node after a reasonable amount of time to ensure that it is back up. This prevents unnecessary deletions and re-insertions of nodes into the system which could make a big difference especially if the network is unstable and nodes tend to drop out and rejoin due to network instabilities. Finally to conclude all the three algorithms seems to focus a lot more on doing the least amount of node traversal as a performance metric rather than time spend in reaching a node to retrieve the information. The basic assumption is made that the time spend is proportional to the nodes traversed and also that logical closeness can emulate physical closeness by caching the resources or hashing the IP addresses. From sh366 Tue Jan 31 11:15:05 2006 Return-Path: Received: from postoffice10.mail.cornell.edu (postoffice10.mail.cornell.edu [132.236.56.14]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k0VGF5407793 for ; Tue, 31 Jan 2006 11:15:05 -0500 (EST) Received: from orpheus3.dataserver.cornell.edu (orpheus3.dataserver.cornell.edu [128.253.161.167]) by postoffice10.mail.cornell.edu (8.12.10/8.12.6) with ESMTP id k0VGF4vg010550 for ; Tue, 31 Jan 2006 11:15:04 -0500 (EST) Message-ID: <247983975.1138724103700.JavaMail.webber@orpheus3.dataserver.cornell.edu> Date: Tue, 31 Jan 2006 11:15:03 -0500 (EST) From: Huang Shiang-Jia To: egs+summary Subject: PAPER 2 Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 X-Mailer: uPortal WEB email client 3.0 Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id k0VGF5407793 X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.6 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.0.2 X-Spam-Level: • Chord always forwards messages to a successor (node clockwise from the key in the ID space). In Pastry and Tapestry, messages are forwarded to a node whose ID shares longer prefix with the key, or failing that is numerically closer to the key, than the present node. The ID of such a node may be larger or smaller than the present node. • [Locality] The advantage of Pastry and Tapestry over Chord is that they take into account network topology to reduce the routing latency. Particularly, Tapestry and Pastry behave well in locating “nearby” objects that may be distant from the present node in the ID space: Pastry maintains a neighbor set; Tapestry proposed the location mapping scheme in addition, as will be described below. • In stable states, Chord ‘guarantees’ the number of nodes that must be contacted in a lookup is O(logN). Pastry and Tapestry ‘expects’ the number of steps to resolve a lookup is O(logN), but it can take more steps due to the cases of surrogate routing. • Routing in Pastry and Tapestry is recursive (vs. iterative in Kademlia). Chord can route either iteratively or recursively. • In Pastry and Tapestry, the routing path is a function of the destination node ID, not of the source node ID, as in Chord. All the three routing protocols rely on applications to replicate values associated with keys, but they differ in the following ways: • Pastry simply provides a distributed hash table interface for replications. Replicas of the value associated with a key are stored at the k numerically closest nodes. • The successor list mechanism proposed by Chord a lot helps applications replicate data. In Chord, replicas of the values are stored at the k nodes succeeding the key. By keeping track of the successors, Chord can notify applications to propagate data to new replicas once any node(s) in the list fails. • In Tapestry, the servers that store an object periodically route publish messages toward the root of this object. Nodes along the publication path store pointer mappings for object replicas in sorted order of network latency from themselves. In this way, queries can therefore be routed to the locally nearest replica. “Replication is critical in the overlay routing infrastructure. Lookups will fail if the node that stores the value associated with the key fails. It is my doubt that is the replication ought to be done in application level or the routing protocols could do something with it? Second, lookups may fail when the values associated with keys migrate, but all these three papers don’t give details of the migration.” • Chord makes the number of keys per node more uniform (in order to improve load balance) by running virtual nodes. Pastry and Tapestry just assume that nodes are assigned IDs uniformly. • Security issues are addressed in Tapestry; for example, security measures can be imposed in the neighbor link of a Tapestry node. In Pastry and Chord, it is applications’ responsibility to impose security measures. • Chord and Tapestry periodically update the routing and object location information, while Pastry lazily repairs its state table. • Tapestry nodes store back-pointers to help new nodes construct their routing tables, while Pastry nodes don’t. • During each stabilization step in Chord, a node updates its immediate successor and one other entry in the successor list or finger table. I was wondering if all are stabilized for each call would be better. From ids3 Tue Jan 31 11:32:34 2006 Return-Path: Received: from postoffice10.mail.cornell.edu (postoffice10.mail.cornell.edu [132.236.56.14]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k0VGWY415833 for ; Tue, 31 Jan 2006 11:32:34 -0500 (EST) Received: from webmail.cornell.edu (hermes21.mail.cornell.edu [132.236.56.20]) by postoffice10.mail.cornell.edu (8.12.10/8.12.6) with ESMTP id k0VGWWvg022573 for ; Tue, 31 Jan 2006 11:32:33 -0500 (EST) Received: from 128.84.98.64 by webmail.cornell.edu with HTTP; Tue, 31 Jan 2006 11:32:33 -0500 (EST) Message-ID: <4827.128.84.98.64.1138725153.squirrel@webmail.cornell.edu> Date: Tue, 31 Jan 2006 11:32:33 -0500 (EST) Subject: PAPER 2 From: "Ivan Stoyanov" To: egs+summary User-Agent: SquirrelMail/1.4.5 MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Priority: 3 (Normal) Importance: Normal X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00 autolearn=ham version=3.0.2 X-Spam-Level: Pastry, Chord, Tapestry and Kademlia have similar design goals and similar characteristics. Tapestry and Pastry are quite similar, using respectively suffix and prefix -based routing, with their lookup time being O(log2^b(N)), while Chord and Kademlia are O(log2(N)). Tapestry is generally a more complicated improvement of Pastry. The main improvements are the additional redundancy in the form of multiple messages or links and the routing table optimization, which results in better routing performance than Pastry. Also, Tapestry used object replication which makes it more faiulure resistant. Another important feature of Tapestry is the root election algorithm. This makes routing more flexible, but requires maintenance of global properties and more work for the join protocol. As far as simplicity is concerned, Tapestry is the most complex of all with Kademlia and Chord being simpler. Kademlia's main contributions is the usage of XOR metric. Chord, on the other side, uses consistent hashing to store key-value mappings on the successor node in a circular space. This makes node joining very simple, without too much information changing place. Chord does not take care of object replication and, like Pastry, says that node failure will be handles by the availability of multiple rounds. Kademlia and Tapestry do take of object replication. Chord is the only system that provides a proof of correctness for its routing. All four systems are vulerable to network partitioning attacks, because an attacker can join multiple times at self-chosen points. All four systems do not address content verifiability, so any node can claim to posses any data, but the actual vericication is left to the above application. From asg46 Tue Jan 31 11:33:39 2006 Return-Path: Received: from postoffice10.mail.cornell.edu (postoffice10.mail.cornell.edu [132.236.56.14]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k0VGXc416028 for ; Tue, 31 Jan 2006 11:33:38 -0500 (EST) Received: from webmail.cornell.edu (hermes21.mail.cornell.edu [132.236.56.20]) by postoffice10.mail.cornell.edu (8.12.10/8.12.6) with ESMTP id k0VGXbvg023403 for ; Tue, 31 Jan 2006 11:33:37 -0500 (EST) Received: from 128.84.98.90 by webmail.cornell.edu with HTTP; Tue, 31 Jan 2006 11:33:38 -0500 (EST) Message-ID: <2735.128.84.98.90.1138725218.squirrel@webmail.cornell.edu> Date: Tue, 31 Jan 2006 11:33:38 -0500 (EST) Subject: paper 2 From: "Abhishek Santosh Gupta" To: egs+summary User-Agent: SquirrelMail/1.4.5 MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Priority: 3 (Normal) Importance: Normal X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00 autolearn=ham version=3.0.2 X-Spam-Level: Pastry vs Chord Routing information : Chord maintains fewer entries as opposed to both Pastry and Tapestry - chord maintains only m entries as opposed to routing table,neighbour and leaf sets. Chord maintains pointers only to its predecessors while Pastry has an entire neighbour set(with entries less than and greater than its nodeid). Chord does maintain a succesor list though. The chord paper states in the context of multiple concurrent joins causing network partitions -"these cases could be detected and repaired by periodic sampling of the ring topology". However, it does not mention how sampling could be carried out in a distributed system effectively. Node insertions : the algorithm requires O(log N) time for insertion of a node which is the least amongst all the three. Pastry vs Tapestry The algorithm for routing was exactly similar in both cases--i.e. both used ideas from radix sort for their routing policies. However, the manner in which paper dealt with node insertions and deletions was different. Node deletion :when Tapestry detects a neighbour to be invalid, it does not remove the entry from the table (which is what Pastry does) but it marks it as invalid. Thus, it gives this failed or deleted node a second chance. If the node is back again within the associated time period it validates that entry. Re-routing : In Pastry, no mechanisms existed for re-routing due to unsuccessful delivery because of a falied or malicious node. Tapestry re-routes via a alternate path after a timeout interval. Multiple roots : The root node (singular) is a single point of failure for an object. Tapestry eliminates this by assigning multiple roots to each object via addition of a salt to the object id and then carrying out hashing ( Pastry has a single root). Mobile Objects : Tapestry also includes mechanisms for dealing with objects which are moved from one server to another while Pastry does not. Tapestry also offers an algorithm to detect query hotspots and offers suggestions on locations where additional copies could be placed to improve query response times. None of the above papers deal with malicious nodes - nodes who may respond to departure messages but do not forward packets. Re-routing mechanisms seem to fail in the case of such nodes in the system. Expressive queries is another area that is not dealt with too. Abhishek Gupta From kelvinso Tue Jan 31 11:53:05 2006 Return-Path: Received: from exchfe2.cs.cornell.edu (exchfenlb-2.cs.cornell.edu [128.84.97.34]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k0VGr5422448 for ; Tue, 31 Jan 2006 11:53:05 -0500 (EST) Received: from EXCHVS2.cs.cornell.edu ([128.84.97.24]) by exchfe2.cs.cornell.edu with Microsoft SMTPSVC(6.0.3790.1830); Tue, 31 Jan 2006 11:53:05 -0500 X-MimeOLE: Produced By Microsoft Exchange V6.5 Content-class: urn:content-classes:message MIME-Version: 1.0 X-Security: message sanitized on sundial.cs.cornell.edu See http://www.impsec.org/email-tools/sanitizer-intro.html for details. $Revision: 1.148 $Date: 2004-12-19 11:59:17-08 X-Security: The postmaster has not enabled quarantine of poisoned messages. Content-Type: multipart/alternative; boundary="----_=_NextPart_001_01C62686.CD6CFA18" Subject: PAPER 2 Date: Tue, 31 Jan 2006 11:50:34 -0500 Message-ID: <2AA53C9C489B0049B43E56D28088677B2B58D1@EXCHVS2.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: PAPER 2 Thread-Index: AcYkk5F3tMseroJHQeSUarrqPTiDIQB8uKgB References: <1138511915.3962.64.camel@localhost.localdomain> From: "Kelvin So" To: X-OriginalArrivalTime: 31 Jan 2006 16:53:05.0126 (UTC) FILETIME=[CE0FE860:01C62686] X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on sundial.cs.cornell.edu X-Spam-Status: No, score=-4.9 required=5.0 tests=ALL_TRUSTED,AWL,BAYES_00, HTML_10_20,HTML_MESSAGE autolearn=ham version=3.0.2 X-Spam-Level: This is a multi-part message in MIME format. ------_=_NextPart_001_01C62686.CD6CFA18 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable =93Chord: A Scalable Peer-t-peer Lookup service for Internet Applications=94 by Stoica and =93Tapestry: An Infrastructure for = Fault-tolerant Wide-area Location and Routing=94 by Ben both present a distributed hash = table structure which is a scalable and efficient algorithm for locating = objects in large and dynamic networks.=20 Chord uses a one-dimensional, circular identifier space, which is similar to Pastry. (Similar to Pastry: An object with key k is assigned = to the first node whose identifier is equal to or follows k in the = identifier space. Each node maintains a successor and a predecessor in the id = space. A simple lookup can simply use successor to go around the id space to find = the object, but that would take O(n). ) To increase performance, Chord = maintains a finger table (similar to binary search) which contains log(n) pointers while pastry uses prefix routing to increase performance in lookup. The = ith entry in the node n finger table is the successor of n + 2i-1. = Therefore, when a node routes to an object, each hop toward the object greedily = move at least half of the remaining distance. Therefore, it results in log(n) = hops. When a peer joins the network, it routes to its successor of itself and contacts its successor of its arrival. Because Chord periodically fixes fingers, and successor, it notices a failed node and updates the corresponding entry. To improve robustness, it uses a list of successors instead of one successor, and then replicates the data to the list of successors. The design of Chord is simple Tapestry uses similar prefix routing as Pastry, but it matches the digit from right to left. The routing is very similar to Pastry, except tapestry doesn=92t maintain Leafset information. The first differences = between Pastry is that Tapestry uses soft-state to republish object to keep = location pointer up-to-date. Tapestry has more redundancy and optimization than Pastry. It allows having multiple roots, which keeps pointer to the = object in the network, and redundant links for neighbors to provide fault = tolerance. It also has other optimizations, such as caching root location if it is = visited often. However, Tapestry is more complex than Pastry.=20 ------_=_NextPart_001_01C62686.CD6CFA18 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable PAPER 2

        “Chord: A Scalable Peer-t-peer Lookup service for Internet = Applications” by Stoica and “Tapestry: An Infrastructure for = Fault-tolerant Wide-area Location and Routing” by Ben both present = a distributed hash table structure which is a scalable and efficient = algorithm for locating objects in large and dynamic networks.
        Chord uses a one-dimensional, = circular identifier space, which is similar to Pastry. (Similar to = Pastry: An object with key k is assigned to the first node whose = identifier is equal to or follows k in the identifier space. Each node = maintains a successor and a predecessor in the id space. A simple lookup = can simply use successor to go around the id space to find the object, = but that would take O(n). ) To increase performance, Chord maintains a = finger table (similar to binary search) which contains log(n) pointers = while pastry uses prefix routing to increase performance in lookup. The = ith entry in the node n finger table is the successor of n + 2i-1. = Therefore, when a node routes to an object, each hop toward the object = greedily move at least half of the remaining distance. Therefore, it = results in log(n) hops. When a peer joins the network, it routes to its = successor of itself and contacts its successor of its arrival. Because = Chord periodically fixes fingers, and successor, it notices a failed = node and updates the corresponding entry. To improve robustness, it uses = a list of successors instead of one successor, and then replicates the = data to the list of successors. The design of Chord is simple
        Tapestry uses similar prefix = routing as Pastry, but it matches the digit from right to left. The = routing is very similar to Pastry, except tapestry doesn’t maintain = Leafset information. The first differences between Pastry is that = Tapestry uses soft-state to republish object to keep location pointer = up-to-date. Tapestry has more redundancy and optimization than Pastry. = It allows having multiple roots, which keeps pointer to the object in = the network, and redundant links for neighbors to provide fault = tolerance. It also has other optimizations, such as caching root = location if it is visited often. However, Tapestry is more complex than = Pastry.

------_=_NextPart_001_01C62686.CD6CFA18-- From XXX Tue Jan 31 11:53:11 2006 Received: from zproxy.gmail.com (zproxy.gmail.com [64.233.162.193]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k0VGrB422473 for ; Tue, 31 Jan 2006 11:53:11 -0500 (EST) Received: by zproxy.gmail.com with SMTP id 12so1271450nzp for ; Tue, 31 Jan 2006 08:53:10 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:sender:to:subject:mime-version:content-type; b=tOkGSIi5KIhU0ATqKq0SR8QCW7E2M9VeCG2lPfHY+iiRB8LwmLHPs8TMtp10M0TLSd+7Rl+mz6Z/ifrZ8ywB4K629wU6fncKUNK2JMtxgqIAcTkOMn64LKkYCy2e5oe0lR/9rg1jBp6ZHDJ93tmdna7d2xRPb85nEDCdtFcUYjM= Received: by 10.64.243.17 with SMTP id q17mr2452889qbh; Tue, 31 Jan 2006 08:53:10 -0800 (PST) Received: by 10.65.205.2 with HTTP; Tue, 31 Jan 2006 08:53:10 -0800 (PST) Message-ID: <554904a70601310853m24721ee8q872869d8ee53d9be@mail.gmail.com> Date: Tue, 31 Jan 2006 11:53:10 -0500 From: "Takayuki Hoshi (TK)" To: CS615 Peer-to-Peer Systems Paper summary Subject: PAPER 2 - Takayuki Hoshi MIME-Version: 1.0 X-Security: message sanitized on sundial.cs.cornell.edu See http://www.impsec.org/email-tools/sanitizer-intro.html for details. $Revision: 1.148 $Date: 2004-12-19 11:59:17-08 X-Security: The postmaster has not enabled quarantine of poisoned messages. Content-Type: multipart/alternative; boundary="----=_Part_18295_29538092.1138726390477" X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on sundial.cs.cornell.edu X-Spam-Status: No, score=-1.5 required=5.0 tests=BAYES_00,HTML_00_10, HTML_MESSAGE,RCVD_BY_IP autolearn=no version=3.0.2 X-Spam-Level: ------=_Part_18295_29538092.1138726390477 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable THE "CHORD" PAPER In this paper, the authors present the Chord protocol, a routing protocol for a peer-to-peer lookup service for Internet applications. It is a simple looku= p system which is load-balanced, fully decentralized, scalable, fault tolerant, and name-flexible, and which uses a simple but consistent hashing method to assign keys to nodes. It solves the problem of locating key in a collection of distributed nodes and maintains routing information with frequent node arrivals and departures. In a Chord network, identifiers are ordered on an identifier circle modulo 2^m where the successor function is extensively used for key assignment and where a node may have a finger table to accelerate lookups. In Chord, each node has to maintain only O(log N) state of other nodes and lookups need O(log N) messages; O( |keys|/N) keys are expected to update their finger tables when a node joins and leaves in an N-node network. The experimental results confirm the robustness in the case of nod= e failures and show that the path length for lookups is about a half lg N There are many differences between Chord and Pastry. First, the design of Chord is significantly simpler than that of Pastry. This mainly comes from the fact that Chord's routing algorithm doesn't pay attention to key-prefixes and uses a simple hashing for key lookups with a small routing (finger) table. As as result, each node in Chord is required to maintain little amount of information as opposed to Pastry whose nodes have to store significantly more information. Chord, unlike Pastry, holds provable correctness and provable performance, in addition to its naming flexibility. One of the biggest issues of Chord, however, is that i= t doesn't consider locality since its neighbors are unrelated to network proximity. The contribution of the authors lies in providing the design of a simple, yet practical peer-to-peer protocol that can be easily implemented. Some of its future works may include modifications to the Chord protocol so that it considers locality, concentration on security and the issue of network overloading by malicious attacks like the Sybil attack. ---------------------------------------------------------------------------= --------- THE "TAPESTRY" PAPER In this paper, the authors present a scalable, decentralized, fault-tolerant, and adaptive infrastructure for wide-area location and routing called "Tapestry." It is an overlay network, similar to Pastry, that uses a modified routing algorithm of Plaxton in desirable ways and provides an explicit notion of locality, achieving the location-independent routing of messages directly to the closest copy of an object. Each node stores a neighbor map similar to Pastry, pointers to its closest nodes matching the suffix for each level, and a backpointer list that points to nodes which point to the node. The whole network may be seen as a routing mesh of neighbors. The routing information in this network is easily repaired and is purely soft state. Tapestry is also self-administering and resilient under heavy load. The experimental results demonstrate the high performance of Tapestry's decentralized object location & routing scheme and its fault-tolerance mechanisms. Despite the similarity, there are distinct differences between Tapestry and Pastry. First, whereas Pastry replicates the object and places replicas at random locations in the network, Tapestry promotes locating the nearest copy of an object fo= r each node, thereby reducing the network latency of message being sent to a particular node. Routing approaches are different as well; in particular, instead of the matching prefix method as in Pastry, each hop in Tapestry extends the matching suffix. Also, Tapestry's surrogate routing gives assurance on the weaker bounds on the number of logical bounds in routing distances, thereby, unlike Pastry, giving a guarantee to find an object, if it is reachable. The contributions of the authors include the improvements to Plaxton's routing algorithm, augmenting robustness, scalability, dynamic adaptation, and self-administration. Tapestry's ability to deliver messages to the closest copy of objects (or services) in a location independent manner, is also notable. As the authors suggest, future works may include further performance analysis unde= r a variety of conditions and parameters and how it can be made more secure and resilient to malicious attacks. ------=_Part_18295_29538092.1138726390477 Content-Type: text/html; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable
THE "CHORD" PAPER

In this paper, the authors present t= he Chord protocol, a routing protocol for a
peer-to-peer lookup service = for Internet applications. It is a simple lookup system
which is load-ba= lanced, fully decentralized, scalable, fault tolerant, and
name-flexible, and which uses a simple but consistent hashing method to= assign keys
to nodes. It solves the problem of locating key in a collec= tion of distributed nodes
and maintains routing information with frequen= t node arrivals and departures. In a
Chord network, identifiers are ordered on an identifier circle modulo 2= ^m where the
successor function is extensively used for key assignment a= nd where a node may have
a finger table to accelerate lookups. In Chord,= each node has to maintain only O(log
N) state of other nodes and lookups need O(log N) messages; O( |keys|/N= ) keys are
expected to update their finger tables when a node joins and = leaves in an N-node
network. The experimental results confirm the robust= ness in the case of node
failures and show that the path length for lookups is about a half lg N=

There are many differences between Chord and Pastry.  First, t= he design of Chord is
significantly simpler than that of Pastry. This ma= inly comes from the fact that
Chord's routing algorithm doesn't pay attention to key-prefixes and use= s a simple
hashing for key lookups with a small routing (finger) table.&= nbsp; As as result, each
node in Chord is required to maintain little am= ount of information as opposed to
Pastry whose nodes have to store significantly more information. Chord,= unlike
Pastry, holds provable correctness and provable performance, in = addition to its
naming flexibility.  One of the biggest issues of C= hord, however, is that it doesn't
consider locality since its neighbors are unrelated to network proximit= y.

The contribution of the authors lies in providing the design of a= simple, yet
practical peer-to-peer protocol that can be easily implemen= ted. Some of its future
works may include modifications to the Chord protocol so that it consid= ers locality,
concentration on security and the issue of network overloa= ding by malicious attacks
like the Sybil attack.


------------= ------------------------------------------------------------------------


THE "TAPESTRY" PAPER

In this paper, the author= s present a scalable, decentralized, fault-tolerant, and
adaptive infras= tructure for wide-area location and routing called "Tapestry."&nb= sp; It is
an overlay network, similar to Pastry, that uses a modified routing alg= orithm of
Plaxton in desirable ways and provides an explicit notion of l= ocality, achieving the
location-independent routing of messages directly= to the closest copy of an object.
Each node stores a neighbor map similar to Pastry, pointers to its clos= est nodes
matching the suffix for each level, and a backpointer list tha= t points to nodes
which point to the node. The whole network may be seen= as a routing mesh of
neighbors.  The routing information in this network is easily repa= ired and is purely
soft state. Tapestry is also self-administering and r= esilient under heavy load. The
experimental results demonstrate the high= performance of Tapestry's decentralized
object location & routing scheme and its fault-tolerance mechanisms= .

Despite the similarity, there are distinct differences between Tap= estry and Pastry.
First, whereas Pastry replicates the object and places= replicas at random locations
in the network, Tapestry promotes locating the nearest copy of an objec= t for each
node, thereby reducing the network latency of message being s= ent to a particular
node. Routing approaches are different as well; in p= articular, instead of the
matching prefix method as in Pastry, each hop in Tapestry extends the m= atching
suffix.  Also, Tapestry's surrogate routing gives assurance= on the weaker bounds on
the number of logical bounds in routing distanc= es, thereby, unlike Pastry, giving a
guarantee to find an object, if it is reachable.

The contributio= ns of the authors include the improvements to Plaxton's routing
algorith= m, augmenting robustness, scalability, dynamic adaptation, and
self-admi= nistration. Tapestry's ability to deliver messages to the closest copy of
objects (or services) in a location independent manner, is also notable= . As the
authors suggest, future works may include further performance a= nalysis under a
variety of conditions and parameters and how it can be m= ade more secure and
resilient to malicious attacks.



------=_Part_18295_29538092.1138726390477-- From tudorm Tue Jan 31 11:57:27 2006 Return-Path: Received: from exchfe2.cs.cornell.edu (exchfenlb-2.cs.cornell.edu [128.84.97.34]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k0VGvR424135 for ; Tue, 31 Jan 2006 11:57:27 -0500 (EST) Received: from exchfe1.cs.cornell.edu ([128.84.97.33]) by exchfe2.cs.cornell.edu with Microsoft SMTPSVC(6.0.3790.1830); Tue, 31 Jan 2006 11:57:27 -0500 Received: from [192.168.0.6] ([65.110.147.185]) by exchfe1.cs.cornell.edu over TLS secured channel with Microsoft SMTPSVC(6.0.3790.1830); Tue, 31 Jan 2006 11:57:26 -0500 Message-ID: <43DF96C9.7070808> Date: Tue, 31 Jan 2006 11:56:41 -0500 From: Tudor Marian User-Agent: Thunderbird 1.5 (X11/20051201) MIME-Version: 1.0 To: egs+summary Subject: PAPER 2 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-OriginalArrivalTime: 31 Jan 2006 16:57:26.0873 (UTC) FILETIME=[6A135490:01C62687] X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.2 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.0.2 X-Spam-Level: Chord differs from Pastry in several key points. Both overlays split the identifier space into a modulo n ring, but in Chord's case the keys are located at the node with the immediately successor id, as opposed to Pastry where a node is responsible for the keys who's id's are closer to the node's id. As a consequence, Chord doesn't require any leaf set, and the routing table consists of m entries (m is the number of bits the keys have) such that the i-th entry in the table of node n holds the first node that succeeds n by at least 2^{i-1} in the circle. Chord doesn't make any use of proximity metric, hence it may not take advantage of locality, which is the case of Pastry. Node joining is different as well, a new chord node n that knows about n' and wants to join will delegate the task of filling in it's finger table to n'. This has an upper bound of O(m logN), which is more than the O(log N) in Pastry's case. Each Chord node runs a stabilization periodic algorithm to take care of churn, moreover nodes keep not just the finger routing tables but predecessor pointers as well. Tapestry is very much like Pastry, both in the way the routing works with prefix/suffix of addresses/ids, insertion and deletion algorithms and storage overhead costs. Tapestry however caches object pointers along query routes as opposed to PAST's replica placement of objects at several nodes with node id in the vicinity of the object's id. Tudor From ids3 Thu Feb 2 04:21:57 2006 Return-Path: Received: from authusersmtp.mail.cornell.edu (granite1.mail.cornell.edu [128.253.83.141]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k129Lu414673 for ; Thu, 2 Feb 2006 04:21:56 -0500 (EST) Received: from [128.253.212.208] (r253212208.resnet.cornell.edu [128.253.212.208]) (authenticated bits=0) by authusersmtp.mail.cornell.edu (8.13.1/8.12.10) with ESMTP id k129LuOq005692 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for ; Thu, 2 Feb 2006 04:21:56 -0500 (EST) Message-ID: <43E1CF35.90101> Date: Thu, 02 Feb 2006 04:21:57 -0500 From: Ivan Stoyanov User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716) X-Accept-Language: en-us, en MIME-Version: 1.0 To: egs+summary Subject: PAPER 2 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.6 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.0.2 X-Spam-Level: The main idea of the paper is to organize peers in an multidimentional virual space. Similar to Chord, keys to data are uniformly distributed accross the participating peers using a hash function mapping. Nodes need to maintain links for their immediate neighbors only, so the size of the routing table is 2d. Routing in CAN takes O(n^1/d). Node joins affect only O(d) nodes. CAN uses soft-state routing table updates. Absence of such update messages signals that the node has failed. The system does not have a good way of handling crashed nodes and can quickly become inconsistent when neighbors disagree on which nodes and up or down. In addition, an attacker can repeatedly report its neighbors as failed and thus easily disrupt the system. Another problem with the paper is that the parameter d cannot be adjusted dynamically. The paper, however, provides good theoretical base and does address locality issues, replication and caching.