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