Middle men wanted

[Joe Armstrong]

On Wed, 5 May 2004, Ulf Wiger (AL/EAB) wrote:

> 
> 
> > -----Original Message-----
> > From: owner-erlang-questions@REDACTED
> > [mailto:owner-erlang-questions@REDACTED]On Behalf Of Joe Armstrong
> > Sent: den 5 maj 2004 11:25
> > To: erlang-questions@REDACTED
> > Subject: Middle men wanted
> > 
> > 
> > 
> > 
> >    I'm collecting middle men - let me explain.
> > 
> >    Cheers
> > 
> > /Joe
> > 
> >   (warning long text)
> 
> 
> Perhaps you could add some thinking about how to handle issues
> like fault tolerance, in-service upgrade, etc... you know, that
> OTP framework that you and some others invented a few years ago. ;)

  Well it's like this (rolling up sleeves)

  What I'm trying  to do is make distributed Erlang  work with an very
large number of nodes (but not as we do things today)

  In distributed  Erlang all  nodes now about  all other  nodes. This
doesn't work if there are very large numbers of nodes.

  I now want to ask what nodes should node J know about? - to answer this
I'm experimenting with the following (this was previously posted to the
planet lab mailing list)


>>  Assume we number  the machines 1..N where N  = 2^K (a K of  10 or 11
>>should do)
>>
>>  Define  the neighbors  of  N to  be  all machines  with a  Manhattan
>>distance of 1 from N.
>>
>>  I'll give an example in base 2^4.
>>
>>  Machine 6 has a binary address 0110 in base 16
>>
>>  The following machines have a Manhattan distance 1 from 0110
>>
>>	1110 0010 0100 0111 (ie machines 14, 2, 8 and 7)
>>
>>  These are formed by changed one bit at a time from 0110
>>
>>  Thus "Manhattan" neighbors of machine 6 are 14,2,8 and 7
>>
>>  Each machine has *exactly* four neighbors.
>>
>>  In 2^11 each machine has *exactly* 11 neighbors.
>>
>>  This give a very nice way of connecting all the nodes together. In a
>>fully  saturated  net of  2^11  nodes  all  machines have  exactly  11
>>neighbors which  are symmetrically  placed (they are  all edges  of an
>>11-D hyper cube).
>>
>>  You can use this structure to broadcast changes to all nodes, gather
>>statistics etc.
>>
>>  If the address space is not fully saturated you can include nodes at
>>a Manhattan distance  of 2 etc.  - this  arrangement has the properties
>>that:
>>
>>  1) it  should  relatively  easy  to  ensure that  there  are  always
>>sufficient number of "nearby" nodes  (in Manhattan space) to any given
>>node to ensure  that individual nodes do not  become disconnected from
>>the network.
>>
>>  2) The system is  symmetric - ie there is no  hierarchy and all nodes
>>have exactly the same number of neighbors.
>>
>>  3) Any two nodes are a maximum of K hops apart.
>>
>>  4) Operations on the entire network can be done in log time.
>>
>>   ---
>>
>>  I have made  an experimental "empty" server which  uses this kind of
>>network.
>>
>>  The idea is to have a  null server which becomes a placeholder for a
>>real server. The  empty server can be sent a  higher order function to
>>paramertise it and to tell it  to become a specific server. Thus I can
>>send a  "become an HTTP server"  function to the empty  server, and it
>>turns into an HTTP server.
>>
>>  I will  be making this available  fairly soon - turning  this into a
>>name server etc. is pretty easy.
>>
>>  I can offer simple XML services - but if you want to really have fun
>>you'll need to run an Erlang client :-)

   Now so far, I've made the polyprotocol ports and the apply server.
So all I have to do is let each node chat to it's Manhattan neighbors.

   This gets me started and gets the network strongly connected.

  In  (say) a network  of 2^32  nodes each  node would  be permanently
connected to it's  32 Manhattan distance 1 neighbors -  or if they do
not exists to distance 2 neighbors  etc. The purpose of this is just
to make  sure that individual nodes  do not get  disconnected from the
network - for this to happen all 32 nodes must fail (or the local link
go  down) -  then  I'd add  routing  etc. as  different and  logically
separated overlays ...

   After this I'll add error correction etc 

   Then I'll add leadership elections

   And then a layer with distributed hash tables (like chord, tapestry etc)
and then (finally) the applications

   BWT Mike pointed this out to me:

http://msdn.microsoft.com/longhorn/default.aspx?pull=/msdnmag/issues/04/01/indigo/default.aspx

   (don't say I told you so :-)



   /Joe



> 
> There's not necessarily much discrepancy there, but I believe it
> would be helpful to reveal how you've thought about it. 
> Proposing a uniform way of reporting unexpected things would 
> also be good; in one part of your examples, you use io:format/2,
> while in another, you use something called ed_log:error/1.
> 
> /Uffe
>