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

Jan Provazník jprovazn at redhat.com
Tue Aug 21 20:04:01 UTC 2012


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 at 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



More information about the aeolus-devel mailing list