Re: [babel] babel Digest, Vol 17, Issue 5

[Juliusz Chroboczek <[e-mail]>]

I've now had some time to spend on the rest of your mail.

> hmm, I am not a big friend of "eventual consistencies" since I don't like my
> customers to "eventually" pay the bills. We do and must live with epsilon
> which is what e.g. OSPF is doing and Babel does as well

I'm not familiar with the "epsilon" terminology, but if I understand
correctly what you mean -- OSPF encapsulates the probabilistic aspect
within the reliable flooding algorithm.  Assuming that flooding
terminates, OSPF is correct.  Of course, no bound can be given on the
termination of flooding, but at least the probabilistic nature of the
protocol is cleanly encapsulated within the flooding algorithm.  All the
remainder of the protocol is completely deterministic.

This is very different from Babel, which does not rely on a reliable
transport, and therefore carries probabilities throughout the protocol.
Hence the strong invariant (loop-freedom), which has the side benefit of
allowing a somewhat more lax style of specification.

> Yeah, in summary though I don't think Babel is anything new much really in
> terms of distributed algo nature

I agree, most of the good ideas in Babel were stolen from other protocols
(RIP, DSDV, EIGRP, BGP).

> and FSMs would do a fine job on Babel as well.

I don't know how to do that.  I don't know how to express in an FSM the
notion that "When to acquire a neighbour is an implementation detail, as
long as a neighbour is acquired soon enough.  A simple strategy is to
create a neighbour table entry as soon as we receive a well-formed Babel
packet from a given IP, but other strategies are possible".

> (acknowledging the fact again that Babel is significantly simpler as
> algorithm and somewhat more positively stable than link-states).

Quoting for my personal enjoyment :-)

> And to completely split the hair here four ways, the proof exists that NFA and
> class equivalent to DFA so head I win and tails you loose ;-) 

I don't think the theorem applies here.  The equivalence only states that
the class of recognised languages is the same, nothing more.

-- Juliusz