Re: Multimaster Algorithm

[Dave Horsfall <daveh@ci.com.au>]

On Thu, 17 Oct 2002, Derek Simkowiak wrote:

> 	Those "few milliseconds" that we are waiting gives the other
> master a chance to process our simultaneous update of the same entry.
> This is analogous to ethernet fallback (is that the right terminology?).
> The "few milliseconds" should be a randomly-chosen number within a small
> range, again just like ethernet.  (There are algorithms for picking these
> "few milliseconds"  times, with fallback if further collisions occur, but
> I don't know much about them.  Somebody with ethernet experience will need
> to comment.)

Aha - one I can answer!

I think your referring to the "collision detect" part of CSMA/CD (carrier
sense multiple access with collision detect).  When a collision is
detected, all transmitters back off for a random time then try again.
The actual backoff rule is "binary exponential backoff" i.e. you double
the timeout after each failed attempt.  In practice, you double up to 10
times (no more than 2^10 hosts on an Ethernet) and give up after 16 times.

> 	Can anyone see a reason why the above algorithm would not ensure
> multimaster replication without conflicts?  If somebody can help me with
> the fallback algorithms, I would be happy to work on implementing this.
> In fact, this could all be implemented in slurpd, so we wouldn't have to
> muck around with the slapd code at all (so no more "experimental" #defined
> junk in the database code).

Sounds like it should work...  Note that in our case, we could potentially
have masters on the other side of the world, so we'd be looking at delays
in the order of seconds.

-- 
Dave Horsfall  DTM  VK2KFU  daveh@ci.com.au  Ph: +61 2 9906-4333