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

Imre Farkas ifarkas at redhat.com
Thu Aug 23 14:45:24 UTC 2012


On 08/21/2012 10:04 PM, Jan Provazník wrote:
> 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.

Yeah, perfectly makes sense! Thanks for getting into the discussion on 
the probability distributions! :-)

Imre

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