[p2p-hackers] Paradigma Question: DHT's or Small World?

[Bryan Turner]

Alex,

>  Churn: The system should support a high churn rate of peers/high churn
rate of
> objects.  By the way, since these hypotheses are intuitive but unproved,
does
> anybody know a theoretical or experimental work, that proofed them?
Furthermore,
> maybe this question is a bit naive, but what exactly is high?

	See [1,2] for some discussion of churn and the "half-life" of a
network.  These models were built from Chord, but the results are useful to
both systems.

	To answer your question more directly: "high" means close to the
half-life of your network.  The half-life being the time it takes half the
nodes in the network to cycle off of it.  If your churn rate is higher than
this, you effectively cannot keep the network together, as it is outpacing
your stabilization protocol.  If your churn is lower, then you get a stable
network.  So a "high" churn rate is just under your network's half-life.

> Profile locality: One peer maps to one user. Probably a user is not
interested
> or willing to transfer it's local profile to a global index but likes to
keep
> it locally, e.g. for anonymity or to delete entries.

	Depending on system design, anonymity may be improved if a 'peer' is
actually a darknet of users.  This provides k-anonymity within the group.
See [3,4] for such protocols.  Probably not relevant to your request, but
it's fascinating research anyway..

> Popularity:  If most of the searches go for popular objects, small world
may
> be the first choice. For example, this is the case for most music sharing
networks.

	The greater practical concern for popularity is resolving "flash
crowds" gracefully in the system.  Neither DHT/Small World models define the
behavior for this case.  You should review some of the various solutions to
this problem (too many to reference, but see [5], Section 3, and [6],
Section III, for an example).

> What kind of application scenario suits to this requirements?

	Any form of data repository where the primary user is an individual.
For instance: Phone Book, Restaurant Guide, News Portal, Product Catalog,
Wiki, etc..

Hope that helps!
--Bryan
bryan.turner at pobox.com

[1] Observations on the Dynamic Evolution of Peer-to-Peer Networks
	David Liben-Nowell, et. al.
	http://citeseer.ist.psu.edu/liben-nowell02observations.html

[2] Analysis of the Evolution of Peer-to-Peer Systems
	David Liben-Nowell, et. al.
	http://citeseer.ist.psu.edu/liben-nowell02analysis.html

[3] k-Anonymous Message Transmission, Luis von Ahn, et. al.
	http://www-2.cs.cmu.edu/~abortz/work/k-anon-final.html

[4] A New k-Anonymous Message Transmission Protocol
	Gang Yao, Dengguo Feng
	http://dasan.sejong.ac.kr/~wisa04/ppt/9A2.pdf

[5] Novel Architectures for P2P Applications: The Continuous-Discrete
Approach
	Moni Naor, Udi Wieder
	http://citeseer.ist.psu.edu/554254.html

[6] Small World Overlay P2P Networks, Ken Y. K. Hui, et. al.
	
http://www.cse.cuhk.edu.hk/~cslui/PUBLICATION/iwqos2004_small_world.pdf

-----Original Message-----
From: p2p-hackers-bounces at zgp.org [mailto:p2p-hackers-bounces at zgp.org] On
Behalf Of Alexander Löser
Sent: Friday, February 04, 2005 7:58 AM
To: Peer-to-peer development.
Subject: Re: [p2p-hackers] Paradigma Question: DHT's or Small World?

Thank you very much in sharing this discussion!!  You gave me very valuable
comments on the design question to choose either small world or DHT's.  If I
understood your arguments right, small world should be the preferred
paradigm, if the system design requires the following (hard or soft)
features:

(Hard features)
Churn: The system should support a high churn rate of peers/high churn rate
of objects:
By the way, since these hypotheses are intuitive but unproved, does anybody
know a theoretical or experimental work, that proofed them? Furthermore,
maybe this question is a bit naive, but what exactly is high?

Complex queries: The system allows a user to pose complex queries, e.g.
several keywords, or if I speak about meta data annotated documents more
than one (semantic) predicate per query.

(Soft features)
Profile locality: One peer maps to one user. Probably a user is not
interested or willing to transfer it's local profile to a global index but
likes to keep it locally, e.g. for anonymity or to delete entries.

Popularity:  If most of the searches go for popular objects, small world may
be the first choice. For example, this is the case for most music sharing
networks.

Community search: Depending on the shortcut creation strategies between
friends on a small world network, the small world paradigm supports the data
sharing graph between people with similar interests. By the way: Does it
also support similar semantics?

What kind of application scenario suits to this requirements? I think of a
networked desktop search application. Similar to Gnutella, some people
publish some of its documents, most don't. Some of them are annotated by
meta data, probably with the same vocabulary or within the same ontology,
some not. Users pose keyword queries, similar in a single desktop search
engine.  Queries either match the documents filename, folder or (if any)
documents meta data.

Would be the small world paradigm support such a system?

Alex
--
___________________________________________________________

  Alexander Löser
  Technische Universität Berlin
  http://cis.cs.tu-berlin.de/~aloeser/
  office : +49- 30-314-25551
  fax    : +49- 30-314-21601
  skype  : hallo.alex
___________________________________________________________


_______________________________________________
p2p-hackers mailing list
p2p-hackers at zgp.org
http://zgp.org/mailman/listinfo/p2p-hackers
_______________________________________________
Here is a web page listing P2P Conferences:
http://www.neurogrid.net/twiki/bin/view/Main/PeerToPeerConferences