[p2p-hackers] part 2: proxying and introduction: the two fundamental operations of emergent networks

[zooko at zooko.com]

About two weeks ago I posted a message entitled "proxying and introduction: the
two fundamental operations of emergent networks":

http://zgp.org/pipermail/p2p-hackers/2001-August/000258.html


 an anonymous fan wrote:
>
> This is great stuff, Zooko.  It has really got me thinking.  ...too bad that the
> following thread was about MN more than how the resulting emergent network
> behaves.

Thanks!

Yes, I was sort of hoping that Oskar or someone would pick up the implicit
challenge.  See, AFAICT, Freenet and most other networks have focussed
exclusively on proxying and neglected introduction.

There is a sound theoretical reason for concentrating on proxying, as Oskar can
lucidly explain: that with introduction alone, and no proxying, the size of
your horizon is proportional to the size of your local state (i.e. you have to
remember everyone's id and address, or whatever, in order to use them).
Therefore introduction is "non-scalable" in Oskar's opinion.

The counterargument to that is that introduction is *required*.  A new node is
created and it is not connected to anyone in the network.  How does it get
connected?  That is the problem of Original Introduction.  People who neglect
introduction end up with some kind of kludge to do Original Introduction (e.g.
node-lists on HTTP, the MN Meta Trackers, or manually configuring your node to
connect to other nodes), and with no transitive introduction at all.

But that gives a central point of failure (e.g. you can take out the HTTP
server that newcomers depend on in order to connect to the network), or at
least passes the buck for having a robust, emergent introduction service off to
the HTTP or the manual configuration or whatever.

So a really good emergent network needs both: proxying *and* introduction.


IMO a really good emergent network is going to have:

1. good Transitive Introduction

2. good Original Introduction, which should utilize the features of the
    Transitive Introduction -- instead of being a wholly separate behavior with
    different properties
 2.a. easy-for-users Original Introduction such as "type in the DNS or IP of
    your friend who is already connected to the Emergent Net", or "scan local
    net / local wireless area for Emergent Net nodes"
 2.b. an easily accessible default original introduction service i.e. a set of
    redundant original introducer nodes like the MN Meta Trackers

3. Proxying for superlinear effective horizon


But in the immediate term, I don't really care about number 3: proxying of
operations (although I do care about relaying of messages) until the number of
nodes on my network times the amount of local space it takes to carry on a
relationship is approaching the amount of local space that I am willing to
allocate on each node.  Quick back-of-the-envelope calculations go like this:

128 bytes for addressing information (could do with less, but let's be a bit
pessimistic), 128 bytes for crypto information (could do with less, again), and
let's just say 256 bytes for local reputation (i.e. what you know about that
other node, how it performs, etc.) for a nice round number of 512 bytes per
counterparty.  (Note: if you really wanted to squeeze I believe you could get
this down to 20 bytes for crypto and addressing, and maybe 20 bytes for local
reputation for a total of 40 bytes per counterparty, but let's be pessimistic
while writing on the back of this particular envelope...)

So if users are willing to allocate up to 128 MB of local persistent storage
for maintaining their relationships in the network, then each node can have
direct relationships with at least 2^18 == 262,144 other nodes.

By the time this 2^18 limit is actually hurting my network, Freenet v0.5 will
be out, and I can learn from all of the applied research that Freenet has done
in effective proxying techniques and then add those proxying techniques into my
network.  Of course, it's also possible that harddrives will be bigger by then
and users will be willing to allocate more than 128 MB just for peer
relationships.


Now my purpose here is definitely not to criticize proxying as such!  Proxying
is very important for a lot of reasons.  For one thing, if you don't have
proxying then local network usage is *also* proportional to the effective
network horizon of a given operation (although there of several things that can
ameliorate that problem including multicast) and for another thing, smaller
devices with tighter storage constraints are more likely to need proxying.
Another reason is that there may be some theoretical or engineering benefits
to combining message-relay with higher-layer operations (as Freenet does) as
opposed to making them separate abstraction layers (as Mojo Nation does).
Finally, as Lucas Gonze pointed out in private e-mail, proxying allows for more
complex relationships, for example maybe you don't *want* to introduce your two
friends to each other, because you don't want them to be able to exchange
information without giving you access to it.


So my purpose here is *not* to denigrate proxying, but to draw attention to the
important of introduction.  Here is a quick recap of the reasons why
introduction is vitally important to emergent networks:

1. Introduction is required, in order to have a network at all in the first
   place.
2. You can do non-transitive Original Introduction, but then it must be
   centralized and/or manually managed by humans.  (Which is okay for a lot of
   applications.)
3. If you are going to implement transitive, automatic Introduction in order to
   have robust, automatic joining of the network, then why not use it?  e.g.:
  a. You already use it to go from 1 neighbors to K neighbors (where K is the
   minimum number of neighbors that you need to be part of the network), then
   why not use it to go from K neighbors to M neighbors, where M is a higher
   number for greater efficiency in some cases.
  b. Use automatic transitive introduction to dynamically heal and optimize the
   network.
4. Introduction may make for more efficient networks than proxying in some
   cases (those cases where higher degree of connectivity is better).
  a. One such case seems to be when the total number of nodes on the entire
   network is sufficiently small, which the current state of Mojo Nation.


Regards,

Zooko

P.S.  Thanks again, for those who didn't read my earlier message, to Oskar,
Adam Langley, and Bram for getting me thinking about this last year, and to
Mark Miller for teaching me the ways of Granovetterism (== Introductionism).

P.P.S.  I don't know that much about Freenet, and it probably already has some
transitive introduction features, but the Freenet people have not discussed it
in terms of "Proxying and Introduction: The Two Fundamental Network Operations"
before now as far as I know.