Re: efficient compare
Date: Sun, 23 Apr 2006 21:48:53 GMT
Message-ID: <9DS2g.64787$VV4.1227251_at_ursa-nb00s0.nbnet.nb.ca>
Andersen wrote:
>> Which begs the question: does it have to be more than one place? >> is there no acceptable way to connect data sources and sinks to >> one database?
>
> Yes, it needs to be in 100 places, eventual consistency is all that
> matters.
>
>> It seems you've already answered this question and are trying to >> figure out how to maintain a distributed database. I suggest you >> check out the distributed databases already on the market (dismal >> performers) or check out Stonebraker's work-in-process (tolerates >> inconsistencies "for a while.")
>
> Doubt any database systems would help. I am interested in algorithms,
> not off the shelf dbms, becaues I doubt they scale to 100 or 500
> nodes... geographically distributed... It might seem like asking for a
> lot, but I am ready to accept eventual consistency.
I direct you once again to my original answer: "The efficiency will depend on the physical structure representing the sets and on the costs of indexes or sorts."
100 or 500 nodes is physically much different than 2 nodes. Because there are C(N,2) possible edges between N nodes, we are now talking about 4950 to 124750 pairwise connections distributed geographically.
Thus, the first optimization is to arrange your nodes into a more-or-less balanced binary tree.
Pair off your leaf nodes to use the algorithm I already suggested with the modification that the computer evaluating the necessary changes not only applies the changes to itself and its paired computer, but it then pairs itself again with the evaluator from another pair and repeats the process.
Alternatively, arrange the nodes so that they are each paired with two computers and alternate between pairings. The trick there is to make sure you have no islands of nodes separated from the rest.
Since you change the physical structure constantly, I am done. Plonk! Received on Sun Apr 23 2006 - 23:48:53 CEST