From khare@pest.w3.org Tue Feb 13 21:03:10 1996
Return-Path: <khare@pest.w3.org>
Received: from www10.w3.org by theory.lcs.mit.edu (5.65c/TOC-1.2S)
id AA00511; Tue, 13 Feb 96 21:03:05 EST
Received: from pest.w3.org by www10.w3.org (5.0/NSCS-1.0S)
id AA26707; Tue, 13 Feb 1996 21:03:01 +0500
Received: by pest.w3.org (NX5.67f2/NX3.0S)
id AA28522; Tue, 13 Feb 96 21:03:04 -0500
Message-Id: <9602140203.AA28522@pest.w3.org>
Content-Type: text/plain
Mime-Version: 1.0 (NeXT Mail 3.3risc v118.3)
Received: by NeXT.Mailer (1.118.3)
From: Rohit Khare <khare@pest.w3.org>
Date: Tue, 13 Feb 96 21:02:59 -0500
To: w3t@w3.org
Subject: Chat with David Karger: Solving the 'DNS Problem'
Cc: FoRK@xent.w3.org, schooler@cs.caltech.edu, karger@theory.lcs.mit.edu,
mslevine@theory.lcs.mit.edu
Reply-To: khare@w3.org
X-Url: http://www.xent.w3.org/
Content-Length: 3395
Status: R
Dave K. came up to me and inconsiderately interrupted me while I was busily
schmooozing a grad student from Lynch's group, and outlined a pretty decent
solution to the 'DNS' problem. I am completely misrepresenting his work and
may be greviously wrong at several points... with that proviso in mind:
There's a set of N machines, arbitrarily connected together. The rule, as
stated by TimBL, is to use no more than root-N storange at any node.
Each machine has an address A, chosen from a fixed set (0..maxIP), and an
identity string I.
The solution is a pseudorandom 'coloring' function that can hash an I into
one of K colors. The set of k-colored machines is randomly distributed about
the network. Each machine n, though, can discover via gossip the 'nearest'
machine of each of the other K-1 colors. Similarly, the machine n can find the
nearest other machine of color-k and join a gossip-tree for keeping complete
information on the machines of that color.
Then, to resolve an I' -> A, talk to any machine of the color hash(I'). It
could be the nearest, which you know, or a random machine, which distributes
the load in case of failure.
Scaling N. This is one of the biggest objections: if you have a thousand
colors in the world, but another 100k machines join the network, how can we
'renumber' the color partitions? One is to assume that local-node storage
increases with Moore's Law, and 1000 colors is good for all time. The problem
is that Moore's Law is a statistical property, not an invariable expansion of
every node.
We use a transition strategy of running a 1000-colored world of tables and a
1001-colored set for a few weeks/days/minutes, and propagate the new,
monotonically-increasing value to the world. Alternatively, David mentioned
adding new tiers to reduce memory load from N^1/2 to N^1/3 (at the cost of
going from O(2) hops to O(3))
Narrow Pipes. There's no direct use of the underlying network topology,
though my guess is this would 'just work' when faced with a narrow
internetwork connection; a node would fill out it's 'zone' of K-1 colored
hosts with notes from 'this side' of the link.
Dynamic host-up, host-down. Not clear at all yet how reasonably this mesh
react to new hosts and the transience of existing hosts. What is known is that
if a host goes down, it's not going to be hammered with requests, nor its
alternate, if we each query is aimed at a different host of that color. [Of
course, I'm a little unclear on how you find other same-color hosts in the
first place, without asking in advance]
Deployment... well, we just won't talk about that in public, OK? I would
guess, though, that we could consider running this color protocol only between
some subset of the machines in the world, where I is restricted to a domain
name and A is a domain server (sound familiar?) Simulations seem key to taking
this idea further
Bottom line: unless we can find a way to change the requirements on him or
punch a hole, we may have to go forward with Dr. K and his students on this
one...
Rohit
PS. Everyone should feel free to blame Dave Raggett for planting the silly
fix-DNS idea in Dr. K's head
PPS. Today's Theorist Tip-Off: Only a theorist can latch onto root-n as a
'real number'. As in "Hey, N's a number, and N^1/2 is a *real* number!"
(Thanks to Matt Levine)