[p2p-hackers] DHT generalization for purposes other than network performance

[zooko at zooko.com]

I'm going to paraphrase a blog entry I wrote some years ago and then mention
some newer research that is related.

In January 2003 [1] I wrote something like:

> Thanks to Peter Marbach for the discussion that prompted this insight.
> 
> A network is defined on top of an underlying network. The first emergent 
> networks (Chord), assumed that the underlying network was (a) fully 
> connected and (b) homogeneous in the sense that any hop was considered to be 
> just as expensive as any other hop. The most important contribution of 
> Pastry (and then of Kademlia) is to treat the underlying network as 
> heterogeneous, in the sense that some hops are considered more expensive 
> that others. For Pastry, they chose to make these costs reflect network 
> performance (i.e. latency or throughput) so that Pastry would optimize for 
> faster routing (e.g. don't send packets through Japan when they are on their 
> way from Canada to USA). For Kademlia, they chose to make these costs 
> reflect uptime of peers in order to optimize for stability. So my big
> realization is:
> 
> *** Trust (or vulnerability, or exposure) can also be modelled in the same 
>     way, as costs on the links of the underlying network.
> 
> In addition, the underlying network may be incompletely connected, either 
> because of (a) trust disconnects, (b) firewalls, NATs, censorship, 
> terrorism, (c) the underlying network doesn't have complete routing e.g. 
> wireless ad hoc networks.
> 
> This encourages me a lot: the fact that mainstream emergent network 
> researchers like Project IRIS might develop techniques for overlay networks 
> to work on more general underlying networks (especially non-fully-
> connected), and that these techniques can then be applied to trust networks.


The recent research that I wanted to cite was Michael Freedman et al. analyzing
practical details of how current DHTs work atop non-fully-connected underlay
networks: [2].  

[2] doesn't propose any good general solution, and indeed it speculates that a
fresh new DHT designed to handle non-fully-connected underlays may be needed.

Regards,

Zooko

[1] http://www.zooko.com/log-2003-01.html#d2003-01-23-trust_is_just_another_topology
[2] "Non-Transitive Connectivity and DHTs"
    http://www.scs.cs.nyu.edu/~mfreed/publications/