On Mon, Mar 06, 2000 at 07:18:12AM +0100, Johann G. Hautzinger wrote:
> woody weaver wrote:
> >
> > A couple of points:
> >
> > 1. (obligatory mathematical note from an ex math professor) The
> > rainwall actually scales sublinearly. Each machine (tries to) talk to
> > every other machine, and there are election rules and etc. That sort of
> > overhead increases as the square of the number of firewalls, and so at
> > some point, the complexity of that computation would start getting
> > significant. (end obligatory math note)
> as an ex pupil of a math professor i doubt this ... if there were two
> firewalls each one would have to talk to the other (=2x1), if there were
> three, this would be 6 (=3x2x1) ... with n firewalls this would be
> nx(n-1)x(n-2)...x1 or n! in short. looks to me as if this was faculty,
> no?
Grin. The election rules allow you to escape having to maintain a 2^n
or n! complexity. Consider it from the perspective of a single CPU.
Periodically, I'm going to go out and talk to every other machine [O(n)]
and see if they are saying that they are working. For example, lets
assume we have three CPU's, A, B, and me at C. If A tells me he
is working, and B tells me he is not working (or fails to communicate)
I don't necessarily have to go back to A and ask him what he thinks
about B. I just trust my data -- to a point. Moreover, when I
communicate with A, that also works for him talking to me, so the
attempted communications are (C,A), (C,B), (A,B) -- only 3, not 6.
So its n * O(n) = O(n^2), not worse.
In addition, the election stuff becomes important if, for example, I try
to talk to A and B, and fail to both. I could assume that for some
strange reason, both machines have simultaneously died, and I should
take over the work for the whole cluster. That's probably the wrong
decision, though; more likely is that I've died, and A & B should take
over for me. So if the clique of machines I can talk to is less than
half of the clique that was working a few ticks ago, I should probably
conclude I'm in a failed clique, and wait... or at least, that is where
the deep magic in the communication process lies.
yes?
--woody
>
> *greetz* from vienna
>
> Hannes
>
> --
> Johann Georg Hautzinger, email: trema_at_eic.at, Tel.: 531 00 1907
> Erste Bank AG - OE 0423 - Orga./Entw. Treasury u. Orga.Wertpapier
> Boersegasse 14, 1010 Wien http://treasury.erstebank.at
Received on Mar 12 2000
Intro
