Middle men wanted
Wed May 5 15:03:05 CEST 2004
On Wed, 5 May 2004, Ulf Wiger (AL/EAB) wrote:
> > -----Original Message-----
> > From:
> > [mailto:]On Behalf Of Joe Armstrong
> > Sent: den 5 maj 2004 11:25
> > To:
> > 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
>> 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
>> If the address space is not fully saturated you can include nodes at
>>a Manhattan distance of 2 etc. - this arrangement has the properties
>> 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
>> 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
>> 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:
(don't say I told you so :-)
> 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.
More information about the erlang-questions