[prev in list] [next in list] [prev in thread] [next in thread] 

List:       linux-ha-dev
Subject:    Re: [Linux-ha-dev] In search of a good algorithm
From:       Alan Robertson <alanr () unix ! sh>
Date:       2002-01-15 13:33:56
[Download RAW message or body]

Lars Marowsky-Bree wrote:
> 
> On 2002-01-14T13:58:02,
>    Ram Pai <linuxram@us.ibm.com> said:
> 
> >       Is there a algorithm better than O(n square) that can effectively
> >       compute a group with the largest membership?
> 
> I think if you are starting from scratch (ie, no group yet formed), N^2 is the
> best you can do, because you have to verify N:N connectivity at least once.
> 
> However, the normal case is nodes leaving or joining the cluster, where you
> only have to verify connectivity between the new node and the existing
> cluster, which can be done in O(N).
> 
> The initial setup of a n=99 cluster thus might take 10-20 seconds, but adding
> the 99ne node will be done in under a second.

Actually, even O(N^2) isn't so bad.  As Nelio points out, the optimal answer
is probably NP-hard.  So, getting a reasonable approximation in O(N^2) time
is probably as good as it gets.

For N=100, with each operation taking 100usec, that gives 10^6 usec which is
1 sec.  The question is, how fast can you make the constant of
proportionality ;-).

If our first attempt works fine for initial forming of a cluster of 100, in
a handful of seconds, we'll be pretty happy.

The main thing is to get it to work at all first, then get it to work fast
later.

There are all kinds of options to get it to work fast later...

New algorithms, subclusters "under the hood" (hidden from user space),
etc...

	-- Alan Robertson
	   alanr@unix.sh
_______________________________________________________
Linux-HA-Dev: Linux-HA-Dev@lists.community.tummy.com
http://lists.community.tummy.com/mailman/listinfo/linux-ha-dev
Home Page: http://linux-ha.org/
[prev in list] [next in list] [prev in thread] [next in thread]