Re: [PATCH conductor] RM 3396: Complex provider selection algorithms (rev. 2)

On 08/17/2012 11:45 AM, Imre Farkas wrote: > On 08/15/2012 05:24 PM, Jozef Zigmund wrote: >> On Thu, 2012-08-02 at 14:24 +0200, ifarkas(a)redhat.com wrote: >>> This revision includes: >>> - a new page where user can enable/disable strategies >>> - fixes to address Jan's and Jozef's findings during their review >>> >> >> ACK, you can pushed the patchset. >> >> As we discussed it's needed to fix ASAP instance variables in patchset >> according "Coding Guidelines" part Instance Variables. [1] >> >> Question at the end: >> Other story is discussion about probability distribution and throwing >> out the matches of selected provider accounts. As we weren't able to say >> exactly if it's ok or not, we'd like to ask community(the best some >> person who has good knowledge from this field) :) >> >> What's happened? >> We are using random match in two places when we are trying to run >> deployment. One of that match is thrown out because the calculated match >> is changed by new one in the final launch. The questions is if we are >> breaking probability distribution of the provider account's selection ? >> I don't think so. If it was true, it would mean that the pseudo random generator distributes random numbers in some regular periodic cycle. It would be very weak pseudo random generator ;). You can check that this is not happening with simple test (same principle as Imre's script): 1. generate however-big-you-want array of rand(100) numbers 2. pick every 3rd (or other) item and add them to array 3. group numbers in this array by their first number -> you get 10 groups, counts of random numbers in each group is balanced But Jozef mentioned that this selection algorithm is called 3 times when launching a deployment - twice in pre-launch phase when checking if a match exists. For these checks it's not necessary to pick one match from possible matches - in these pre-launch validations all you need to know is if any match exists. So it would be best to split find_match_with_common_account method into 2 methods: first which returns all possible matches (this would be used both in pre-launch validations and launch itself) and second method which picks one match from all possibilities.

>> [1] - >> https://www.aeolusproject.org/redmine/projects/aeolus/wiki/Coding_Guidelines >> >> >> >> -- >> Jozef >> > > I created a simple script which you can run on current master branch. It > runs a number of experiments in 2 ways: > - 1st: it is using all the number from the random generator > - 2nd: it randomly throws out some outputs of the random generator > > Then it displays how many times each match have been picked. If you run > the experiment you can see there's no significant difference whether we > are throwing away some numbers of the random generator, or not. > > Here's the source: https://gist.github.com/3377279 > > Why is that? I don't exactly know the mathematical proof for this, so > maybe I am wrong here, but intuitively you can consider the following: > Each pick has the same probability distribution: x% to be picked as A, > y% to be picked as B. No matter which subset do you examine, it is true > for the whole subset that x% of the subset will be picked as A, and y% > will be picked as B, because each and every item in the subset belong to > the same probability distribution. > > Any issue regarding the test, or comment/critique are more than welcomed! > > Imre > > Jan